KMP与哈希专题笔记与题解

KMP与前缀函数

前缀函数的定义

给定一个长度为\(n\)的字符串\(s\)(下标从\(1\)开始),约定\(s[l,r]\)表示从\(s[l]\)开始到\(s[r]\)结束的字符串,\(s\)前缀函数 被定义为一个长度为\(n\)的数组\(\pi\)。其中\(\pi[i]\)为既是字符串\(s[1,i]\)的前缀同时也是该字符串的后缀的 最长 真前缀字符串(真前缀字符串指不为这个字符串本身的前缀字符串)长度。

换言之,\(\pi[i]\)只关心字符串\(s[1,i]\),且若\(\pi[i]=j\),则有字符串\(s[1,j]=s[i-j+1,i]\)。抽象的数学定义即为:\(π(i)=max\{j|s[1,j]=s[i−j+1,i], j≤i\}\)

求解与优化

根据定义可以得出两个结论来帮助我们快速求解\(\pi\)函数。

第一个性质

\(\pi[i+1] \le \pi [i] + 1\)

证明这个结论,我们不妨利用反证法。

假设\(\exists i \in [1,n)\),满足\(\pi[i+1]>\pi[i]+1\)

依据\(\pi[i+1]\)的定义,有\(s[1,j] = s[i-j+2,i+1]\),对于等式两边的字符串同时删去最右边的一个字符,有\(s[1, \pi[i+1]-1]=s[i-\pi[i+1]+2,i]\)

这个等式表明这两个相等的字符串既是字符串\(s[1,i]\)的前缀同时也是该字符串的后缀,且根据假设,这个字符串的长度大于我们假设中的\(\pi[i]\),与\(\pi[i]\)是最长真前缀字符串的定义矛盾,所以假设不成立。

第二个性质

观察第一个性质,考虑不等式的等号可以何时取得,可以证明的是:

\(s[i+1]=s[\pi[i]+1]\),则有\(\pi[i+1]=\pi[i]+1\)

这个结论可以比较形象地去理解:\(s[1,\pi[i]]=s[i-\pi[i]+1,i]\),两个字符串右边界同时囊括新的元素,左式加入的是\(s[\pi[i]+1]\),右式加入的是\(s[i+1]\),由于性质中条件的存在,所以等式仍然成立\(s[1,\pi[i]+1]=s[i-\pi[i]+1,i+1]\)所以我们得到了一个真前缀字符串,根据定义,此时是最优的,所以结论得证。

最终算法

参照这两个性质,我们能够推导出最终的算法。由于第二个性质是递推的关系,所以我们可以利用这个重新描述一下\(\pi[i+1]\)的定义,让其更便于计算。

找到最大的\(j\),使得\(s[1, j]=s[i-j+1,i]\)\(s[i]=s[j+1]\),此时由第二个性质可得\(\pi[i+1]=j+1\)

求解这个定义式,考虑两种情况。1)两个字符相等,即第二个条件满足,直接赋值\(\pi[i+1]=\pi[i]+1\),求解完成。2)条件二不满足,则需要考虑尝试更短的字符串。为了加速,我们希望直接移动到最长的长度\(j'<\pi[i]\),使得在位置\(i\)前缀性质仍得以保持,而后我们需要比较\(s[i]=s[j'+1]\)是否成立,如此反复。需要注意的是,定义中的\(j\)\(\pi[i]\)当且仅当\(s[i]=s[j+1]\)时相等。

依据此,写出以下求解函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
void getpi(char* s, int pi[])
{
int n = strlen(s + 1);
for(int i = 2; i <= n; i++)
{
int j = pi[i - 1];
while(s[i]!=s[j+1] && j)
j = pi[j];
if(s[j + 1] == s[i])
j++;
pi[i] = j;
}
}

KMP与前缀函数应用

KMP算法

描述

给定主串\(s\)以及模式串\(p\),询问模式串在主串中出现的全部位置。例如:主串ABABA,模式串ABA,分别出现在\([1,3]\)\([3,5]\)的位置。

