感谢宇哥提供的思路,manacher算法,确实很强大,充分利用了回文串的性质
code
/* ID: yueqiq PROG: calfflac LANG: C++ */ #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("calfflac.in","r",stdin) #define writef freopen("calfflac.out","w",stdout) const int maxn = 20005; const int INF = 0x3fffffff; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; const double pi = acos(-1.0); using namespace std; int main() { readf; writef; //无语了 ,定义在外面就会wa char str[maxn], str1[maxn], str2[maxn<<1]; int num[maxn],p[maxn]; int i, j; i=j=0; char c; while (~scanf("%c",&c)){ str[i]=c; if(str[i]>='A'&&str[i]<='Z' || str[i]>='a'&&str[i]<='z'){ str1[j]=str[i]; if( str1[j]>='a'&&str1[j]<='z' ) str1[j]-=32; num[j]=i; j++; } i++; } str[i]='\0'; str1[j]='\0'; //manacher //构造形如#a#b#c#的字符串,确保奇数 str2[0]=str2[1]='#'; j=2; for(i=0; str1[i]!='\0'; i++){ str2[j++]=str1[i]; str2[j++]='#'; } str2[j]='\0'; int maxx=0, maxId=0, id=0, st, ed; for(i=1; str2[i]!='\0'; i++){ if( maxId>i ) p[i]=min(p[2*id-i], maxId-i); else p[i]=1; while( str2[i-p[i]]==str2[i+p[i]]) p[i]++; if(i+p[i]>maxId){ maxId=i+p[i]; id=i; } if(p[i]-1>maxx){ maxx=p[i]-1; st=(i-maxx)/2;//str1中回文的起始 ed=(i+maxx)/2-1; //str1中回文的最后 } } PD(maxx);LN; int s=num[st], e=num[ed];// for(i=s; i<=e; i++) printf("%c",str[i]); LN; }