KMP 算法详解:
KMP 算法是一种改进的字符串匹配算法, 由 D.E.Knuth,J.H.Morris 和 V.R.Pratt(雾) 提出的.
对于字符串匹配问题 (such as 问你在 abababb 中有多少个 ab 串?), 朴素的想法是定一个 i, 从字符串首扫到字符串尾部来枚举字符串位置, 找到一个首字符相同的就通过第二层 for 循环来继续往下一个字符一个字符的匹配.
直到匹配到长度和需要匹配的子串 (模式串) 长度相等, 我们就说找到了一个在原串中的子串并将答案加一, 然后继续往下像蜗牛一样的搜索.
有关相似的算法, 链接这里 hash
举个栗子: A:GCAKIOI B:GC , 那么我们称 B 串是 A 串的子串
我们称等待匹配的 A 串为主串, 用来匹配的 B 串为模式串.
一般的朴素做法就是枚举 B 串的第一个字母在 A 串中出现的位置并判断是否适合, 而这种做法的时间复杂度是 O(mn) 的, 当你处理一篇较长文章的时候显然就会超时.
我们会发现在字符串匹配的过程中, 绝大多数的尝试都会失败, 那么有没有一种算法能够利用这些失败的信息呢?
KMP 算法就是
KMP 算法的关键是利用匹配失败后的信息, 尽量减少模式串与主串的匹配次数以达到快速匹配的目的
设主串 (以下称为 T)
设模式串 (以下称为 W)
用暴力算法匹配字符串过程中, 我们会把 T[0] 跟 W[0] 匹配, 如果相同则匹配下一个字符, 直到出现不相同的情况, 此时我们会丢弃前面的匹配信息, 然后把 T[1] 跟 W[0] 匹配, 循环进行, 直到主串结束, 或者出现匹配成功的情况. 这种丢弃前面的匹配信息的方法, 极大地降低了匹配效率.
我们来看一看 KMP 是怎么工作的
在 KMP 算法中, 对于每一个模式串我们会事先计算出模式串的内部匹配信息 (也就是说这个东西只和模式串有关, 可以预处理, 这个处理我们后面会提到), 在匹配失败时最大的移动模式串, 以减少匹配次数.
比如, 在简单的一次匹配失败后, 我们会想将模式串尽量的右移和主串进行匹配. 右移的距离在 KMP 算法中是如此计算的: 在已经匹配的模式串子串中, 找出最长的相同的前缀和后缀, 然后移动使它们重叠.
我们用两个指针 i 和 j 分别表示 A[i-j+1......i] 和 B[1......j] 完全相等, 也就是说 i 是不断增加的, 并且随着 i 的增加, j 也相应的变化, 并且 j 满足以 A[j] 结尾的长度为 j 的字符串正好匹配 B 串的前 j 个字符, 现在需要看 A[i+1] 和 B[j+1] 的关系
当 A[i+1]=B[j+1] 时, 我们将 i 和 j 各增加 1
否则, 我们减小 j 的值, 使得 A[i-j+1......i] 和 B[1......j] 保持匹配并尝试匹配新的 A[i+1] 和 B[j+1]
举个栗子:
- T: a b a b a b a a b a b a c b
- W:a b a b a c b
当 i=j=5 时, 此时 T[6]!=W[6], 这表明此时 j 不能等于 5 了, 这个时候我们要改变 j 的值, 使得 W[1...j] 中的前 j'个字母与后 j'个字母相同, 因为这样 j 变成 j'后 (也就是将 W 右移 j'个长度) 才能继续保持 i 和 j 的性质. 这个 j'显然越大越好. 在这里 W[1...5] 是匹配的, 我们发现当 ababa 的前三个字母和后三个字母都是 aba, 所以 j'最大也就是 3, 此时情况是这样
- T: a b a b a b a a b a b a c b
- W: a b a b a c b
那么此时 i=5,j=3, 我们又发现 T[6] 与 W[4] 是相等的, 然后 T[7] 与 W[5] 是相等的 (这里是两步)
所以现在是这种情况: i=7,j=5
- T: a b a b a b a a b a b a c b
- W: a b a b a c b
这个时候又出现了 T[8]!=W[6] 的情况, 于是我们继续操作. 由于刚才已经求出来了当 j=5 时, j'=3, 所以我们就可以直接用了 (通过这里我们也可以发现 j'是多少和主串没有什么关系, 只和模式串有关系)
于是又变成了这样
- T: a b a b a b a a b a b a c b
- W: a b a b a c b
这时, 新的 j=3 依然不能满足 A[i+1]=B[j+1], 所以我们还需要取 j'我们发现当 j=3 时 aba 的第一个字母和最后一个字母都是 a, 所以这时 j'=1
新的情况:
- T: a b a b a b a a b a b a c b
- W: a ba b a c b
仍然不满足, 这样的话 j 需要减小到 j'就是 0(我们规定当 j=1 时, j'=0)
- T: a b a b a b a a b a b a c b
- W: a ba b a c b
终于, T[8]=B[1],i 变为 8,j 变为 1, 我们一位一位往后, 发现都是相等的, 最后当 j=7 还满足条件时, 我们就可以下结论: W 是 T 的子串, 并且还可以找到子串在主串中的位置 (i+1-m+1, 因为下标从 0 开始)
这一部分的代码其实很短, 因为用了 for 循环
- inline void kmp()
- {
- int j=0;
- for(int i=0;i<n;i++)
- {
- while(j>0&&b[j+1]!=a[i+1]) j=nxt[j];
- if(b[j+1]==a[i+1]) j++;
- if(j==m)
- {
- printf("%d\n",i+1-m+1);
- j=nxt[j];
- // 当输出第一个位置时 直接 break 掉
- // 当输出所有位置时 j=nxt[j];
- // 当输出区间不重叠的位置时 j=0
- }
- }
- }
这里就有一个问题: 为什么时间复杂度是线性的?
我们从上述的 j 值入手, 因为每执行一次 while 循环都会使 j 值减小 (但不能到负数), 之后 j 最多 + 1, 因此整个过程中最多加了 n 个 1. 于是 j 最多只有 n 个机会减小. 这告诉我们, while 循环最多执行了 n 次, 时间复杂度平摊到 for 循环上后, 一次 for 循环的复杂度是 O(1), 那么总的时间复杂度就是 O(n) 的 (n 是主串长度). 这样的分析对于下文的预处理来说同样有效, 也可以得到预处理的时间复杂度是 O(m)(m 是模式串长度)
接下来是预处理
预处理并不需要按照定义写成 O(m2) 甚至 O(m3), 窝们可以通过 nxt[1],nxt[2]....nxt[n-1] 来求得 nxt[n] 的值
举个栗子
W :a b a b a c b
nxt:0 0 1 2 ??
假如我们有一个串, 并且已经知道了 nxt[1~4] 那么如何求 nxt[5] 和 nxt[6] 呢?
我们发现, 由于 nxt[4]=2, 所以 w[1~2]=w[3~4], 求 nxt[5] 的时候, 我们发现 w[3]=w[5], 也就是说我们可以在原来的基础上 + 1, 从而得到更长的相同前后缀, 此时 nxt[5]=nxt[4]+1=3
W :a b a b a c b
nxt:0 0 1 2 3?
那么 nxt[6] 是否也是 nxt[5]+1 呢? 显然不是, 因为 w[nxt[5]+1]!=w[6], 那么此时我们可以考虑退一步, 看看 nxt[6] 是否可以由 nxe[5] 的情况所包含的子串得到, 即是否 nxt[6]=nxt[nxt[5]]+1?
事实上, 这样一直推下去也不行, 于是我们知道 nxt[6]=0
那么预处理的代码就是这样的
- inline void pre()
- {
- nxt[1]=0;// 定义 nxt[1]=0
- int j=0;
- rep(i,1,m-1)
- {
- while(j>0&&b[j+1]!=b[i+1]) j=nxt[j];
- // 不能继续匹配并且 j 还没有减到 0, 就退一步
- if(b[j+1]==b[i+1]) j++;
- // 如果能匹配, 就 j++
- nxt[i+1]=j;// 给下一个赋值
- }
- }
全部代码:
- #include
- #include
- #include
- using namespace std;
- char s1[1000003],s2[1000003];
- int p[1000002];
- int n,m;
- inline void yuchuli()
- {
- int j=0;
- for(int i=1;i<m;i++)
- {
- while(j>0&&s2[i+1]!=s2[j+1])j=p[j];
- if(s2[i+1]==s2[j+1])j++;
- p[i+1]=j;
- }
- }
- int main(){
- scanf("%s",s1+1);scanf("%s",s2+1);
- n=strlen(s1+1);m=strlen(s2+1);
- yuchuli();
- int j=0;
- for(int i=0;i<n;i++)
- {
- while(j>0&&s1[i+1]!=s2[j+1])j=p[j];
- if(s2[j+1]==s1[i+1])j++;
- if(j==m)
- {
- printf("%d\n",i+2-j);
- j=p[j];
- }
- }
- for(int i=1;i<=m;i++)
- {
- printf("%d",p[i]);
- }
- return 0;
- }
完结!
部分 (后半段) 内容引用 ych 大佬的
原因链接 https://www.cnblogs.com/lbssxz/p/11093691.html
来源: http://www.bubuko.com/infodetail-3105017.html