题解

暴力算法是枚举主串从\(i\)开始出现模式串,然后进行验证,时间复杂度为\(O(nm)\)\(n,m\)是主串和模式串的长度。利用前缀函数可以优化枚举的过程,根据前缀函数的定义,一旦验证失败,我们就向后移动模式串,让前缀保持匹配,这样可以避免重新从头开始匹配模式串。详细解析可以参考这里

另一种思考方式是,将主串拼接到模式串后面,那么这个新串的长度为\(m\)的前缀就是模式串,对这个新的字符串求前缀函数,若\(\pi[i]=m\),则出现一次模式串完全匹配。在两串中间添加的分隔符是为了保证新串的前缀函数不会大于模式串的长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int M = 200010;
char s[M], p[M];
int n, m, ne[M];
int main()
{
scanf("%d%s%d%s", &n, p + 1, &m, s);
p[n + 1] = '#';
strcat(p + 1, s);
int len = strlen(p + 1);
for (int i = 2; i <= len; i++)
{
int j = ne[i - 1];
while (j && p[j + 1] != p[i])
j = ne[j];
if (p[j + 1] == p[i])
j++;
ne[i] = j;
if (ne[i] == n)
printf("%d ", i - n - n - 1);
}
return 0;
}

CF1137B-Camp schedule

描述

给定\(01\)字符串\(s\)\(t\),重新组合\(s\)内元素的位置,使得\(t\)能够尽可能多的在\(s\)中匹配,输出重新构造后的\(s\)

题解

朴素想法是先统计\(s\)内的\(0,1\)数量\(cnt[0],cnt[1]\),将\(t\)尽可能多的循环输出,直至无法构成\(t\)后输出剩余的\(0\)\(1\),但是由于匹配是可以允许又重叠部分的,如\(101\)\(10101\)中匹配了两次。考虑贪心的思想,我们要想匹配尽可能多,就要让匹配之间的重叠部分尽可能大,而匹配之间存在的最大重叠就是\(t\)的最长公共前后缀,随后想到\(KMP\)算法。

我们首先判断\(s\)的元素能否构造出一个\(t\),不能就直接返回\(s\),可以就令\(ans=t\),而后从\(t\)的第二位开始匹配\(t\)

我们记录当前\(t\)匹配到的位置\(pos\),此时如果还有该位置需要的元素就令\(ans+=t[pos],cnt[t[pos]]--\)。如果匹配到了\(t\)的末尾,令\(pos=ne[pos]\),表示重新开始新一轮匹配。循环直到\(s\)内元素用完或者无法继续匹配了,将剩余的元素加到\(ans\)后面即可。

代码

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
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int N = 500010;
char s[N], t[N];
int ne[N];
string res;
int cnt[2];
int main()
{
scanf("%s%s", s + 1, t + 1);
int ls, lt;
ls = strlen(s + 1), lt = strlen(t + 1);
if (ls < lt)
{
printf("%s\n", s + 1);
return 0;
}
for (int i = 1; i <= ls; i++)
cnt[s[i] - '0']++;
for (int i = 2; i <= lt; i++)
{
int j = ne[i - 1];
while (t[i] != t[j + 1] && j)
j = ne[j];
if (t[i] == t[j + 1])
++j;
ne[i] = j;
}
int len = 1;
while (cnt[0] > 0 && cnt[1] > 0)
{
if (t[len] == '0')
{
if (cnt[0] > 0)
{
res += '0';
cnt[0]--;
}
else
break;
}
else
{
if (cnt[1] > 0)
{
res += '1';
cnt[1]--;
}
else
break;
}
len++;
if (len == lt + 1)
len = ne[lt] + 1;
}
while (cnt[0]--)
res += '0';
while (cnt[1]--)
res += '1';
cout << res << endl;
return 0;
}

CF535D-Tavas and Malekas

描述

