哈希表
1 | const int HASH_CNT = 2; |
2 | const int mod[HASH_CNT] = {(int)1e9 + 7, 998244353}; |
3 | const int seed[HASH_CNT] = {27, 39}; |
4 | typedef vector<int> vi; |
5 | struct swh{ |
6 | vector<char> s; int len = 0; |
7 | vector<int> pre[HASH_CNT], pw[HASH_CNT]; |
8 | void init(){ |
9 | s.clear(); |
10 | s.push_back(0); |
11 | len = 0; |
12 | for(int i = 0; i < HASH_CNT; i++){ |
13 | pre[i].push_back(0); |
14 | pw[i].push_back(1); |
15 | } |
16 | } |
17 | swh(){init();} |
18 | void extend(char ch){ |
19 | s.push_back(ch); len++; |
20 | for(int i = 0; i < HASH_CNT; i++){ |
21 | pw[i].push_back(1ll * pw[i].back() * seed[i] % mod[i]); |
22 | int t = int((1ll * pre[i].back() * seed[i] + ch) % mod[i]); |
23 | pre[i].push_back(t); |
24 | } |
25 | } |
26 | vi gethash(int l, int r){ |
27 | vi res(HASH_CNT, 0); |
28 | for(int i = 0; i < HASH_CNT; i++){ |
29 | int t = (int)((pre[i][r] - 1ll * pre[i][l - 1] * pw[i][r - l + 1]) % mod[i]); |
30 | if(t < 0) t += mod[i]; |
31 | res[i] = t; |
32 | } |
33 | return res; |
34 | } |
35 | }; |
36 | bool equal(const vi &a, const vi &b){ |
37 | bool res = 1; |
38 | for(int i = 0; i < HASH_CNT; i++) res &= a[i] == b[i]; |
39 | return res; |
40 | } |
KMP
1 | const int L = 1e6 + 7; |
2 | int nxt[L]; |
3 | void getNext(char *s){ |
4 | int l = strlen(s + 1); |
5 | int j = -1; |
6 | nxt[0] = -1; |
7 | for(int i = 1; i <= l; i++){ |
8 | while(~j && s[i] != s[j + 1]) j = nxt[j]; |
9 | nxt[i] = ++j; |
10 | } |
11 | } |
12 | int kmp(char *s, char *t){ |
13 | int l = strlen(s + 1), m = strlen(t + 1); |
14 | int res = 0; //匹配次数 |
15 | int j = 0; |
16 | for(int i = 1; i <= l; i++){ |
17 | while(~j && s[i] != t[j + 1]) j = nxt[j]; |
18 | if(++j == m) res++; |
19 | } |
20 | return j; |
21 | } |
拓展KMP（求Z函数）
1 | const int N = 2E7 + 7; |
2 | int z[N * 2]; |
3 | void getZ(const char* s){ |
4 | int l = 0, r = 0; |
5 | int len = strlen(s + 1); |
6 | z[1] = len; // 根据题目要求决定 |
7 | for(int i = 2; i <= len; i++){ |
8 | if(i <= r) z[i] = min(z[i - l + 1], r - i + 1); |
9 | else z[i] = 0; |
10 | while(i + z[i] <= len && s[i + z[i]] == s[1 + z[i]]) z[i]++; |
11 | if(i + z[i] - 1 > r){ |
12 | l = i; r = i + z[i] - 1; |
13 | } |
14 | } |
15 | } |
Trie树
普通模板（转自OIwiki）
1 | struct trie { |
2 | int nex[100000][26], cnt; |
3 | bool exist[100000]; // 该结点结尾的字符串是否存在 |
4 | |
5 | void insert(char *s, int l) { // 插入字符串 |
6 | int p = 0; |
7 | for (int i = 0; i < l; i++) { |
8 | int c = s[i] - 'a'; |
9 | if (!nex[p][c]) nex[p][c] = ++cnt; // 如果没有，就添加结点 |
10 | p = nex[p][c]; |
11 | } |
12 | exist[p] = 1; |
13 | } |
14 | bool find(char *s, int l) { // 查找字符串 |
15 | int p = 0; |
16 | for (int i = 0; i < l; i++) { |
17 | int c = s[i] - 'a'; |
18 | if (!nex[p][c]) return 0; |
19 | p = nex[p][c]; |
20 | } |
21 | return exist[p]; |
22 | } |
23 | }; |
维护异或和
1 | namespace xorvTrie{ // 自低位到高位依次插入，支持全局加1 |
2 | const int D = 20; |
3 | const int SZE = N * D; |
4 | int rt[N], ch[SZE][2], cnt[SZE], xorv[SZE]; |
5 | int tot = 0; |
6 | void maintain(int o){ |
7 | cnt[o] = xorv[o] = 0; |
8 | if(ch[o][0]){ |
9 | cnt[o] += cnt[ch[o][0]]; |
10 | xorv[o] ^= xorv[ch[o][0]] << 1; |
11 | } |
12 | if(ch[o][1]){ |
13 | cnt[o] += cnt[ch[o][1]]; |
14 | xorv[o] ^= (xorv[ch[o][1]] << 1) | (cnt[ch[o][1]] & 1); |
15 | } |
16 | } |
17 | int mknode(){ |
18 | ++tot; |
19 | ch[tot][0] = ch[tot][1] = 0; cnt[tot] = 0; |
20 | return tot; |
21 | } |
22 | void insert(int &o, int x, int dep){ |
23 | if(!o) o = mknode(); |
24 | if(dep > D){ |
25 | cnt[o]++; |
26 | return; |
27 | } |
28 | insert(ch[o][x & 1], x >> 1, dep + 1); |
29 | maintain(o); |
30 | } |
31 | void erase(int o, int x, int dep){ |
32 | if(dep > D){ |
33 | cnt[o]--; |
34 | return; |
35 | } |
36 | erase(ch[o][x & 1], x >> 1, dep + 1); |
37 | maintain(o); |
38 | } |
39 | void addall(int o){ |
40 | swap(ch[o][0], ch[o][1]); |
41 | if(ch[o][0]) addall(ch[o][0]); |
42 | maintain(o); |
43 | } |
44 | } |
AC自动机
判断有几个模式串在文本串t中出现
1 | const int N = 1E6 + 7; |
2 | const int S = 26; |
3 | int tr[N][S], ex[N], fail[N], tot; |
4 | void insert(const char* s){ |
5 | int u = 0; |
6 | for(int i = 0; s[i]; i++){ |
7 | int v = s[i] - 'a'; |
8 | if(!tr[u][v]) tr[u][v] = ++tot; |
9 | u = tr[u][v]; |
10 | } |
11 | ex[u]++; |
12 | } |
13 | queue<int> q; |
14 | void build(){ |
15 | for(int i = 0; i < S; i++) if(tr[0][i]) q.push(tr[0][i]); |
16 | while(!q.empty()){ |
17 | int u = q.front(); q.pop(); |
18 | for(int i = 0; i < S; i++){ |
19 | if(tr[u][i]){ |
20 | fail[tr[u][i]] = tr[fail[u]][i]; |
21 | q.push(tr[u][i]); |
22 | } |
23 | else tr[u][i] = tr[fail[u]][i]; |
24 | } |
25 | } |
26 | } |
27 | int query(const char* t){ |
28 | int res = 0; |
29 | for(int i = 0, u = 0; t[i]; i++){ |
30 | int v = t[i] - 'a'; |
31 | u = tr[u][v]; |
32 | for(int j = u; j && ~ex[j]; j = fail[j]){ |
33 | res += ex[j]; ex[j] = -1; |
34 | } |
35 | } |
36 | return res; |
37 | } |
判断模式串在文本串出现次数
1 | const int N = 1005; |
2 | const int S = 26; |
3 | const int L = 55; |
4 | const int W = N * L; |
5 | const int M = 2e6 + 7; |
6 | |
7 | int tr[W][S], tot, fail[W], pos[N]; |
8 | void insert(const char* s, int x){ |
9 | int u = 0; |
10 | for(int i = 0; s[i]; i++){ |
11 | int v = s[i] - 'A'; |
12 | if(!tr[u][v]) tr[u][v] = ++tot; |
13 | u = tr[u][v]; |
14 | } |
15 | pos[x] = u; |
16 | } |
17 | queue<int> q; |
18 | vector<vector<int> > e; |
19 | void build(){ |
20 | for(int i = 0; i < S; i++) if(tr[0][i]) q.push(tr[0][i]); |
21 | while(!q.empty()){ |
22 | int u = q.front(); q.pop(); |
23 | e[fail[u]].push_back(u); |
24 | for(int i = 0; i < S; i++){ |
25 | if(tr[u][i]){ |
26 | fail[tr[u][i]] = tr[fail[u]][i]; |
27 | q.push(tr[u][i]); |
28 | } |
29 | else tr[u][i] = tr[fail[u]][i]; |
30 | } |
31 | } |
32 | } |
33 | int cnt[W]; |
34 | void query(const char* t){ |
35 | int u = 0; |
36 | for(int i = 0; t[i]; i++){ |
37 | if(t[i] < 'A' || t[i] > 'Z'){ |
38 | u = 0; continue; // 题目保证模式串中只含大写字母 |
39 | } |
40 | u = tr[u][t[i] - 'A']; |
41 | cnt[u]++; |
42 | } |
43 | } |
44 | void dfs(int x){ |
45 | for(auto v: e[x]){ |
46 | dfs(v); |
47 | cnt[x] += cnt[v]; |
48 | } |
49 | } |
后缀数组
倍增+sort $O(n \log^2n)$
1 | const int N= 1e6 + 8; |
2 | int sa[N], rk[N << 1], oldrk[N << 1]; |
3 | int w; |
4 | void sa_sort(const char* s){ |
5 | int n = strlen(s + 1); |
6 | for(int i = 1; i <= n; i++) sa[i] = i, rk[i] = s[i]; |
7 | for(w = 1; w < n; w <<= 1){ |
8 | sort(sa + 1, sa + n + 1, [](int x, int y){ |
9 | return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y]; |
10 | }); |
11 | memcpy(oldrk, rk, sizeof(oldrk)); |
12 | for(int p = 0, i = 1; i <= n; i++){ |
13 | if(oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]){ |
14 | rk[sa[i]] = p; |
15 | } |
16 | else rk[sa[i]] = ++p; |
17 | } |
18 | } |
19 | for(int i = 1; i <= n; i++) printf(i == n ? "%d\n":"%d ", sa[i]); |
20 | } |
计数排序版本 $O(n\log n)$
1 | // 多组数据时要注意memset和memecpy复杂度会假！！！ |
2 | const int N = 1E6 + 7; |
3 | const int S = 128; |
4 | int rk[N], oldrk[N << 1], sa[N], cnt[N], id[N], px[N]; |
5 | int height[N]; |
6 | // px[i] = rk[id[i]] |
7 | bool cmp(int x, int y, int w){ |
8 | return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w]; |
9 | } |
10 | void sa_sort(const char* s){ |
11 | int i, w, p, m = S; |
12 | int n = strlen(s + 1); |
13 | for(i = 1; i <= n; i++) ++cnt[rk[i] = s[i]]; |
14 | for(i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; |
15 | for(i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i; |
16 | for(w = 1;; w <<= 1, m = p){ |
17 | for(p = 0, i = n; i > n - w; i--) id[++p] = i; |
18 | for(i = 1; i <= n; i++) if(sa[i] > w) id[++p] = sa[i] - w; |
19 | memset(cnt, 0, sizeof(cnt)); |
20 | for(i = 1; i <= n; i++) ++cnt[px[i] = rk[id[i]]]; |
21 | for(i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; |
22 | for(i = n; i >= 1; i--) sa[cnt[px[i]]--] = id[i]; |
23 | memcpy(oldrk, rk, sizeof(rk)); |
24 | for(p = 0, i = 1; i <= n; i++) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p; |
25 | if(p == n){ |
26 | for(i = 1; i <= n; i++) sa[rk[i]] = i; |
27 | break; |
28 | } |
29 | } |
30 | |
31 | //利用height[rk[i+1]]>=height[rk[i]]-1 |
32 | //O(n) |
33 | for(int i = 1, k = 0;i <= n; i++){ |
34 | if(k) k--; |
35 | while(rk[i] > 1 && s[i + k] == s[sa[rk[i] - 1] + k]) k++; |
36 | height[rk[i]] = k; |
37 | } |
38 | } |
王老师模板
1 | |
2 | //sa:排名对应的前缀, rk:前缀的排名, tp:第二关键字排名对应的前缀, tax:排名对应的个数 |
3 | //height:排名i与i-1后缀的LCP(最长公共前缀) |
4 | int sa[MAXN],r1[MAXN],r2[MAXN],tax[MAXN],height[MAXN]; |
5 | int *rk=r1,*tp=r2; |
6 | char s[MAXN]; |
7 | |
8 | void rsort(int n,int m){ |
9 | memset(tax,0,(m+1)*sizeof(tax[0])); |
10 | for(int i=1;i<=n;i++) tax[rk[i]]++;//当前排名装桶 |
11 | for(int i=1;i<=m;i++) tax[i]+=tax[i-1];//计算桶的名次 |
12 | for(int i=n;i>=1;i--) sa[tax[rk[tp[i]]]--]=tp[i];//按照第二关键字降序，分配排名。 |
13 | } |
14 | void get_sa(char* s){ |
15 | //O(nlogn) |
16 | int n=strlen(s+1), m=0; |
17 | for(int i=1;i<=n;i++) |
18 | m=max(m,rk[i]=s[i]),tp[i]=i; |
19 | rsort(n,m); |
20 | for(int k=1,p=0;p<n;k<<=1,m=p){ |
21 | p=0; |
22 | //重制第二关键字 |
23 | for(int i=n-k+1;i<=n;i++) tp[++p]=i; //后续为空，排前面 |
24 | for(int i=1;i<=n;i++) if(sa[i]>k) tp[++p]=sa[i]-k; //按照第一关键字排第二关键字 |
25 | |
26 | rsort(n,m); |
27 | |
28 | swap(tp,rk); |
29 | rk[sa[1]]=p=1; |
30 | for(int i=2;i<=n;i++){ |
31 | rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p; |
32 | } |
33 | } |
34 | |
35 | //利用height[rk[i+1]]>=height[rk[i]]-1 |
36 | //O(n) |
37 | for(int i=1,k=0;i<=n;i++){ |
38 | if(k) k--; |
39 | while(rk[i]>1 && s[i+k]==s[sa[rk[i]-1]+k]) k++; |
40 | height[rk[i]]=k; |
41 | } |
42 | } |