【模版】一些字符串函数（仅代码）

发表于 阅读次数：

KMP（前缀函数）

定义：

\(bd_i\)：对于字符串 \(s\)，使 \(s_{0 \dots bd_{i}-1} = s_{i-bd_{i}+1 \dots i}\) 成立的最大值。

代码：

1
2
3
4
5
6
for (int i = 1; i < n; i++) {
	int j = bd[i-1];
	while (j && s[i] != s[j]) j = bd[j-1];
	if (s[i] == s[j]) j++;
	bd[i] = j;
}

字符串下标从 \(0\) 开始。

exKMP（Z函数）

定义：

\(z_i\)：字符串 \(s\) 与 \(s\) 以 \(i\) 为起始的后缀的最长公共前缀。

代码：

1
2
3
4
5
6
7
8
9
10
11
void getZ(const string& s, int z[]) {
    int n = s.size(), l = 0, r = -1;
    for (int i = 1; i < n; i++) {
        int k = (i > r) ? 0 : min(z[i-l], r-i+1);
        while (i+k < n && s[i+k] == s[k]) k++;
        z[i] = k;
        if (i+k-1 > r)
            l = i, r = i+k-1;
    }
    z[0] = n;
}

字符串下标从 \(0\) 开始。

Manacher

定义：

\(d_{1i}\)：以 \(i\) 为中心的奇回文串的最大半径。

\(d_{2i}\)：以 \(i-1\) 和 \(i\) 为中心的偶回文串的最大半径。

\(len\)：所求的答案之一，\(s\) 中最长回文串的长度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n = s.size();
int len = 0, nl = 0, nr = 0;
for (int i = 0, l = 0, r = -1; i < n; i++) {
	int k = (i>r) ? 1 : min(d1[l+r-i], r-i+1);
	while (0<=i-k && i+k<n && s[i-k]==s[i+k]) k++;
	d1[i] = k--;
	if (i+k>r)
		l = i-k, r = i+k;
	if (r-l+1 > len)
		len = r-l+1, nl = l, nr = r;
}
for (int i = 0, l = 0, r = -1; i < n; i++) {
  	int k = (i>r) ? 0 : min(d2[l+r-i+1], r-i+1);
  	while (0<=i-k-1 && i+k<n && s[i-k-1]==s[i+k])k++;
  	d2[i] = k--;
  	if (i+k>r)
   		l = i-k-1, r = i+k;
   	if (r-l+1 > len)
   		len = r-l+1, nl = l, nr = r;
}

字符串下标从 \(0\) 开始。