POJ 3974 最長回文字串（manacher算法）

題意：給出一個字符串，求出最長回文字串。 思路：一開始我直接上了後綴數組DC3的解法，然後MLE了。看了DISCUSS發現還有一種計算回文字串更加優越的算法，就是manacher算法。就去學習了一下， /************************以下轉自http://funnyxj.blog.163.com/blog/static/20459016020127514231538/********************/ 這個算法要解決的就是一個字符串中最長的回文子串有多長。這個算法可以在O（n）的時間復雜度內既線性時間復雜度的情況下，求出以每個字符為中心的最長回文有多長， 這個算法有一個很巧妙的地方，它把奇數的回文串和偶數的回文串統一起來考慮了。這一點一直是在做回文串問題中時比較煩的地方。這個算法還有一個很好的地方就是充分利用了字符匹配的特殊性，避免了大量不必要的重復匹配。 算法大致過程是這樣。先在每兩個相鄰字符中間插入一個分隔符，當然這個分隔符要在原串中沒有出現過。一般可以用‘#’分隔。這樣就非常巧妙的將奇數長度回文串與偶數長度回文串統一起來考慮了（見下面的一個例子，回文串長度全為奇數了），然後用一個輔助數組P記錄以每個字符為中心的最長回文串的信息。P［id］記錄的是以字符str［id］為中心的最長回文串，當以str［id］為第一個字符，這個最長回文串向右延伸了P［id］個字符。 原串： w aa bwsw f d 新串： # w# a # a # b# w # s # w # f # d # 輔助數組P： 1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1 這裡有一個很好的性質，P［id］-1就是該回文子串在原串中的長度（包括‘#’）。如果這裡不是特別清楚，可以自己拿出紙來畫一畫，自己體會體會。當然這裡可能每個人寫法不盡相同，不過我想大致思路應該是一樣的吧。 好，我們繼續。現在的關鍵問題就在於怎麼在O（n）時間復雜度內求出P數組了。只要把這個P數組求出來，最長回文子串就可以直接掃一遍得出來了。 由於這個算法是線性從前往後掃的。那麼當我們准備求P［i］的時候，i以前的P［j］我們是已經得到了的。我們用mx記在i之前的回文串中，延伸至最右端的位置。同時用id這個變量記下取得這個最優mx時的id值。（注：為了防止字符比較的時候越界，我在這個加了‘#’的字符串之前還加了另一個特殊字符‘$’，故我的新串下標是從1開始的） /********************************************************************************************************************************/ CODE：

 
#include <set>  
#include <map>  
#include <stack>  
#include <cmath>  
#include <queue>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <iomanip>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 0x3fffffff  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair<int,int>  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
#define N 2000055  
using namespace std;  
  
char s[N] ;  
char str[N] ;  
int rad[N] ;  
int manacher () {  
    int len = strlen(s) ;  
    int max = 0;  
    str[0] = '$';  
    str[1] = '#';  
    int i = 0  ;  
    for (; i < len; i++) {  
        str[i * 2 + 2] = s[i];  
        str[i * 2 + 3] = '#';  
    }  
    str[2 * len + 2] = 0;  
    for (int i = 1; i < 2 * len + 2 ; i++) {  
        rad[i] = 0;  
    }  
    int id = 0;  
    for (i = 1; i < 2 * len + 2; i++) {  
        if (max > i)  
            rad[i] = min(rad[2 * id - i], rad[id] + id - i) ;  
        else  
            rad[i] = 1 ;  
        while (str[i + rad[i]] == str[i - rad[i]])  
            rad[i] ++ ;  
        if (rad[i] + i > max) {  
            max = rad[i] + i;  
            id = i;  
        }  
    }  
    int mx = 0;  
    for (i = 1; i < 2 * len + 2 ; i++) {  
        if (mx < rad[i] - 1)  
            mx = rad[i] - 1;  
    }  
    return mx;  
}  
  
int main() {  
    int ca = 0 ;  
    while(scanf("%s",s) != EOF) {  
        if(strcmp(s , "END") == 0)break ;  
        printf("Case %d: " , ++ ca) ;  
        printf("%d\n",manacher()) ;  
    }  
    return 0 ;  
}