HDU - 4763 -Theme Section(迭代求公共前后缀跑KMP)

博主链接

题目链接

题意：

给一个字符串，求出字符串的最大的相同前缀后缀，并且满足前缀后缀在字符串中间出现了。

题解：

可以先对字符串跑KMP求一下Next数组，由next数组定义可以知道，里面存的是当前字符最长前缀和后缀，所以我们只需要从最后一个字符出发，递归寻找每个长度为的Next值的前缀后缀，对于长度为len的前缀，只需要用该前缀起和字符串的除了前缀和后缀的部分匹配就可以了，如果匹配成功，就看是否需要更新答案。

代码：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+21;
const int mod=1e9+7;
char s[maxn];
int nex[maxn];
int len;
void GetNex(){
    int j=-1;
    for(int i=0;s[i];i++){
        while(s[i]!=s[j+1]&&j!=-1)j=nex[j];
        if(s[i]==s[j+1]&&i!=0)j++;
        nex[i]=j;
    }
}
bool kmp(int l){
    int j=-1;
    for(int i=l;i<len-l;i++){
        while(j!=-1&&s[j+1]!=s[i])j=nex[j];
        if(s[i]==s[j+1])j++;
        if(j+1==l)return true;
    }
    return false;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s",s);
        len=strlen(s);
        if(len<3){
            puts("0");
            continue;
        }
        GetNex();
        int ans=nex[len-1];
        int mx=0;
        while(ans!=-1){
            if(kmp(ans+1)){
                mx=max(mx,ans+1);  //查找中间是否有这个串
            }
            ans=nex[ans];
        }
        printf("%d\n",mx);
    }
    return 0;
}