String application - calculate the longest true prefix of a string

Title Description

Given a string , Such as ABCDAB, be ABCDAB The true prefix of has ：{ A, AB,ABC, ABCD, ABCDA }ABCDAB The true suffix of has ：{ B, AB,DAB, CDAB, BCDAB } therefore , The longest equivalent string between the true prefix and the true suffix of this string is AB, We call it the string “ The longest true prefix ”. Try to implement a function string matched_Prefix_Postfix(string str), Get the input string str The longest true prefix of . If there is no longest true prefix, output empty

Input

The first 1 That's ok ： The number of strings n The first 2 Go to the first place n+1 That's ok ：n A string

Output

n The longest true prefix , If there is no longest true prefix, output empty.

  The sample input

6
a
ab
abc
abcd
abcda
abcdab

Sample output

empty
empty
empty
empty
a
ab

Code

#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;
}