本文共 1387 字，大约阅读时间需要 4 分钟。
analyse:
直接暴力枚举每一个终点，然后枚举回文串的半径即可.
Time complexity：O(n*m)
Source code：
// Memory Time// 1347K 0MS// by : Snarl_jsb// 2014-10-03-14.25#include #include #include #include #include #include #include #include #include #include #include #include #define N 1000010#define LL long longusing namespace std;int k,real[1100],sta,max_len,cas=1;char st[1100],ss[1100];int main(){ ios_base::sync_with_stdio(false); cin.tie(0);// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout); while(~scanf("%d",&k)) { getchar(); gets(st); int len=0; max_len=0; int l1=strlen(st); for(int i=0;i ='a'&&st[i]<='z')||(st[i]>='A'&&st[i]<='Z')) { if(st[i]>='A'&&st[i]<='Z') st[i]+=32; ss[len]=st[i]; real[len]=i; len++; } } for(int i=0;i =0;++j) { if(ss[i+j]!=ss[i-j]) error++; if(error>k) break; } j--; if(real[i+j]-real[i-j]+1>max_len) { max_len=real[i+j]-real[i-j]+1; sta=real[i-j]; } error=0; for(j=1;i+j =0;++j) { if(ss[i+j]!=ss[i-j+1]) error++; if(error>k) break; } j--; if(j<=0) continue; if(real[i+j]-real[i-j+1]+1>max_len) { max_len=real[i+j]-real[i-j+1]+1; sta=real[i-j+1]; } } printf("Case %d: %d %d\n",cas++,max_len,sta+1); } return 0;}
转载于:https://www.cnblogs.com/crazyacking/p/4005207.html