题解 CF1200E 【Compress Words】
Soulist
2019-08-12 21:08:41
这道题也是非常毒了。。。
~~主要是题意，我猜应该有很多人和我一样以为是合并$i$和$i-1$吧~~
~~实际上~~题意是说每新读入一个新字符串就将其和已有的字符串合并。
$Sol.$
考虑每次新加入一个单词，我们可以枚举一个长度，判断其前缀和已有字符串的后缀是否相同。
这个相同用$hash$判就好了。
然后暴力算的话复杂度会带个$\log$，所以还要预处理一下每个数前面的系数的$k$次方在$\%hash$意义下是多少。
这样就是$O(S)$了
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int read() {
char cc = getchar(); int cn = 0, flus = 1;
while(cc < '0' || cc > '9') { if( cc == '-' ) flus = -flus; cc = getchar(); }
while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar();
return cn * flus;
}
const int mod = 1e9 + 7 ;
const int mod2 = 1e9 + 9 ;
const int ha = 233 ;
const int ha2 = 377 ;
const int N = 1e6 + 5 ;
int n, cnt, r, inv[N], inv2[N] ;
char out[N], s[N] ;
signed main()
{
n = read() ; int Maxa = 1e6 ; inv[0] = 1, inv2[0] = 1 ;
rep( i, 1, Maxa ) inv[i] = ( inv[i - 1] * ha ) % mod, inv2[i] = ( inv2[i - 1] * ha2 ) % mod ;
rep( i, 1, n ) {
scanf("%s", s + 1 ) ;
r = strlen( s + 1 ) ;
int hash1 = 0, hash2 = 0 ;
int hash12 = 0, hash22 = 0 ;
int k = min( r, cnt ), ans = 0 ;
rep( i, 1, k ) {
hash1 = ( hash1 * ha + s[i] ) % mod ;
hash2 = ( hash2 + out[cnt - i + 1] * inv[i - 1] ) % mod ;
hash12 = ( hash12 * ha2 + s[i] ) % mod ;
hash22 = ( hash22 + out[cnt - i + 1] * inv2[i - 1] ) % mod ;
if( hash1 == hash2 && hash12 == hash22 ) ans = i ;
}
for( int i = ans + 1; i <= r; ++ i ) out[++ cnt] = s[i] ;
}
rep( i, 1, cnt ) printf("%c", out[i] ) ;
return 0;
}
```