超全超详解 KMP个人理解
适合想象力丰富,可以脑补(无图片)
28.找出字符串第一个匹配项的第一个匹配项的下标
给你两个字符串 haystack
和 needle
,请你在 haystack
字符串中找出 needle
字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle
不是 haystack
的一部分,则返回 -1
。
示例 1:
输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。
示例 2:
输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。
思路
kmp算法,找到p在s中第一次出现的位置。
一般来说从1开始比较好s = ' ' + s ;
next数组。
按照道理来说,使用两个数组,来维护移动两个数组是可以比较出来的, 如果出现不同的那么维护短的数组直接到头重新开始就好,但是现在我们可以做到。由于对于p而言,我的后边的一部分,和我前边的一部分是一致的,那么我可以不从头开始,从已经预设好的next[j]开始。
类似于我在和你匹配的过程中,快结束了,但是最后没匹配上,这个时候,我还想和你匹配,我的前半段和你之前的是一样的,我再凑一凑,看看能否和你继续匹配。从这里继续来匹配。
那我肯定希望我们比较的时间少一点比较好,所以,我肯定找我和你剩下部分里最多和你一样的部分。
原来我的身子到脚的部分和你一样,但是最后不一样,现在我把头到腰部的位置发现,和我腰到腿的地方一样,那么我现在换一下,用头到腰的位置继续和你比。
next[i] 表示 的含义就是: 以1开始的和以i结束的这段里,相等的字符串的长度最长的一个字符串。next[i]的长度是和p有关的,也就是先要算出来next数组,然后再可以帮助我们来去匹配s.
原理搞得明白kmp在做什么,但是如何具体的去写代码呢?这个问题其实有点复杂。
我来想一个最好记录下来的代码吧
求next数组:
我们需要的是两个指针,一个是i循环,向后。还有一个是k吧,他是前缀的数组,只有匹配之后才移动。
我们默认串是从1开始的,i从2开始,k从0开始。
第一个while(k && p[i] != p[k+1])k = next[k];
这个就是使用next数组的作用,让他出现不匹配的情况时,让k到最近的匹配的点。之后也应该是这样用的。k为0的情况,就是一开始的情况,已经没法再找到跟开始的位置了。
if(p[i] == p[k+1]) k++ ; 这个表示的就是出现一致的,说明匹配成功。k向后移动。移动到一样的点的位置。例如,第一个点aa匹配成功。那么k就到了1。
next[i] = k ; 表示的是好的,现在i这个点如果后边的不一样可以从k开始。abab , i到4的位置,k此时再上一行代码里,匹配到了k变成了2,那么现在next[4] = 2 ;
如果,再次循环的过程中,ababc。这个时候,出现了情况是p[i]!=p[k+1] ,c和a不同,这个时候,k = 还是2,所以就让k =next[2] = 0,重新回到0。
大概就是这个意思。第一行while来使用next,如果出现不同,让k回到最佳的位置,第二行匹配下面的代码,如果匹配一致继续,然后存下来当前的i位置的next[i] = k;
for(int i = 2 , k = 0 ; i <= m ; i++)
{
while(k && nums[i]!=nums[k+1] ) k = next[k];
if(nums[i] == nums[k+1]) k++;
next[i] = k;
}
那么继续,如果已经有了我们的next数组如何使用数组来找到进行对字符串的匹配呢?(直接从代码理解)
规定是s是需要被匹配的长的串,p是短的那个串。从1开始。i表示遍历s的指针,j表示遍历p的指针。由于我们一定要遍历s所以从1开始,由于我们不一定那个字符和p第一个一致与否,所以j从0开始。
循环内部,第一行依旧是while来判断能否匹配j的下一个,如果不行,那么j跳到next指定的那个位置。
第二行,依旧是如果s[i] == p[j+1] 那么j++,当前的字符匹配成功。
第三行,if(j == m ) 说明匹配成功。这个时候做你想做的。
这道题是在找到匹配成功的开始的那个位置,i的值表示的是在s中的位置,那么找到开头,就需要减去p字符的长度, i - m 就是所求,由于题目要求的是从0开始,我们的设置是从1开始,所以假设为saddsf 和sad, 那么刚好,i是3,m是3,i-m就是第0个位置。
for(int i = 1 , j = 0 ; i <= n ; i ++){
while(j && s[i] != p[j+1]) j = next[j];
if(s[i] == p[j+1]) j++;
if(j == m) return i-m;
}
代码
class Solution {
public:
int strStr(string s, string p) {
int n = s.size() , m = p.size();
s = ' ' + s , p = ' ' + p ;
// 匹配next数组
vector<int> next(m+1);
for(int i = 2 , k = 0 ; i <= m ; i++)
{
while(k && p[i]!=p[k+1] ) k = next[k];
if(p[i] == p[k+1]) k++;
next[i] = k;
}
// j 相当于是前缀,i相当于是后缀,i会比j搓出来一个,并且当j+1和i匹配,。
// 在匹配之后,j++,next[i] =
for(int i = 1 , j = 0 ; i <= n ; i ++){
while(j && s[i] != p[j+1]) j = next[j];
if(s[i] == p[j+1]) j++;
if(j == m) return i-m;
}
return -1;
}
};