HDOJ 4763 - Theme Section 利用KMP的fail数组,,很暴力

题意:

现在给一个字符串..问订前头..顶后头..中间...不重叠最长的相同串为多长...

题解:

先用KMP得出每个位置的fail值..然后最后一个点开始不断地fail..直到0..标记上这些值..然后从扫描每个位置..每个位置都fail到0..找不冲突.并且最后一个位置fail出现了的.最长的就是答案....

Program:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdlib>
#include<stack>
#include<map>
#define MAXN 1000005
#define MAXM 1000505
#define ll long long 
#define eps 1e-8
using namespace std;   
char s[MAXN];
int fail[MAXN]; 
void KMP(int len)
{
     int i,h;
     memset(fail,0,sizeof(fail));
     for (i=2;i<=len;i++)
     {
             h=fail[i-1];
             while (s[h+1]!=s[i] && h) h=fail[h];
             if (s[h+1]==s[i]) fail[i]=h+1;
                          else fail[i]=0;
     }    
    /* for (i=1;i<=len;i++) printf("%d",fail[i]);
      printf("\n"); */
}
bool maybe[MAXN];
int getans(int len)
{
     int i,h,ans=0;
     memset(maybe,false,sizeof(maybe));
     h=fail[len];
     while (h)
     {
             maybe[h]=true;
             h=fail[h];
     }
     for (i=len-1;i>=1;i--)
     {
             h=fail[i];
             while (h)
             {
                    if (maybe[h] && i<=len-h && i>=2*h) ans=max(ans,h);
                    h=fail[h];
             }
     }
     return ans;
}
int main()
{   
     int cases,len,i; 
     scanf("%d",&cases);
     while (cases--)
     {
             scanf("%s",s+1),len=strlen(s+1);
             KMP(len); 
             printf("%d\n",getans(len));             
     } 
     return 0;
}