1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 char b[10000001],a[10000001]; 6 char tmp[10000001]; 7 int n,f[10000001],zu;//f[i]表示插入一堆#后，以i为中心的最长回文子串の半径长度， 8                 //故其减1后就是原串的最长回文子串的答案  9                 //也是原串中以i为开端的最长回文串の长度。 10 int id,maxid,ans;11 int main()12 {13     while(1)14       {15           scanf("%s",tmp);16           if(tmp[0]==‘E‘)17             break;18           zu++;19           n=strlen(tmp);20           memset(b,0,sizeof(b));21           memset(a,0,sizeof(a));22           memset(f,0,sizeof(f));23           ans=id=maxid=0;24           for(int i=1;i<=n;i++) 25           b[i]=tmp[i-1];26         a[1]=‘#‘;27         for(int i=1;i<=n;i++) 28           {29             a[i<<1]=b[i]; 30              a[i<<1|1]=‘#‘;31            }32         a[0]=‘-‘;33         a[(n+1)<<1]=‘+‘;34         n=n<<1|1;35         f[1]=1;36         id=1;//用id这个变量记下取得这个最优maxid时的id值 37              //即右端扩展到maxid+1时，该回文串中心的位置 38         maxid=2;//maxid是曾经扫描到的回文串中，匹配到的最远的位置+139         for(int i=2;i<=n;i++)40           {41              if(maxid>i)//算法核心：防止重复匹配 42                  f[i]=min(f[(id<<1)-i]//以 关于id的对称点 为中心的的最长回文串长43                                    //因为，分别在id两侧的两半回文串是完全一样的 44                        ,maxid-i    // 但是，以id的对称点为中心的最长回文串有可能超出45                                    //以id为中心的最长回文串的范围，所以，限制其无法超出46                                    //此范围 47                                    ); //(id<<1)-i 为 i 关于 id 的对称点 48               else49               f[i]=1;//否则f[i]=150               for(;a[i+f[i]]==a[i-f[i]];f[i]++);51               ans=max(ans,f[i]-1);52             if(f[i]+i>maxid)//注意是f[i]+i，不是f[i]+i-1，因为maxid是匹配到的最远位置+153               {54                 maxid=f[i]+i;55                 id=i;//若以i为中心时，回文串可以扩展到更远的地方，更新id 56               }57           }58         printf("Case %d: %d\n",zu,ans);59       }60     61     return 0;62 }