KMP算法讲解

KMP算法讲解,kmp算法

老规矩,讲算法前,先说一道小问题吧

给你一个长串和短串,求短串在长串中出现的次数和位置。

设长串长度为len1,短串长度为len2。

如果len1*len2<=108,那就很简单了,直接暴力枚举以每个字符为开始的字符串是否匹配即可,复杂度为O(len1*len2);(是不是感觉太大了?)

如果将数据范围扩大到len1,len2<-106呢?

现在就开始介绍我们的KMP算法。

有了前面的问题,KMP要解决的是什么就自然出来了,KMP的复杂度达到的耸人听问的O(len1+len2)。

我们可以想想我们相对于暴力算法需要改进什么?

我们可以每一次失配(也就是匹配失败)的时候,不用每一次都从上一次的出发点只往后移动一个字符,可以跳啊!

我们可以预处理出每一次跳的位置来有利于节省复杂度啊。

这里我们就讲一讲怎么跳,以及怎么进行预处理。

1.怎么跳?

我们假设字符串为abaaba

我们如果在第二个a时失配了,我们应该怎么往前呢?

我们就可以可以把第一个a放在这一个位置继续匹配。

那么,如果是第四个a呢?

我们是不是就可以把第二个a放在这个位置呢?

大家可以看到,第最后一个字符到第三个a的字符串是aba,而第一个字符到第二个a的字符串是不是也是aba,它们不是一样的吗?

讲到这里,大家应该大概的明白了KMP是怎么跳的了吧。

我们记一个nxt数组,nxt[i]表示的是从第一个字符到第i个字符的最长前后缀的长度。看不懂没关系,举个例子。

假设字符串为abaaba

nxt[0]=0

nxt[1]=0(ab无前后缀)

nxt[2]=1(aba最长前后缀为a)

nxt[3]=1(abaa-----a)

nxt[4]=0(abaab--无)

nxt[5]=3(abaaba-aba)

2.初始化

问题来了,怎么用很少的时间复杂度来进行初始化呢?

很容易想到递推,怎么递推呢?

我们假设求出了前面的nxt,现在多了一个,我们就应该找一找了。

我们可以跳前一个位置的nxt,直到跳到一个位置后面有一个字符是所需要的,是那里的后面那一个字符。

每个这样递推就好了!

而查找的过程与初始化的过程类似,这里就不再赘述了。

下面上一份模板代码

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 char s1[1000010],s2[1000100]; 6 int nxt[1000100]; 7 int main() 8 { 9 scanf("%s",s1);10 scanf("%s",s2);11 nxt[0]=0;12 int len1=strlen(s1);13 int len2=strlen(s2);14 for(int i=1,k=0;i<len2;i++)15 {16 k=nxt[i-1];17 while(k>0&&s2[k]!=s2[i]) k=nxt[k-1];18 if(s2[k]==s2[i]) k++;19 nxt[i]=k;20 }21 for(int i=0,j=0;i<len1;i++)22 {23 while(j!=0&&s1[i]!=s2[j]) j=nxt[j-1];24 if(s1[i]==s2[j]) j++;25 if(j==len2)26 {27 printf("%d\n",i-j+2);28 }29 }30 for(int i=0;i<len2;i++) printf("%d ",nxt[i]);31 return 0;32 }

 

模板题:

感谢大家的支持!

如果有不足之处,请尽管提出,本人不胜感激!

 

老规矩,讲算法前,先说一道小问题吧
给你一个长串和短串,求短串在长串中出现的次数和位置。
设长串长度为len...

老规矩,讲算法前,先说一道小问题吧

给你一个长串和短串,求短串在长串中出现的次数和位置。

设长串长度为len1,短串长度为len2。

如果len1*len2<=108,那就很简单了,直接暴力枚举以每个字符为开始的字符串是否匹配即可,复杂度为O(len1*len2);(是不是感觉太大了?)

如果将数据范围扩大到len1,len2<-106呢?

现在就开始介绍我们的KMP算法。

有了前面的问题,KMP要解决的是什么就自然出来了,KMP的复杂度达到的耸人听问的O(len1+len2)。

我们可以想想我们相对于暴力算法需要改进什么?

我们可以每一次失配(也就是匹配失败)的时候,不用每一次都从上一次的出发点只往后移动一个字符,可以跳啊!

我们可以预处理出每一次跳的位置来有利于节省复杂度啊。

这里我们就讲一讲怎么跳,以及怎么进行预处理。

1.怎么跳?

我们假设字符串为abaaba

我们如果在第二个a时失配了,我们应该怎么往前呢?

我们就可以可以把第一个a放在这一个位置继续匹配。

那么,如果是第四个a呢?

我们是不是就可以把第二个a放在这个位置呢?

大家可以看到,第最后一个字符到第三个a的字符串是aba,而第一个字符到第二个a的字符串是不是也是aba,它们不是一样的吗?

讲到这里,大家应该大概的明白了KMP是怎么跳的了吧。

我们记一个nxt数组,nxt[i]表示的是从第一个字符到第i个字符的最长前后缀的长度。看不懂没关系,举个例子。

假设字符串为abaaba

相关文章

Comment ()
评论是一种美德,说点什么吧,否则我会恨你的。。。