Codeforces Round #578 (Div. 2)E. Compress Words（字符串hash）

https://codeforc.es/contest/1200/problem/E

hash匹配后缀和前缀，不断更新hash值

 1 #define bug(x) cout<<#x<<" is "<<x<<endl
 2 #define IO std::ios::sync_with_stdio(0)
 3 #include <bits/stdc++.h>
 4 #define iter ::iterator
 5 #define pa pair<int,int>
 6 using namespace  std;
 7 #define ll long long
 8 #define mk make_pair
 9 #define pb push_back
10 #define se second
11 #define fi first
12 #define ls o<<1
13 #define rs o<<1|1
14 const int N=1e6+5;
15 int n;
16 ll mod[5]={1000000009,998244353};
17 ll base[5]={666127,777131};
18 ll p[N][2];
19 ll h[N][2];
20 void init(){
21     for(int i=0;i<2;i++)p[0][i]=1;
22     for(int i=1;i<=N-2;i++){
23         for(int j=0;j<2;j++){
24             p[i][j]=p[i-1][j]*base[j]%mod[j];
25         }
26     }
27 }
28 ll cal(int l,int r,int t){
29     return (h[r][t]-h[l-1][t]*p[(r-l+1)][t]%mod[t]+mod[t])%mod[t];
30 }
31 ll get(char c){
32     if(‘a‘<=c&&c<=‘z‘)return c-‘a‘;
33     if(‘A‘<=c&&c<=‘Z‘)return c-‘A‘+26;
34     if(‘0‘<=c&&c<=‘9‘)return c-‘0‘+52;
35 }
36 string s,t;
37 int main(){
38     IO;
39     cin>>n;
40     cin>>s;
41     int pre=1;
42     init();
43     for(int g=1;g<n;g++){
44         cin>>t;
45         int ns=s.length();
46         for(int i=pre;i<=ns;i++){
47             ll c=get(s[i-1]);
48             for(int j=0;j<2;j++){
49                 h[i][j]=(h[i-1][j]*base[j]%mod[j]+c)%mod[j];
50             }
51         }
52         int nt=t.length();
53         ll H[2]={0};
54         pre=ns+1;
55         int id=0;
56         for(int i=1;i<=nt;i++){
57             int f=0;
58             ll c=get(t[i-1]);
59             for(int j=0;j<2;j++){
60                 H[j]=(H[j]*base[j]%mod[j]+c)%mod[j];
61                 if(cal(ns-i+1,ns,j)==H[j])f++;
62             }
63             if(f==2){
64                 id=i;
65             }
66             if(i==ns)break;
67         }
68         s+=t.substr(id,nt-id);
69     }
70     cout<<s<<endl;
71 }
72 /*
73 7
74 RAtONC14epz KfIenADgDKDci OMmOOQOc yVrfGLV49fW1 xntodZLM5 2f7LXdzX xIhm
75 5
76 I want to order pizza
77 */