最近在学习后缀数组,然后想学习如何高效的求最长回文串,竟查到了这贴,呵呵。这是我写的代码,用后缀数组求最长回文串,不过效率不行,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;
}
#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;
}