hash,wa on #5,玄关求条
查看原帖
hash,wa on #5,玄关求条
807667
JenF楼主2024/11/19 19:42
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,MOD=1011451423,b=131;
int n;
string a,ans;
int pw[N],hs[N],hs1[N];//hs1:ans的hs
void init(){
    pw[0]=1;
    for(int i=1;i<N;i++){
        pw[i]=(pw[i-1]*b)%MOD;
    }
}
void has(string s){
    hs[0]=0;
    int l=s.length();
    for(int i=0;i<l;i++){
        hs[i+1]=(hs[i]*b%MOD+s[i])%MOD;
    }
}
int has1(int x){
    return (hs1[ans.size()]-hs1[ans.size()-x]*pw[x]%MOD)%MOD;
}
void has2(int x,char c){
    hs1[x]=(hs1[x-1]*b%MOD+c)%MOD;
}
signed main(){
    //freopen("test.in","r",stdin);
    init();
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        cin>>a;
        has(a);
        for(int j=min(a.size(),ans.size());j>=0;--j){
            if(has1(j)==hs[j]){
                for(int k=j;k<a.size();k++){
                    has2(ans.size()+1,a[k]);
                    ans+=a[k];
                }
                break;
            }
        }
    }
    cout<<ans;
    return 0;
}

2024/11/19 19:42
加载中...