// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度
求模式串的Next数组:
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
这段代码是KMP算法的实现,用于在一个长文本s
中查找模式串p
。
第一个循环用于求解模式串p
的Next
数组。初始时,j = 0
表示前缀为空,i = 2
表示后缀从第二个字符开始。在求解过程中,如果当前字符p[i]
和前缀的下一个字符p[j + 1]
相等,则将j
向后移动一位;否则将j
更新为ne[j]
,其中ne[j]
表示前面最长公共前后缀的长度(也就是Next
数组)。这样做可以保证在匹配过程中尽可能少地回溯。
第二个循环用于在长文本s
中查找模式串p
。初始时,j = 0
表示匹配起点为模式串的开头。在匹配过程中,如果当前字符s[i]
和模式串的下一个字符p[j + 1]
相等,则将j向后移动一位;否则将j更新为ne[j]
。当j = m
时(也就是整个模式串都匹配成功),说明找到了一个匹配位置,并且需要继续寻找下一个匹配位置。因此需要将j
更新为ne[j]
,重新开始匹配。
KMP算法的核心思想是利用已知信息尽可能减少不必要的比较次数,在匹配过程中避免重复比较已经匹配成功的前缀。这样可以将时间复杂度降到O(n+m)的级别,比暴力枚举法要快得多。