最長回文子串——Manacher算法

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;
char c[2000010];
void Insert(string s){
    c[0]='@';
    for(int j=0; j<s.length(); j++){
        c[2*(j+1)]= '@';
        c[2*j+1]=s[j];
    }
}

int min(int a, int b){
    return a>b?b:a;
}

int main()
{
    int n;
    int mx;
    int p;
    int max;
    string s;
    vector<int> v;
    cin>>n;
    for(int j=0; j<n; j++){
        cin>>s;
        Insert(s);
        max=0;
        mx=0;
        p=0;
        v.clear();
        int l=2*s.length()+1;
        for(int i=0; i<l; i++){
            //cout<<max<<endl;
            if(mx>i){
                v.push_back(min(mx-i, v[p*2-i]));
            }else{
                v.push_back(1);
            }
            while(c[i+v[i]]==c[i-v[i]] && (i+v[i])<l && (i-v[i])>=0) v[i]++;
            if((v[i]+i)>mx) {
                mx=v[i]+i;
                p=i;
            }
            if(v[i]>max) max=v[i];
        }
        cout<<max-1<<endl;
    }
    return 0;
}
           

hihoCoder的1032道題的解題代碼

附上最易了解的

算法講解講解

http://m.blog.csdn.net/article/details?id=42061017

以及我了解的Manacher算法：

該算法的思想是從中心向兩邊探索回文，并标記之前探索的回文右邊最遠的字元的下标

1）如果是這種情況：

0  1  2  3  4  5  6  7  8  9  10

c  b  c  d   c  b  c   c  e  c    a

比如現在我要探索的是b（下标5），之前探索的以d（下标3）文中心的最長回文是c  b  c  d  c  b  c，右邊最遠字元是c（下标6），以d為中心最有兩邊是對稱的，b（下标5）的對稱點是b（下标1），右邊最遠字元c（下标6）關于d的對稱點是下标0的字元c，則b（下标1）到c（下标0）這部分的對應字元是b（下标5）到c（下标0），這部分字元前面已經探索過了，可以跳過比對過的，從c（下标7）開始探索，因為這部分是未探索過的。

2）如果是這種情況：

0  1  2  3  4  5  6  7  8  9  10

a  b  c  d  c  b  a   c   e   c    a

比如現在我要探索的是c（下标7），之前探索的以d（下标3）文中心的最長回文是c  b  c  d  c  b  c，右邊最遠字元是c（下标6），c（下标7）是一個新的字元，自己本身都沒有比對過，是以隻能老老實實的一個一個的兩邊比對了。

以上是我的了解。