【模板】KMP字符串匹配

算法参考:https://blog.csdn.net/sb985/article/details/79735488
时间复杂度:$O(m+n)$

计算Next数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int m,n;
char s[maxn], t[maxm];
int Next[maxm];

void getnext()
{
Next[0] = -1;
int i = 0, j = -1;
while(i<m)
{
while(j!=-1 && t[i]!=t[j]) j = Next[j];
Next[++i] = ++j;
}
}

优化的Next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int m,n;
char s[maxn], t[maxm];
int Next[maxm];

void getnext()
{
Next[0] = -1;
int i = 0, j = -1;
while(i<m)
{
while(j!=-1 && t[i]!=t[j]) j = Next[j];
if(t[++j] == t[++i]) Next[i] = Next[j];
Next[i] = j;
}
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
统计主串中模式串的个数,可以重叠。 (HDU-1686,洛谷P3375)
*/
int kmp()
{
int ans = 0;
getnext();
int i = 0, j = 0;
while(i<n)
{
while(j!=-1 && s[i]!=t[j]) j = Next[j];
i++; j++;
if(j==m)
{
ans++;
j = Next[j]; // 如果要求匹配串不重叠,则 j = 0, (HDU-2087)
}
}
return 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
int GetMinPos(string x)
{
int i = 0, j = 1, k;
int l = x.size();
while(i < l && j < l) {
k = 0;
while(x[(i+k)%l] == x[(j+k)%l] && k < l) k++;
if(k == l) break;
if(x[(i+k)%l] < x[(j+k)%l])
if(j+k+1 >= i) j += k+1;
else j = i+1;
else
if(i+k+1 >= j) i += k+1;
else i = j+1;
if(i == j) j++;
}
return min(i,j);
}

int GetMaxPos(string x, int l)
{
int i = 0, j = 1, k;
int l = x.size();
while(i < l && j < l) {
k = 0;
while(x[(i+k)%l] == x[(j+k)%l] && k < l) k++;
if(k == l) break;
if(x[(i+k)%l] < x[(j+k)%l])
if(i+k+1 >= j) i += k+1;
else i = j+1;
else
if(j+k+1 >= i) j += k+1;
else j = i+1;
if(i == j) j++;
}
return min(i,j);
}

文章作者: Irimsky
文章链接: /2019/11/03/【模板】KMP字符串匹配/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Irimsky's Blog

评论