做个网站商场需要多少,高端网站设计定制,白百度一下你就知道,自助建站系统官方版文章目录学习资源什么是KMP什么是前缀表为什么一定要用前缀表如何计算前缀表前缀表有什么问题使用next数组来匹配放码过来构造next数组一、初始化二、处理前后缀不相同的情况三、处理前后缀相同的情况使用next数组来做匹配代码总览测试代码时间复杂度分析学习资源
字符串…
文章目录学习资源什么是KMP什么是前缀表为什么一定要用前缀表如何计算前缀表前缀表有什么问题使用next数组来匹配放码过来构造next数组一、初始化二、处理前后缀不相同的情况三、处理前后缀相同的情况使用next数组来做匹配代码总览测试代码时间复杂度分析学习资源
字符串KMP是时候上场了一文读懂系列- 代码随想录字符串都来看看KMP的看家本领- 代码随想录
什么是KMP
KMP算法是由这三位学者发明的KnuthMorris和Pratt因此用这三位学者名字的首字母组合成来命名该算法。
KMP主要应用在字符串匹配上。KMP的主要思想是当出现字符串不匹配时可以知道一部分之前已经匹配的文本内容可以利用这些信息避免从头再去做匹配了。所以如何记录已经匹配的文本内容是KMP的重点也是next数组肩负的重任。
什么是前缀表
next数组就是一个前缀表prefix table。
前缀表是用来回溯的它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。
为了清楚的了解前缀表的来历举一个例子
要在文本串aabaabaafa中查找是否出现过一个模式串aabaaf。
如动画所示 动画里特意把 子串aa 标记上了这是有原因的大家先注意一下后面还会说道。
可以看出文本串中第六个字符b 和 模式串的第六个字符f不匹配了。如果暴力匹配会发现不匹配此时就要从头匹配了。
但如果使用前缀表就不会从头匹配而是从上次已经匹配的内容开始匹配找到了模式串中第三个字符b继续开始匹配。
此时就要问了前缀表是如何记录的呢
首先要知道前缀表的任务是当前位置匹配失败找到之前已经匹配上的位置在重新匹配此也意味着在某个字符失配时前缀表会告诉你下一步匹配中模式串应该跳到哪个位置。MyNote文本串不用跳转
那么什么是前缀表下表i之前包括i的字符串中有多大长度的相同前缀后缀。
MyNote本文“下表”的通假于“下标”。
为什么一定要用前缀表
前缀表那为啥就能告诉我们 上次匹配的位置并跳过去呢
回顾一下刚刚匹配的过程在下表5的地方遇到不匹配模式串是指向f如图 然后就找到了下表2指向b继续匹配如图 以下这句话对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要
下表5之前这部分的字符串也就是字符串aabaa的最长相等的前缀 和 后缀字符串是 子字符串aa 因为找到了最长相等的前缀和后缀匹配失败的位置是后缀子串的后面那么我们找到与其相同的前缀的后面从新匹配就可以了。
所以前缀表具有告诉我们当前位置匹配失败跳到之前已经匹配过的地方的能力。
如何计算前缀表
接下来就要说一说怎么计算前缀表。如图
一、长度为前1个字符的子串a最长相同前后缀的长度为0。注意这里计算相同前后缀不算重复的字符 二、长度为前2个字符的子串aa最长相同前后缀的长度为1。 三、长度为前3个字符的子串aab最长相同前后缀的长度为0。 以此类推
四、长度为前4个字符的子串aaba最长相同前后缀的长度为1。
五、长度为前5个字符的子串aabaa最长相同前后缀的长度为2。
六、长度为前6个字符的子串aabaaf最长相同前后缀的长度为0。
那么把求得的最长相同前后缀的长度就是对应前缀表的元素如图 可以看出前缀表里的数值代表着就是当前位置之前的子串有多大长度相同的前缀后缀。
再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示 找到的不匹配的位置 那么此时我们要看它的前一个字符的前缀表的数值是多少。
为什么要看前一个字符的前缀表的数值呢因为要找前面字符串的最长相同的前缀和后缀。
所以要看前一位的 前缀表的数值。
前一个字符的前缀表的数值是2 所有把下表移动到下表2的位置继续比配。可以再反复看一下上面的动画。
最后就在文本串中找到了和模式串匹配的子串了。
前缀表有什么问题
来看一下刚刚求的这个前缀表有什么问题呢 看这个位置红框的位置如果要找下表1 所对应 前缀表里的数值的时候前缀表里的数值依然是1然后就要跳到下表1的位置如此就形成了一个死循环。
**如何怎么避免呢就把前缀表里的数值统一减一 开始位置设置为-1 **。 这一点对理解后面KMP代码很重要
改为如图所示 这样就避免的死循环只不过后续取 前缀表里的数值的时候要记得再1才是我们想要的值。
最后得到的新前缀表在KMP算法里通常用一个next数组来表示。
注意这个next数组就根据模式串求取的。
使用next数组来匹配
有了next数组就可以根据next数组来 匹配文本串s和模式串t了。
注意next数组是新前缀表旧前缀表统一减一了。
匹配过程动画如下 放码过来
下文统称haystack为文本串, needle为模式串。
haystack, needle出处。
构造next数组
定义一个方法getNext来构建next数组参数为一个名为next数组和一个字符串。代码如下
private void getNext(int[] next, String s) {}构造next数组其实就是计算模式串s前缀表的过程。主要有如下三步
初始化处理前后缀不相同的情况处理前后缀相同的情况
一、初始化
定义两个指针i和j
j指向前缀终止位置严格来说是终止位置减一的位置i指向后缀终止位置与j同理。
通常是先i后j为什么这里相反接下来看代码就清楚了。
然后还要对next数组进行初始化赋值如下
int j -1;
next[0] j;j 初始化为 -1原因是前文说过前缀表要统一减一的操作避免死循环得情况所以j初始化为-1。 next[] 表示 i包括i之前最长相等的前后缀长度其实就是jnext[0]初始化为j 。
二、处理前后缀不相同的情况
因为j初始化为-1那么i就从1开始进行s[i] 与 s[j1]的比较。这里可能一开始不适应理解不用急。
所以遍历模式串s的循环下表i 要从 1开始代码如下
for(int i 1; i s.length(); i) { // 注意i从1开始如果 s[i] 与 s[j1]不相同也就是遇到 前后缀末尾不相同的情况就要回退。
如何回退next[j]就是记录着j包括j之前的子串的相同前后缀的长度。
那么 s[i] 与 s[j1] 不相同就要找 j1前一个元素在next数组里的值就是next[j]。
所以处理前后缀不相同的情况代码如下
while (j 0 s.charAt(i) ! s.charAt(j 1)) { // 前后缀不相同了j next[j]; // 回退
}三、处理前后缀相同的情况
如果s[i] 与 s[j 1] 相同那么就同时向后移动i 和j 说明找到了相同的前后缀同时还要将j前缀的长度赋给next[i], 因为next[i]要记录相同前后缀的长度。
代码如下
if (s.charAt(i) s.charAt(j 1)) { // 找到相同的前后缀j;
}
next[i] j; // 将j前缀的长度赋给next[i]最后整体构建next数组的函数代码如下
private void getNext(int[] next, String s) {int j -1;next[0] j;for(int i 1; i s.length(); i) { // 注意i从1开始while (j 0 s.charAt(i) ! s.charAt(j 1)) { // 前后缀不相同了j next[j]; // 向前回溯}if (s.charAt(i) s.charAt(j 1)) { // 找到相同的前后缀j;}next[i] j; // 将j前缀的长度赋给next[i]}
}代码构造next数组的逻辑流程动画如下 得到了next数组之后就开始用它做匹配。
使用next数组来做匹配
在文本串haystack里找是否出现过模式串needle。定义两个下表j 指向模式串起始位置i指向文本串其实位置。
那么j初始值依然为-1这是因为next数组里记录的起始位置为-1。
i就从0开始遍历文本串代码如下
for (int i 0; i haystack.length(); i) { // 注意i就从0开始接下来就是 haystack.charAt(i) 与 needle.charAt(j 1) 因为j从-1开始的 进行比较。
如果 haystack.charAt(i) 与 needle.charAt(j 1) 不相同j就要从next数组里寻找下一个匹配的位置。
代码如下
while(j 0 haystack.charAt(i) ! needle.charAt(j 1)) { // 不匹配j next[j]; // j 寻找之前匹配的位置
}如果 haystack.charAt(i) 与 needle.charAt(j 1) 相同那么i 和 j 同时向后移动 代码如下
if (haystack.charAt(i) needle.charAt(j 1)) { // 匹配j和i同时向后移动 j;
}如果j指向了模式串t的末尾那么就说明模式串t完全匹配文本串s里的某个子串了。
本题要在文本串字符串中找出模式串出现的第一个位置从0开始所以返回当前在文本串匹配模式串的位置i 减去 模式串的长度就是文本串字符串中出现模式串的第一个位置。
代码如下
if (j (needle.length() - 1) ) { // 文本串s里出现了模式串treturn (i - needle.length() 1);
}代码总览
public class KMP {private void getNext(int[] next, String s) {int j -1;next[0] j;for(int i 1; i s.length(); i) { // 注意i从1开始while (j 0 s.charAt(i) ! s.charAt(j 1)) { // 前后缀不相同了j next[j]; // 向前回溯}if (s.charAt(i) s.charAt(j 1)) { // 找到相同的前后缀j;}next[i] j; // 将j前缀的长度赋给next[i]}}public int strStr(String haystack, String needle) {if (needle.length() 0) {return 0;}int[] next new int[needle.length()];getNext(next, needle);int j -1; // // 因为next数组里记录的起始位置为-1for (int i 0; i haystack.length(); i) { // 注意i就从0开始while(j 0 haystack.charAt(i) ! needle.charAt(j 1)) { // 不匹配j next[j]; // j 寻找之前匹配的位置}if (haystack.charAt(i) needle.charAt(j 1)) { // 匹配j和i同时向后移动 j; }if (j (needle.length() - 1) ) { // 文本串s里出现了模式串treturn (i - needle.length() 1); }}return -1;}
}测试代码
import static org.junit.Assert.*;import org.junit.Test;public class KMPTest {Testpublic void test() {KMP k new KMP();assertEquals(2, k.strStr(hello, ll));assertEquals(-1, k.strStr(aaaaa, bba));assertEquals(3, k.strStr(aabaabaafa, aabaaf));}}
时间复杂度分析
假设文本串长度为n模式串长度为m。因为在匹配的过程中根据前缀表不断调整匹配的位置可以看出匹配的过程是O(n)但之前还要单独生成next数组时间复杂度是O(m)所以整个KMP算法的时间复杂度是O(nm)的。
暴力的解法显而易见是O(n * m)所以KMP在字符串匹配中极大的提高的搜索的效率。
