KMP-hdu-4763-Theme Section - c++编程基础

题目意思：

给一个字符串S，求最大长度的串A，使得S满足APAQA。

解题思路：

kmp.

先求出S串的next数组，然后从next[n]开始，如果next[n]<=n/3,然后从n/3+1开始到n-next[n]用kmp,判断是否存在1~next[n]的子串。如果不存在则继续往前找。

代码：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define eps 1e-6  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
#define ll __int64  
#define LL long long  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 1100000  
  
int next[Maxn];  
int n,cnt,nn;  
char save[Maxn];  
  
void getnext()  
{  
    int j=0;  
  
    next[1]=0;  
    for(int i=2;i<=n;i++)  
    {  
        while(j>




0&&save[j+1]-save[i])  
            j=next[j];  
        if(save[j+1]==save[i])  
            j++;  
        next[i]=j;  
    }  
    return ;  
}  
bool kmp(int a,int b) //在a,b区间是否存在与1~nn之间的子串  
{  
    int j=0;  
  
    for(int i=a;i<=b;i++)  
    {  
        while(j>0&&save[j+1]-save[i])  
            j=next[j];  
        if(save[j+1]==save[i])  
            j++;  
        if(j==nn)  
            return true;  
    }  
    return false;  
}  
  
int main()  
{  
  int t;  
  
  scanf("%d",&t);  
  while(t--)  
  {  
      scanf("%s",save+1);  
      n=strlen(save+1);  
      getnext();  
      int i=n;  
      int ans=0;  
      while(i>n/3) //A串的长度肯定<=n/3  
        i=next[i];  
  
      while(i)  
      {  
          nn=i;  
          cnt=0;  
  
          bool flag=kmp(i+1,n-i); //是否存在  
          if(flag)  
          {  
             ans=i; //找到了  
             break;  
          }  
          i=next[i]; //继续往前 使得满足前后  
      }  
      printf("%d\n",ans);  
  }  
   return 0;  
}