参考：http://blog.sina.com.cn/s/blog_70811e1a01014esn.html
首先，将字符串都变成奇数字符串（如：将12121变成$1#2#1#2#1*，考虑到边界问题，将第一个与最后一个设置为不同的）
#include <iostream> #include <cmath> #include <string> using namespace std; void findBMstr(string str) { int s=str.size(); int *rad=new int[s]; int i,j,k; for (i=1,j=0;i<s-1;) { while(str[i-j-1]==str[i+j+1]) j++; rad[i]=j; for (k=1;k<=j&&rad[i-k]!=rad[i]-k;k++) rad[i+k]=min(rad[i-k],rad[i]-k); i+=k; j=max(j-k,0); } int ma=0;j=1; for (int i=1;i<s-1;i++) { if (ma<rad[i]) { j=i; ma=rad[i]; } } int start=j-ma; int end=j+ma; for (i=start;i<=end;i++) { if (str[i]!='#') cout<<str[i]; } cout<<endl; delete []rad; } int main() { string a,b="$"; cin>>a; int size=a.size(); b+=a[0]; for (int i=1;i<size;i++) { b+='#'; b+=a[i]; } b+='*'; cout<<a<<endl; findBMstr(b); return 0; }
