UKE了!!!
查看原帖
UKE了!!!
552688
clx201022楼主2023/2/26 10:00
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>kmp;
int n;
char t[N],s[N];
void prefix(string s,vector<int> &kmp,int ss){
    kmp[0]=0;//0~s.size()-1
    for(int i=1;i<ss;i++){
        int j=kmp[i-1];
        while(j/*>0*/&&s[i]!=s[j])j=kmp[j-1];
        if(s[i]==s[j])j++;
        kmp[i]=j;
    }
    return;
}
int KMP(string s,string t,int st,int ss)
{
    //vector<int>v;//s在t中出现的位置
    int pre=0/*前一个位置的前缀函数值*/,ps=max(st-ss,0);
    if(s[0]==t[ps])pre++;
    for(int i=ps+1;i<st;i++){
        int j=pre;
        while(j/*>0*/&&t[i]!=s[j])j=kmp[j-1];
        if(t[i]==s[j])j++;
        pre=j;
    }
    return pre;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",t);
    for(int i=1;i<n;i++)//n-1次
    {
        scanf("%s",s);
        int ss=strlen(s);
        int st=strlen(t);
        kmp.resize(ss);
        prefix(s,kmp,ss);
        int cnt=KMP(s,t,st,ss);
        for(int j=cnt;j<ss;j++)
        {
            t[st++]=s[j];
        }
    }
    printf("%s",t);
    return 0;
}
2023/2/26 10:00
加载中...