CF1200E Compress Words KMPHash

https://codeforces.com/problemset/problem/1200/E

这个题就是求字符串拼接后的字符串，中间重复的不要

Hash或者KMP解决
就是匹配新出现的串与原来串的（长度与新出现串相等的）后缀的匹配
KMP做法

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e6+12;
char s[maxn];
char t[maxn];
int fail[maxn];
int main ()
{
    int n;
    int e=0;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",s);
        int len=strlen(s);
        int j=0,k=-1;
        fail[0]=-1;
        while(j<len)
        {
            if(k==-1||s[j]==s[k])
            {
                ++j;
                ++k;
                fail[j]=k;
            }
            else
            {
                k=fail[k];
            }
        }
        int i=max(0,e-len);
        j=0;
        while(i<e)
        {
            if(j==-1||t[i]==s[j])
            {
                j++;
                i++;
            }
            else
            {
                j=fail[j];
            }
        }
        while(j<len)
        {
            t[e]=s[j];
            putchar(t[e]);
            e++;
            j++;
        }
    }
    return 0;
}

HASH做法

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e6+10;
char s[maxn];
char tp[maxn];
int mod=1e9+7;
int mod1=1313131;
int mod2=998244353;
int mu=1;
ll ha1[maxn];
ll ha2[maxn];
ll g1[maxn];
ll g2[maxn];
void init()
{
    g1[0]=1;
    g1[0]=1;
    for(int i=1;i<maxn;i++)
    {
        g1[i]=g1[i-1]*mod1%mod;
        g2[i]=g2[i-1]*mod2%mod;
    }
}
ll hash1(int a,int b)
{
    return (ha1[b]-ha1[a-1]*g1[b-a+1]%mod+mod)%mod;
}
ll hash2(int a,int b)
{
    return (ha2[b]-ha2[a-1]*g2[b-a+1]%mod+mod)%mod;
}
void f(char c)
{
    ha1[mu]=(ha1[mu-1]*mod1+c)%mod;
    ha2[mu]=(ha2[mu-1]*mod2+c)%mod;
    mu++;
}
int main()
{
    int n;
    init();
    cin>>n;
    while(n--)
    {
        scanf("%s",tp+1);
        int pos=1;
        int len=strlen(tp+1);
        int mi=min(len,mu-1);
        ll h1=0,h2=0;
        for(int i=0;i<mi;i++)
        {
            int posm=mu-i-1;
            int posz=i+1;
            h1=(h1*mod1+tp[posz])%mod;
            h2=(h2*mod2+tp[posz])%mod;
            ll w1=hash1(posm,mu-1);
            ll w2=hash2(posm,mu-1);
            if(hash1(posm,mu-1)==h1&&hash2(posm,mu-1))
            {
                pos=2+i;
            }
        }
        for(int i=pos;i<=len;i++)
        {
            f(tp[i]);
            printf("%c",tp[i]);
        }
    }
    return 0;
}