串应用- 计算一个串的最长的真前后缀

题目描述

给定一个串，如ABCDAB，则ABCDAB的真前缀有：{ A, AB,ABC, ABCD, ABCDA }ABCDAB的真后缀有：{ B, AB,DAB, CDAB, BCDAB } 因此，该串的真前缀和真后缀中最长的相等串为AB，我们称之为该串的“最长的真前后缀”。试实现一个函数string matched_Prefix_Postfix(string str)，得到输入串str的最长的真前后缀。若不存在最长的真前后缀则输出empty

输入

第1行：串的个数 n第2行到第n+1行：n个字符串

输出

n个最长的真前后缀，若不存在最长的真前后缀则输出empty。

 样例输入

6
a
ab
abc
abcd
abcda
abcdab

样例输出

empty
empty
empty
empty
a
ab

代码

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+20;
int t,n,nex[maxn];
string mains,s,ress;

void getnext(){
    int i=0,j=-1,len=s.length();
    nex[0]=-1;
    while(i<len){
        if(j==-1 || s[i]==s[j]){
            nex[++i]=++j;
        }
        else j=nex[j];
    }
}

int find(){
    int i,j;
    int l1=mains.length(),l2=s.length();
    for(i=0,j=0;i<l1 && j<l2;){
        if(j==-1 || mains[i]==s[j]){
            i++,j++;
        }
        else j=nex[j];
    }
    if(j==l2){
        return i-j+1;
    }
    return -1;
}

int main(){
//    freopen("123.in","r",stdin);
    cin>>t;
    while(t--){
        cin>>s;
        memset(nex,0,sizeof nex);
        getnext();
        int cnt=nex[s.length()];
        if(cnt==0 || cnt==-1) puts("empty");
        else{
            string ans=s.substr(0,cnt);
            cout<<ans<<endl;
        }
    }
    return 0;
}