Codeforce 1200 E. Compress Words（字元串Hash + 暴力）

題目大意：有 n 個單詞，按順序把 n 個單詞拼起來成一整個單詞，拼起來的時候前一個單詞的字尾 和後一個單詞的字首的最長相同部分要省略掉一個，例如：apple please 拼起來是 applese

所有單詞總長不超過 1 0 6 10^6 106

題解：用字元串hash可以 O ( n ) O(n) O(n)處理， O ( 1 ) O(1) O(1)比較。因為每個串隻會被掃一遍，可以直接暴力，預處理 O ( n ) O(n) O(n)，暴力 O ( n ) O(n) O(n)查找最長相同部分。

由于字元串長達到了 1 0 6 10^6 106，單模hash 已經搞不了，要用更安全的雙 hash,取 2 個較大的模數 mod1 和 mod2，以及一個素數 p (p 不用太大，單模的 p 也不用太大，模數一定要大)

（這題就作為字元串hash入門了）

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 3e6 + 10;
#define pll pair<long long,long long>
ll p = 201326611;
ll h = 402653189;
ll pw[maxn],hw[maxn];
ll hash1[maxn];
ll hash2[maxn];
ll tmp1[maxn],tmp2[maxn];
char s[maxn],t[maxn];
int n;
pll Hash(int l,int r,ll hash1[],ll hash2[]) {
	return pll((hash1[r] - hash1[l  - 1] * hw[r - l + 1] % h + h) % h,(hash2[r] - hash2[l - 1] * pw[r - l + 1] % p + p) % p);
}
int main() {
	hw[0] = pw[0] = 1;
	for(int i = 1; i < maxn; i++) {
		hw[i] = hw[i - 1] * 131 % h; 
		pw[i] = pw[i - 1] * 131 % p;
	}
	scanf("%d",&n);
	int tot = 1,lst = 1;
	hash1[0] = hash2[0] = 0;
	for(int i = 1; i <= n; i++) {
		if(i == 1) {
			scanf("%s",s + 1);
			tot = strlen(s + 1);
			continue;
		}
		scanf("%s",t + 1);
		int len = strlen(t + 1);
		for(int j = lst; j <= tot; j++) {
			hash1[j] = (hash1[j - 1] * 131 + 1ll * s[j]) % h;
			hash2[j] = (hash2[j - 1] * 131 + 1ll * s[j]) % p;
		}
		lst = tot;
		for(int j = 1; j <= len; j++) {
			tmp1[j] = (tmp1[j - 1] * 131 + 1ll * t[j]) % h;
			tmp2[j] = (tmp2[j - 1] * 131 + 1ll * t[j]) % p;
		}
		int pos = 0;
		for(int j = 1; j <= len && j <= tot; j++)
			if(Hash(1,j,tmp1,tmp2) == Hash(tot - j + 1,tot,hash1,hash2))
				pos = j;
		for(int j = 1 + pos; j <= len; j++)
			s[++tot] = t[j];
	}
	s[++tot] = 0;
	printf("%s\n",s + 1);
	return 0;
}