已知字符串 \(p\) 是一个长度为 \(n\) 的字符串的子串,给定 \(p\) 在原串中匹配的 \(m\) 个位置,求解原字符串可能有多少种情况。

题解

若无条件限制,总可能方案数是 \(26^n\) ,根据题意,我们统计在满足条件后原串中已经固定了字符的数量 \(cnt\) ,答案就是 \(26^{n-cnt}\) 中方案数。

考虑暴力枚举,时间复杂度为 \(\mathcal{O}(n^2)\) 会TLE,所以使用 \(KMP\) 内前缀数组的思想进行优化。

在枚举 \(m\) 个位置的时候考虑两种情形,1)枚举两个位置中间的长度大于等于 \(|p|\) 的长度,那么直接使这 \(|p|\) 个位置固定,2)枚举两个位置中间的长度小于 \(|p|\) ,则考虑利用前缀数组将字符串 \(p\) 当前填充的位置向后移动,若无法通过移动满足条件就输出0,否则就将这中间一段也加进 \(cnt\) ,最终复杂度 \(\mathcal{O}(n+m)\)

代码

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
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m, x[N], ne[N], cnt;
char p[N];

long long qmi(long long a, long long b, long long m)
{
a %= m;
long long res = 1;
while (b > 0)
{
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}

int main()
{
cin >> n >> m >> p + 1;
for (int i = 1; i <= m; i++)
cin >> x[i];
int len = strlen(p + 1);
for (int i = 2; i <= len; i++)
{
int j = ne[i - 1];
while (p[j + 1] != p[i] && j)
j = ne[j];
if (p[j + 1] == p[i])
++j;
ne[i] = j;
}
sort(x + 1, x + m + 1);
for (int i = 1; i <= m; i++)
{
if (i == 1 || x[i] - x[i - 1] >= len)
{
cnt += len;
}
else
{
bool flag = false;
int j = ne[len], l = x[i - 1] + len - x[i];
while (j)
{
if (j == l)
{
flag = true;
cnt += len - l;
break;
}
j = ne[j];
}
if (!flag)
{
puts("0");
return 0;
}
}
}
printf("%lld\n", qmi(26, n - cnt, 1000000007));
}

CF149E-Martian String

描述

给定字符串\(s\)和若干个字符串\(p\),求满足\(\exists a,b,c,d,(1 \le a \le b \le c \le d \le |s|)\),使得\(s[a,b]+s[c,d]=p\)\(p\)串个数。

题解

对于每一个\(p\)串进行判断,首先找到\(p\)的所有真前缀在\(s\)中的第一次匹配,记录每个匹配内最后一个字母的位置\(pre[i]\)\(i\)表示当前前缀的长度),如果无法匹配则默认为\(1\)。然后将\(s,p\)都反转过来,找到所有当前的\(p\)的真前缀的第一次匹配,比较此时第一个字母的位置和\(pre[len - i]\),如果合法,那么判断该串满足条件,如果所有真前缀都不满足,则不满足条件。

之所以记录第一次匹配是为了尽可能的去满足\(s[a,b],s[c,d]\)两子串不重叠的条件,如果第一次都要产生重叠,那么接下来的就更不可能了。

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1010;
char s[N], p[M], sr[N], pr[M];
int pre[M], suf[M], ne[M];
int res = 0;

