大佬教程收集整理的这篇文章主要介绍了扩展 KMP,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
对于一个长度为 (n) 的字符串 (s),定义函数 (z[i]) 表示 (s) 和 (s[i,n-1]) (即以 (s[i]) 开头的后缀)的最长公共前缀(LCP)的长度。(z) 被称作为 (s) 的 Z 函数。特别地,(z[0]=[0])。
国外一般将计算该数组的算法称为 Z Algorithm,而国内则称其为 扩展 KMP。
下面若干样例展示了对于不同字符串的 Z 函数:
在该算法中,我们从 (1) 到 (n−1) 顺次计算 (z[i]) 的值((z[0]=0))。在计算 (z[i]) 的过程中,我们会利用已经计算好的 (z[0],…,z[i−1])。
对于 (i),我们称区间 ([i,i+z[i]−1]) 是 (i) 的 匹配段,也可以叫 Z-box。
举例:
对于 (z(text{aBACaba})=[0,0,1,0,3,0,1]:)
a
。abc
。算法的过程中我们维护右端点最靠右的匹配段。为了方便,记作 ([l,r])。根据定义,(s[l,r]) 是 (s) 的前缀。在计算 (z[i]) 时我们保证 (l≤i)。初始时 (l=r=0)。
在计算 (z[i]) 的过程中:
设小串(模式串)为 (B),大串(文本串)为 (A)。
本代码中 (z[0]=|B|)。
求 (z) 数组:
void getZ()
{
z[0] = lenb;
int now = 0;
while (now + 1 < lenb && B[now] == B[now + 1])
now++;
z[1] = now;
int p0 = 1;
for (int i = 2; i < lenb; ++i)
{
if (i + z[i - p0] < p0 + z[p0])
{
z[i] = z[i - p0]; //第一种情况
}
else
{
now = p0 + z[p0] - i;
now = max(now, 0);
while (now + i < lenb && B[now] == B[now + i])
now++;
z[i] = now;
p0 = i;
}
}
}
求 (B) 与 (A) 的每一个后缀的 LCP 长度数组:
void exkmp()
{
int now = 0;
while (now < lenb && now < lena && B[now] == A[now])
now++;
ext[0] = now;
int p0 = 0;
for (int i = 1; i < lena; ++i)
{
if (i + z[i - p0] < p0 + ext[p0])
ext[i] = z[i - p0];
else
{
now = p0 + ext[p0] - i;
now = max(now, 0);
while (now < lenb && now + i < lena && B[now] == A[now + i])
now++;
ext[i] = now;
p0 = i;
}
}
}
对于内层 while
循环,每次执行都会使得 (r) 向后移至少 (1) 位,而 (r<n−1),所以总共只会执行 (n) 次。
对于外层循环,只有一遍线性遍历。
总复杂度为 (O(n))。
以上是大佬教程为你收集整理的扩展 KMP全部内容,希望文章能够帮你解决扩展 KMP所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。