建设网站所需要什么,方案 网站建设,做求职网站市场,网站建设的税收分类编码文章目录28. 找出字符串中第一个匹配项的下标看答案KMPnext数组#xff08;前缀表#xff09;最长公共前后缀如何计算前缀表前缀表与next数组时间复杂度分析28. 找出字符串中第一个匹配项的下标
莫得思路……好久没做题#xff0c;都已经忘得差不多了
看答案
其实就是自己…
文章目录28. 找出字符串中第一个匹配项的下标看答案KMPnext数组前缀表最长公共前后缀如何计算前缀表前缀表与next数组时间复杂度分析28. 找出字符串中第一个匹配项的下标
莫得思路……好久没做题都已经忘得差不多了
看答案
其实就是自己写一个String的indexOf函数它的作用是返回某个字符串在另一个字符串中首次出现的位置。
利用的思想是KMP
KMP
例子 要在文本串aabaabaafa 中查找是否出现过一个模式串aabaaf。
KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时可以知道一部分之前已经匹配的文本内容可以利用这些信息避免从头再去做匹配了。
next数组前缀表
next数组就是一个前缀表prefix table。
前缀表有什么作用呢
前缀表是用来回退的它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。
那么什么是前缀表记录下标i之前包括i的字符串中有多大长度的相同前缀后缀。
最长公共前后缀
文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
正确理解什么是前缀什么是后缀很重要!
所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…
匹配的过程在下标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。
那么把求得的最长相同前后缀的长度就是对应前缀表的元素如图 找到的不匹配的位置 那么此时我们要看它的前一个字符的前缀表的数值是多少。
然后移动到从前一个字符处开始它对应的前缀表是多少就向前移多少个位置不包括前一个元素本身所以移动到b处 其实这里移动到的位置就是前缀表的元素代表的位置不用前移多少个元素比如aabaaf中f处不匹配应该移动到它的前一个元素a对应的前缀表元素所指的位置即字符串下标为2的元素处即b。 前缀表与next数组
很多KMP算法的时间都是使用next数组来做回退操作那么next数组与前缀表有什么关系呢
next数组就可以是前缀表但是很多实现都是把前缀表统一减一右移一位初始位置为-1之后作为next数组。
其实这并不涉及到KMP的原理而是具体实现next数组既可以就是前缀表也可以是前缀表统一减一右移一位初始位置为-1。
时间复杂度分析
其中n为文本串长度m为模式串长度因为在匹配的过程中根据前缀表不断调整匹配的位置可以看出匹配的过程是O(n)之前还要单独生成next数组时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(nm)的。
暴力的解法显而易见是O(n × m)所以KMP在字符串匹配中极大地提高了搜索的效率。
class Solution {public int strStr(String haystack, String needle) {int[] nextnew int[needle.length()];next[0]0;getNext(next,needle);int j0;for(int i0;ihaystack.length();i){//这里的i是从0开始此时的目的是要将//长的字符串和短的字符串从0号位置开始比较while(j0haystack.charAt(i)!needle.charAt(j)){jnext[j-1];}if(haystack.charAt(i)needle.charAt(j)){j;}if(jneedle.length()){return i-needle.length()1;}}return -1;}//获得next数组public void getNext(int[] next,String s){int j0;for(int i1;is.length();i){//因为要得到前后相等的公共字符串而next的0位置的元素//一定是0所以i取1也就是从next数组的1号元素开始填充while(j0s.charAt(i)!s.charAt(j)){jnext[j-1];//回退到前个元素的next数组处}if(s.charAt(i)s.charAt(j)){j;}next[i]j;}}
}