int main()
{
scanf("%s", s + 1);
int m;
scanf("%d", &m);
int ls = strlen(s + 1);

for (int i = ls, j = 1; i > 0; i--)
sr[j++] = s[i];
while (m--)
{
scanf("%s", p + 1);
int len = strlen(p + 1);
if (len < 2)
continue;

memset(pre, 0, sizeof pre);
memset(suf, 0, sizeof suf);
int j = 0;

for (int i = 2; i <= len; i++)
{
while (j && p[i] != p[j + 1])
j = ne[j];

if (p[i] == p[j + 1])
j++;

ne[i] = j;
}
j = 0;
for (int i = 1; i <= ls; i++)
{

while (j && s[i] != p[j + 1])
j = ne[j];

if (p[j + 1] == s[i])
j++;

if (!pre[j])

pre[j] = i;
if (j == len)
break;
}

for (int i = len, k = 1; i > 0; i--)
pr[k++] = p[i];
memset(ne, 0, sizeof ne);

j = 0;
for (int i = 2; i <= len; i++)
{

while (j && pr[i] != pr[j + 1])
j = ne[j];

if (pr[i] == pr[j + 1])
j++;

ne[i] = j;
}
j = 0;
for (int i = 1; i <= ls; i++)
{

while (j && sr[i] != pr[j + 1])
j = ne[j];

if (pr[j + 1] == sr[i])
j++;

if (!suf[j])

suf[j] = i;
if (j == len)
break;
}

for (int i = 1; i < len; i++)
{
if (pre[i] && suf[len - i] && pre[i] < ls - suf[len - i] + 1)
{
res++;
break;
}
}
}
printf("%d\n", res);
return 0;
}

字符串哈希

哈希函数

Hash 的核心思想在于,将输入映射到一个值域较小、可以方便比较的范围。

我们定义一个把字符串映射到整数的函数 ,这个\(f\)称为是Hash函数。通过这个函数,我们可以快捷的比较两个字符串是否相等。

我们通常使用多项式哈希的方法,即\(f(s) = \sum s[i] \times b^i (mod M)\)

从这个函数表达式可以看出,两个字符串存在不相等却哈希值相等的情况,哈希函数的判断是一个必要条件,但是我们可以通过恰当地选取\(b,M\)和多次哈希来尽可能降低冲突率。

哈希函数的实现

通常面对多次询问子串哈希的情况,我们可以先预处理出每个前缀的哈希值。

\(f_i(s)\)表示\(f(s[1,i])\),那么\(f(s[l,r]) = \frac {f_r(s) - f_{l-1}(s)} {b^{l-1}}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 10010, b = 10, M = 1e9 + 9;
char s[N];
int h[N], p[N] = {1};
void init()
{
int n = strlen(s + 1);
for(int i = 1; i <= n; i++)
{
h[i] = (h[i - 1] * b % M + s[i]) % M;
p[i] = p[i - 1] * b % M;
}
}
int gethash(int l, int r)
{
return ((h[r] - h[l - 1] * p[r - l + 1]) % M + M) % M;
}

哈希的应用

CF898F-Restoring the Expression

描述

在数字串\(s\)中插入一个加号一个等号,使算式成立,输出成立的等式。

题解

考虑暴力+优化,直接枚举加号和等号的位置需要\(O(n^2)\)的复杂度,高精度加法需要\(O(n)\)的复杂度,总共是\(O(n^3)\)的复杂度,显然会TLE。所以考虑加法的性质和判断的方法。

  • 若右式是一个\(n\)位的数,那么左式至少有一个数为\(n\)\(n-1\)位,较长的数可以在加号左右两侧,因此\(2 \times 2 = 4\),对于每一个确定的等号的位置,加号共有4种可能的位置。
  • 在确定了加号和等号的位置后,通过哈希去判断左式和右式是否相等,因为判断的是必要条件,所以最好取较大而不常用的模数或者使用双哈希。

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010, ba = 10;
const ll mo = 19491001;
char s[N];
ll h[N], b[N] = {1}, ri;
int len, n;

ll gh(int x, int y)
{
return ((h[y] - h[x - 1] * b[y - x + 1]) % mo + mo) % mo;
}
bool ch(int x, int y)
{
if (x == 0 || (y - x != 1 && s[x + 1] == '0') || (y != n - 1 && s[y + 1] == '0'))
return false;
else
return true;
}
void print(int x, int y)
{
for (int i = 1; i <= x; i++)
printf("%c", s[i]);
putchar('+');
for (int i = x + 1; i <= y; i++)
printf("%c", s[i]);
putchar('=');
for (int i = y + 1; i <= n; i++)
printf("%c", s[i]);
}
int main()
{
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++)
{
h[i] = (h[i - 1] * ba % mo + s[i] - '0') % mo;
b[i] = b[i - 1] * ba % mo;
}
int nn = n - n / 3;
for (int i = n >> 1; i <= nn; i++)
{
if(i + i < n) continue;
ri = gh(i + 1, n), len = n - i;
if (ch(len, i) && (gh(1, len) + gh(len + 1, i)) % mo == ri)
{
print(len, i);
return 0;
}
if (ch(len - 1, i) && (gh(1, len - 1) + gh(len, i)) % mo == ri)
{
print(len - 1, i);
return 0;
}
if (ch(i - len, i) && (gh(1, i - len) + gh(i - len + 1, i)) % mo == ri)
{
print(i - len, i);
return 0;
}
if (ch(i - len + 1, i) && (gh(1, i - len + 1) + gh(i - len + 2, i)) % mo == ri)
{
print(i - len + 1, i);
return 0;
}
}
}

