Soulist 的博客

—可惜当时年少

题解 CF1200E 【Compress Words】

这道题也是非常毒了。。。

主要是题意,我猜应该有很多人和我一样以为是合并 $i$和 $i-1$吧

实际上题意是说每新读入一个新字符串就将其和已有的字符串合并。

$Sol.$

考虑每次新加入一个单词,我们可以枚举一个长度,判断其前缀和已有字符串的后缀是否相同。

这个相同用 $hash$判就好了。

然后暴力算的话复杂度会带个 $\log$,所以还要预处理一下每个数前面的系数的 $k$次方在 $\%hash$意义下是多少。

这样就是 $O(S)$了

#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;
}

2019-08-12 21:08:41 in 哈希