? 题意：求最长的回文串。 思路：同样是用Mancher算法在O(n)的时间内解决(我其实是来练练板子的
#include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, /STACK:102400000,102400000) using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const double pi= acos(-1.0); const double esp=1e-6; const int maxn=1000010; char str[maxn]; char s[maxn*2]; int p[maxn*2]; int len; void Manacher() { int i; s[0]='$'; s[1]='#'; for(i=0;i i) p[i]=min(p[2*id-i],p[id]+id-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) p[i]++; if(p[i]+i>p[id]+id) { id=i; } if(p[i]>MaxL) MaxL=p[i]; } printf(%d ,MaxL-1); } int main() { int icase=1; while(~scanf(%s,&str)) { if(strcmp(str,END)==0) break; len=strlen(str); printf(Case %d: ,icase++); Manacher(); } return 0; }
?