CF985F-Isomorphic Strings

描述

给定一个字符串\(s\),执行\(m\)次询问,每次询问判断\(s\)的两个子串是否同构。对于两个字符串同构的定义可以概括为:如果\(s\)中的字符可以被替换得到\(t\),那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

题解

一开始做这道题首先想到的是用两个map去完成。从前向后遍历字符串,如果是首次出现一个字母,就记录这个字母和对应位置上另一个字符串的字母,如果不是首次出现,就去判断这个字母对应的字母和存的字母是否相同。对于两个字符串各做一遍上述操作,如果没有产生矛盾,就判断为同构,否则不同同构。根据数据范围,考虑最糟糕的情况是\(m\)次询问全部是针对\(s\)整个串,最终最坏复杂度为\(O(nm)\),最终会TLE。

那么考虑正解,个人感觉这道题的正解从位运算绕一下理解更方便。首先,\(s\)只由26个小写英文字母组成,其次,我们只需要判断是否同构而不需要知道对于每次判断而言字母之间的映射关系。基于这两点,我们考虑这样一个做法:

对于26个字母,构造26个01串,对于每个字母,遍历\(s\),如果\(s[i]\)与该字母相同则为1,否则为0。而后,我们可以将这26个字符串转换成十进制的数。对于判断同构串时,构造的两组01串转化后,如果存在两个数对应相等,那么说明这两个数代表的字母的对应位置在两串中完全一致,也就是符合同构的条件。那么,我们只需要判断两组数是否完全相等就可以了。

但是,此时考虑到两组01串每个长度可以长达\(2 \times 10^5\),所以转换成十进制的数存不下,所以我们想到可以直接利用哈希去判断两组01串是否相等。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;
const ll mod = 1e9 + 7, B = 233;
ll h[26][N], p[N] = {1ll};
char S[N];
int main()
{
int n, m, x, y, l;
scanf("%d%d", &n, &m);
getchar();
scanf("%s", S + 1);
for (int i = 1; i <= n; i++)
p[i] = p[i - 1] * B % mod;
for (int i = 0; i < 26; i++)
{
for (int j = 1; j <= n; j++)
{
h[i][j] = (h[i][j - 1] * B + (long long)(S[j] == i + 'a')) % mod;
}
}
while (m--)
{
scanf("%d%d%d", &x, &y, &l);
vector<int> v1, v2;
for (int i = 0; i < 26; ++i)
{
v1.push_back(((h[i][x + l - 1] - p[l] * h[i][x - 1]) % mod + mod) % mod);
v2.push_back(((h[i][y + l - 1] - p[l] * h[i][y - 1]) % mod + mod) % mod);
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
printf("%s\n", v1 == v2 ? "YES" : "NO");
}
}

参考

blb的博客: https://0xfaner.top/

OI-Wiki: https://oi-wiki.org/

----- 本文结束 感谢阅读 -----
0%