link

大家都用 KMP 写，我试了一下 Z 函数 Wrong Answer 了

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,len[4005],now;
char a[4005][205],c[1000005];
ll z[1000005];
ll maxx(ll a,ll b){
    return a>b?a:b;
}
ll minn(ll a,ll b){
    return a<b?a:b;
}
void Make(ll x,ll number){
    now=0;
    for(ll i=x;i<=len[1];i++){
        c[++now]=a[1][i];
    }
    c[++now]='&';
    for(ll j=1;j<=len[number];j++) c[++now]=a[number][j];
}
void Z_function(){
    ll l=0, r=0;
    for(ll i=1;i<=now;i++) z[i]=0;
    for(ll i=2;i<=now;i++){
        z[i]=(i>r)?0:minn(r-i+1,z[i-l+1]);
        while(z[i]<now && c[1+z[i]]==c[i+z[i]]) z[i]++;
        if(i+z[i]-1>r) l=i, r=i+z[i]-1;
    }
}
int main(){
    while(scanf("%lld",&n)!=EOF && n){
        for(ll i=1;i<=n;i++){
            scanf("%s",a[i]+1);
            len[i]=strlen(a[i]+1);
        }
        ll ans1=0; string Now=""; 
        for(ll i=1;i<=len[1];i++){ // 暴力枚举第一个字符串的子串的一个优化：i 是当前枚举到的左端点，那么以它开头的字符串可以一次性处理掉，起到优化的作用
            ll Min=1e18;
            for(ll j=2;j<=n;j++){
                Make(i,j);
                Z_function(); // 把两个字符串拼接起来求 Z 函数，相当于用第 j 个字符串和第一个字符串当前后缀进行匹配
                ll Max=0;
                for(ll k=len[1]-i+2;k<=now;k++){
                    Max=maxx(Max,z[k]);
                } // 求出该字符串最长能匹配的长度
                Min=minn(Min,Max); // 求 min 值是因为这个公共子串所有串都得有
            }
            if(!Min) continue;
            string tmp="";
            for(ll j=i;j<=i+Min-1;j++) tmp.push_back(a[1][j]);
            if(Min>ans1){
                ans1=Min;
                Now=tmp;
            }else if(Min==ans1 && (Now=="" || tmp<Now)) Now=tmp; // 以上就是更新答案
        }
        if(ans1==0) puts("IDENTITY LOST");
        else{
            cout<<Now<<endl;
        } // 输出
    }
}