String
最长公共子串
$dp[i][j]$表示前 $i$ 个 $a$ 和前 $j$ 个 $b$ 组成的最长公共子串长度
最长公共子序列
$dp[i][j]$表示的前 $i$ 个 $a$ 和前 $j$ 个 $b$ 组成最长公共子序列长度
最长上升公共子序列
$dp[i][j]$ 表示前 $i$ 个 $a$ 和前 $j$ 个 $b$ 组成的以 $b[j]$ 结尾的最长上升子公共子序列长度
最长回文子序列
最长回文子串
- Manacher 算法
1 | char s[N]; |
回文自动机
功能：
- 求串 S 前缀 0~i 内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同）
- 求串 S 内每一个本质不同回文串出现的次数
- 求串 S 内回文串的个数（其实就是1和2结合起来）
- 求以下标 i 结尾的回文串的个数
1 | const int C = 26; |
字符串哈希
1 | ull P = 1313131; |
序列自动机
$nxt[i][j]$ 表示在原串 $s$ (从 $1$ 开始) 第 $i$ 位后面的第一个 $j$ 出现的位置，设串长为 $n$ ,字符集大小为 $a$，预处理时间复杂度为 $O(n*a)$
1 | for(int i=n;i;i--){ |
求子序列个数
1 | int dfs(int x){ |
求回文子序列或两个串的公共子序列个数等
1 | int dfs(int x,int y){//表示目前字符是串1的第x位，串2的第y位 |
求一个串的回文子序列个数
对原串和反串构造 $next$ 数组, 然后 $dfs$ , 对回文分奇偶, $dfs$ 过程中应该保证 $x+y<=n+1$ , 若 $x+y=n+1$ 为奇串, 否则为偶串. $dfs $ 到一个偶串时，可能会有奇串被漏掉(如自动机只能找到 $abba$，却忽略了 $aba$) 因此，我们考虑手动加上被忽略的奇串，同时注意已经找到的奇串不能再加一次（如 $ababa$），只要特判一下就可以了，代码如下。
1 | int dfs(int x,int y){ |
给定三个串 $A,B.C$, 求一个最长的 $A,B$ 的公共子序列 $S$, 要求 $C$ 是 $S$ 的子序列
再加一个参数 $z$ 表示当前字符是 $C$ 的第 $z$ 位, 但这么做显然是错的，因为匹配过程中 $C$ 的某些字符可能会被跳过, 所以需要对 $next$ 做一些修改
1 | for(int i=1;i<=26;i++) nextc[n][i]=n;//字符集为26个字母,C长度为n |
KMP
1 | int Next[N];// Next[i] 为满足 p[i-z,...,i-1]=p[0,...,z-1] 的最大 z 值(就是 p 的自身匹配) |
扩展KMP
1 | int Extend[N], Next[N]; |
字典树
数组实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23int ch[N][30], tot, val[N];
void Insert(char *s) {
int root = 0, len = (int)strlen(s);
for0(i, len) {
int c = s[i] - 'a';
if (!ch[root][c]) {
mem0(ch[tot + 1]); //使用的时候才用memset开辟空间可以减低空间复杂度
ch[root][c] = ++tot;
}
root = ch[root][c];
val[root]++;
}
}
int Query(char *s) {
int root = 0;
int len = (int)strlen(s);
for0(i, len) {
int c = s[i] - 'a';
if (!ch[root][c]) return 0;
root = ch[root][c];
}
return val[root];
}指针实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37const int MAX = 26;
struct Trie {
Trie *Next[MAX];
int count;
Trie() {
count = 1;
memset(Next, NULL, sizeof(Next));
}
} * root;
void Insert(string s) {
Trie *tmpRoot = root, *tmp;
for0(i, s.size()) {
if (tmpRoot->Next[s[i] - 'a'] == NULL) {
tmp = new Trie;
tmpRoot->Next[s[i] - 'a'] = tmp;
tmpRoot = tmp;
} else {
tmpRoot = tmpRoot->Next[s[i] - 'a'];
tmpRoot->count++;
}
}
}
int Query(string s) {
Trie *tmpRoot = root;
for0(i, s.size()) {
if (tmpRoot->Next[s[i] - 'a'] == NULL) return 0;
tmpRoot = tmpRoot->Next[s[i] - 'a'];
}
return tmpRoot->count;
}
void Free(Trie *T) {
if (T == NULL) return;
for (int i = 0; i < MAX; ++i) {
if (T->Next[i]) Free(T->Next[i]);
}
delete (T);
}
AC自动机
多模匹配算法，多个模式串，在文本串中找出拥有的模式串数，求 $fail$ : 直接与根节点相连的节点来说，如果这些节点失配，他们的Fail指针直接指向root即可;假设当前节点为father，其孩子节点记为child。求child的Fail
指针时，首先我们要找到其father的Fail指针所指向的节点,假如是t的话，我们就要看t的孩子中有没有和child节点所表示的字母相同的节点，如果有的话，
这个节点就是child的fail指针，如果发现没有，则需要找father->fail->fail这个节点，然后重复上面过程，如果一直找都找不到，则child的Fail指针就要指向root。
数组实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56struct Trie {
int next[N][26], fail[N], end[N], root, L; // N的范围为所有pattern的字符数
int newnode() {
for (int i = 0; i < 26; i++) next[L][i] = -1;
end[L++] = 0;
return L - 1;
}
void init() {
L = 0;
root = newnode();
}
void insert(char buf[]) {
int len = (int)strlen(buf), now = root;
for (int i = 0; i < len; i++) {
if (next[now][buf[i] - 'a'] == -1)next[now][buf[i] - 'a'] = newnode();
now = next[now][buf[i] - 'a'];
}
end[now]++;
}
void build() {
queue<int> Q;
fail[root] = root;
for (int i = 0; i < 26; i++) {
if (next[root][i] == -1)next[root][i] = root;
else {
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
}
while (!Q.empty()) {
int now = Q.front();
Q.pop();
for (int i = 0; i < 26; i++) {
if (next[now][i] == -1)next[now][i] = next[fail[now]][i];
else {
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
int query(char buf[]) {
int len = (int)strlen(buf), now = root, res = 0;
for (int i = 0; i < len; i++) {
now = next[now][buf[i] - 'a'];
int temp = now;
while (temp != root) {
res += end[temp];
end[temp] = 0;
temp = fail[temp];
}
}
return res;
}
};
char *pattern, *str;指针实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47const int MAX = 26;
int tot;
vii failTree[N];
struct Node {
int id;
Node *Next[MAX];
Node *Fail; //失配指针,类似next数组,最大的next是和自身比较,fail是和其它匹配串比较
Node() {
memset(Next, 0, sizeof(Next));
Fail = 0;
id=tot++;
}
} * root;
int Insert(char s[]) {
Node *p = root;
int len=strlen(s);
for(int i=0;i< len;i++) {
int c = s[i] - 'a';
if (p->Next[c] == NULL) {
Node *newnode = new Node;
p->Next[c] = newnode;
p = newnode;
} else p = p->Next[c];
}
return p->id;
}
void BuildFail() {
queue<Node *> que;
root->Fail=root;
for(int i=0;i<26;i++){
if(root->Next[i]){
root->Next[i]->Fail=root;
que.push(root->Next[i]);
}else root->Next[i]=root;
}
while (!que.empty()) {
Node *p = que.front();
que.pop();
failTree[p->Fail->id].pu_b(p->id);
for(int i=0;i<26;i++){
if(p->Next[i]){
p->Next[i]->Fail=p->Fail->Next[i];
que.push(p->Next[i]);
}else p->Next[i]=p->Fail->Next[i];
}
}
}
后缀数组
倍增算法 $O(n*logn)$
- 待排序数组长度为n, 放在[0,n-1]中，在最后面补一个0，需要保证每个元素大于零
- srank[0,n-1]为有效值，srank[n]必定为0无效值,srank[i]保存Suffix(i)在所有后缀中从小到大排列的“名次”。
- sa[1,n]为有效值，sa[0] 必定为n是无效值, sa[i]表示排名第i的起点为sa[i];
height[2,n]为有效值,suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39int t1[N],t2[N],c[N],srank[N],height[N],sa[N];
bool cmp(int *r,int a,int b,int l){
return r[a] == r[b] && r[a+l] == r[b+l];
}
void DA(int str[],int n,int m){//m为字符串中的最大值+1
n++;
int i, j, p, *x = t1, *y = t2;
//第一轮基数排序，如果s 的最大值很大，可改为快速排序
for(i = 0;i < m;i++)c[i] = 0;
for(i = 0;i < n;i++)c[x[i] = str[i]]++;
for(i = 1;i < m;i++)c[i] += c[i-1];
for(i = n-1;i >= 0;i--)sa[--c[x[i]]] = i;
for(j = 1;j <= n; j <<= 1){
p = 0;
//直接利用sa 数组排序第二关键字
for(i = n-j; i < n; i++)y[p++] = i;//后面的j 个数第二关键字为空的最小
for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j;//这样数组y保存的就是按照第二关键字排序的结果
//基数排序第一关键字
for(i = 0; i < m; i++)c[i] = 0;
for(i = 0; i < n; i++)c[x[y[i]]]++;
for(i = 1; i < m;i++)c[i] += c[i-1];
for(i = n-1; i >= 0;i--)sa[--c[x[y[i]]]] = y[i];//根据sa 和x 数组计算新的x 数组
swap(x,y);
p = 1; x[sa[0]] = 0;
for(i = 1;i < n;i++)x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
if(p >= n)break;
m = p;//下次基数排序的最大值
}
int k = 0;
n--;
for(i = 0;i <= n;i++)srank[sa[i]] = i;
for(i = 0;i < n;i++){
if(k)k--;
j = sa[srank[i]-1];
while(str[i+k] == str[j+k])k++;
height[srank[i]] = k;
}
}
int r[N];
DC3算法 $O(n)$
- 所有的相关数组都要开三倍
- 待排序数组长度为n, 放在[0,n-1]中，在最后面补一个0
- srank[0,n-1]为有效值，srank[n]必定为0无效值,srank[i]保存Suffix(i)在所有后缀中从小到大排列的“名次”
- sa[1,n]为有效值，sa[0] 必定为n是无效值, sa[i]表示排名第i的起点为sa[i];
height[2,n]为有效值,suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int wa[N],wb[N],wv[N],wss[N],sa[N],srank[N],height[N];
int c0(int *r,int a,int b){
return r[a] == r[b] && r[a+1] == r[b+1] && r[a+2] == r[b+2];
}
int c12(int k,int *r,int a,int b){
if(k == 2) return r[a] < r[b] || ( r[a] == r[b] && c12(1,r,a+1,b+1) );
else return r[a] < r[b] || ( r[a] == r[b] && wv[a+1] < wv[b+1]);
}
void sort(int *r,int *a,int *b,int n,int m){
int i;
for(i = 0;i < n;i++)wv[i] = r[a[i]];
for(i = 0;i < m;i++)wss[i] = 0;
for(i = 0;i < n;i++)wss[wv[i]]++;
for(i = 1;i < m;i++)wss[i]+=wss[i-1];
for(i = n-1;i >= 0;i--)b[--wss[wv[i]]] = a[i];
}
void dc3(int *r,int *sa,int n,int m){
int i, j, *rn = r + n;
int *san = sa + n, ta = 0, tb = (n+1)/3, tbc = 0, p;
r[n] = r[n+1] = 0;
for(i = 0;i < n;i++)if(i %3 != 0)wa[tbc++] = i;
sort(r + 2, wa, wb, tbc, m);
sort(r + 1, wb, wa, tbc, m);
sort(r, wa, wb, tbc, m);
for(p = 1, rn[F(wb[0])] = 0, i = 1;i < tbc;i++)rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p - 1 : p++;
if(p < tbc)dc3(rn,san,tbc,p);
else for(i = 0;i < tbc;i++)san[rn[i]] = i;
for(i = 0;i < tbc;i++) if(san[i] < tb)wb[ta++] = san[i] * 3;
if(n % 3 == 1)wb[ta++] = n - 1;
sort(r, wb, wa, ta, m);
for(i = 0;i < tbc;i++)wv[wb[i] = G(san[i])] = i;
for(i = 0, j = 0, p = 0;i < ta && j < tbc;p++)sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
for(;i < ta;p++)sa[p] = wa[i++];
for(;j < tbc;p++)sa[p] = wb[j++];
}
void DA(int str[],int n,int m){
for(int i = n;i < n*3;i++)str[i] = 0;
dc3(str, sa, n+1, m);
int i,j,k = 0;
for(i = 0;i <= n;i++)srank[sa[i]] = i;
for(i = 0;i < n; i++){
if(k) k--;
j = sa[srank[i]-1];
while(str[i+k] == str[j+k]) k++;
height[srank[i]] = k;
}
}
string s;
int r[N];
应用
- 本质不同子串
后缀自动机
模板
1 | const int CHAR = 26; |
广义后缀自动机
广义后缀自动机就是把所有串放到一个后缀自动机里一起处理。
每次往后缀自动机里添加一个字符串后，将 $last$ 重新挪到 $1$ 号节点上，再添加下一个字符串即可。添加字符串 $S_i$ 时，添加出来的所有实节点及它们在 $pre$ 树上的祖先们代表的子串，都在字符串 $S_i$ 中出现过。于是我们可以利用一些类似于 $set$ 启发式合并的方法，来得到每个节点在多少个字符串中出现过。
应用
1 | int t1[N],t2[N],c[N],srank[N],height[N],sa[N]; |