最近在学习后缀数组，然后想学习如何高效的求最长回文串，竟查到了这贴，呵呵。这是我写的代码，用后缀数组求最长回文串，不过效率不行，hdu3068过不了超时。据说最长回文串用扩展KMP求效率还可以，学习中
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define MAX 220009
int sa[MAX],rank[MAX],height[MAX],tem[MAX],wa[MAX],w[MAX];

void BuildSa(string &str){
    int *x=rank,*tem1;
    memset(tem,0,sizeof(tem));
    for(int i=0; i<str.size(); ++i) tem[ str[i] ]++;
    for(int i=1; i<128; ++i) tem[i]+=tem[i-1];
    for(int i=str.size()-1;i>=0;--i)sa[--tem[str[i]]]=i;
    x[sa[0]]=0;
    for(int i=1; i<str.size(); ++i){
        if(str[sa[i]]==str[sa[i-1]])
            x[sa[i]]=x[sa[i-1]];
        else
            x[sa[i]]=x[sa[i-1]]+1;
    }
    int *y=wa;
    for(int j=1,p=1,m=128; p<str.size(); j*=2,m=p){
        p=0;
        for(int i=str.size()-j; i<str.size(); ++i ) y[p++]=i;
        for(int i=0; i<str.size(); ++i )
            if( sa[i]>j) y[p++]=sa[i]-j;
        for(int i=0; i<str.size(); ++i ) w[i]=x[y[i]];
        memset(tem,0,sizeof(tem));
        for(int i=0; i<str.size(); ++i ) tem[w[i]]++;
        for(int i=1; i<m; ++i ) tem[i]+=tem[i-1];
        for(int i=str.size()-1; i>=0; --i ) sa[--tem[w[i]]]=y[i];
        tem1=x; x=y; y=tem1;
        x[sa[0]]=0; p=1;
        for(int i=1; i<str.size(); ++i){
            if( y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j])
                x[sa[i]]=p-1;
            else
                x[sa[i]]=p++;
        }
    }
}
void BuildHeight(string &str){
    for(int i=1; i<str.size(); ++i) rank[sa[i]]=i;
    for(int i=0,k=0; i<str.size()-1; ++i){
        if(k>0) k--; else k=0;
        int j=sa[rank[i]-1];
        while( str[i+k]==str[j+k]) k++;
        height[rank[i]]=k;
    }
}
int LCP( int a, int b){
    int x,y;
    if( rank[a] > rank[b]){
        x=rank[b];
        y=rank[a];
     }
     else{
          y=rank[b];
          x=rank[a];
     }
    int min=9999999;
    for(int j=x+1; j<=y; ++j )
       if(height[j] < min ) {
           min=height[j];
       }
    return min;
}
int main(){
    string str;
    while( cin >> str ){
        string word=str;
        str+="Z";
        reverse(word.begin(),word.end());
        str+=word;
        str+="A";
        BuildSa(str);
        BuildHeight(str);

         int w=0,max=1;
        for(int i=0; i<word.size(); ++i ){
            int k=LCP(i,2*word.size()-i);//奇数长度回文窜
            if(k!=9999999 && k*2-1>max) {max=k*2-1;w=i;}
            k=LCP(i,2*word.size()-i+1);//偶数长度回文串
            if(k!=9999999 && k*2>max) {max=k*2;w=i;}
            if(max==word.size()) break;
        }
        cout << "最长回文串长度为: " << max << endl;
        cout << "最长回文串为: ";
        if(max%2==0)
            for(int i=w-max/2; i<w+max/2; ++i ) cout << str[i];
        else
            for(int i=w-max/2; i<=w+max/2; ++i ) cout << str[i];
        cout << endl;
    }
    return 0;
}