implement什么意思

LeetCode-难题集之ImplementstrStr（）与KMP算法

ImplementstrStr().

Returnstheindexofthefirstoccurrenceofneedleinhaystack,or-1ifneedleisnotpartofhaystack.

这道题不难但引出了KMP算法，这个是⼀个难理解的算法，先看看此题的三种解法接着介绍KMP算法。

Brute-forceversion

classSolution{

public:

intstrStr(stringhaystack,stringneedle){

inti,hSize=(),nSize=();

if(hSize

if(!nSize)return0;

for(i=0;i<=hSize-nSize&&(i,nSize)!=needle;++i);

returni<=hSize-nSize?i:-1;

}

};

Robin-Karpversion

classSolution{

public:

intstrStr(stringhaystack,stringneedle){

if(needle=="")return0;

for(inti=0;i<();++i){

inttmp=i;

if(i+()>())return-1;

if(needle[0]==haystack[i]){

intj=0;

while(j<()&&needle[++j]==haystack[++i]);

if(j==()){

returntmp;

}el{

i=tmp;

}

}

}

return-1;

}

};

StandardKMPalgorithm

classSolution{

private:

voidbuildKMPTable(conststring&s,vector&KMP_Table)

{

intsSize=(),i=2,j=0;

KMP_Table[0]=-1;

if(sSize>1)KMP_Table[1]=0;

while(i

{

if(s[i-1]==s[j])KMP_Table[i++]=++j;

elif(j>0)j=KMP_Table[j];

elKMP_Table[i++]=0;

}

}

public:

intstrStr(stringhaystack,stringneedle){

intstart=0,i=0,hSize=(),nSize=();

if(hSize

if(!nSize)return0;

vectorKMP_Table(nSize,0);

buildKMPTable(needle,KMP_Table);

while(start<=hSize-nSize)

{

if(haystack[start+i]==needle[i])

{

if(++i==nSize)returnstart;

}

el

{

start=start+i-KMP_Table[i];

i=i>0?KMP_Table[i]:0;

}

}

return-1;

}

};

KMP算法

如果你看不懂KMP算法，那就看⼀看这篇⽂章(绝对原创，绝对通俗易懂)

KMP算法，俗称“看⽑⽚”算法，是字符串匹配中的很强⼤的⼀个算法，不过，对于初学者来说，要弄懂它确实不易。整个寒假，因为家⾥

没有⽹，为了理解这个算法，那可是花了九⽜⼆虎之⼒！不过，现在我基本上对这个算法理解算是⽐较透彻了！特写此⽂与⼤家分享分享！

我个⼈总结了，KMP算法之所以难懂，很⼤⼀部分原因是很多实现的⽅法在⼀些细节的差异。怎么说呢，举我寒假学习的例⼦吧，我是

看了⼀种⽅法后，似懂⾮懂，然后去看另外的⽅法，就全都乱了！体现在⼏个⽅⾯：next数组，有的叫做“失配函数”，其实是⼀个东

西；next数组中，有的是以下标为0开始的，有的是以1开始的；KMP主算法中，当发⽣失配时，取的next数组的值也不⼀样！就这

样，各说各的，乱的很！

所以，在阐述我的理解之前，我有必要说明⼀下，我是⽤next数组的，next数组是以下标0开始的！还有，我不会在⼀些基础的概念上

浪费太多，所以你在看这篇⽂章时必须要懂得⼀些基本的概念，例如“朴素字符串匹配”“前缀”，“后缀”等！还有就是，这篇⽂章的每⼀

个字都是我⾟⾟苦苦码出来的，图也是我⾃⼰画的！如果要转载，请注明出处！好了，开始吧！

假设在我们的匹配过程中出现了这⼀种情况：

根据KMP算法，在该失配位会调⽤该位的next数组的值！在这⾥有必要来说⼀下next数组的作⽤！说的太繁琐怕你听不懂，让我⽤⼀句

话来说明：

返回失配位之前的最长公共前后缀！

好，不管你懂不懂这句话，我下⾯的⽂字和图应该会让你懂这句话的意思以及作⽤的！

⾸先，我们取之前已经匹配的部分（即蓝⾊的那部分！）

我们在上⾯说到next数组的作⽤时，说到“最长公共前后缀”，体现到图中就是这个样⼦！

接下来，就是最重要的了！

没错，这个就是next数组的作⽤了:

返回当前的最长公共前后缀长度，假设为len。因为数组是由0开始的，所以next数组让第len位与主串匹配就是拿最长前缀之后的

第1位与失配位重新匹配，避免匹配串从头开始！如下图所⽰！

（重新匹配刚才的失配位！）

/-

"前缀"和"后缀"。"前缀"指除了最后⼀个字符以外，⼀个字符串的全部头部组合；"后缀"指除了第⼀个字符以外，⼀个字符串的全部尾部组合。

以”ABCDABD”为例，进⾏介绍：

－ ”A”的前缀和后缀都为空集，共有元素的长度为0；

－ ”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

－ ”ABC”的前缀为[A,AB]，后缀为[BC,C]，共有元素的长度0；

－ ”ABCD”的前缀为[A,AB,ABC]，后缀为[BCD,CD,D]，共有元素的长度为0；

－ ”ABCDA”的前缀为[A,AB,ABC,ABCD]，后缀为[BCDA,CDA,DA,A]，共有元素为”A”，长度为1；

－ ”ABCDAB”的前缀为[A,AB,ABC,ABCD,ABCDA]，后缀为[BCDAB,CDAB,DAB,AB,B]，共有元素为”AB”，长度为2；

－ ”ABCDABD”的前缀为[A,AB,ABC,ABCD,ABCDA,ABCDAB]，后缀为[BCDABD,CDABD,DABD,ABD,BD,D]，共有元素的长度为0。

-/

如果都说成这样你都不明⽩，那么你真的得重新理解什么是KMP算法了！

接下来最重要的，也是KMP算法的核⼼所在，就是next数组的求解！不过，在这⾥我找到了⼀个全新的理解⽅法！如果你懂的上⾯我写

的的，那么下⾯的内容你只需稍微思考⼀下就⾏了！

跟刚才⼀样，我⽤⼀句话来阐述⼀下next数组的求解⽅法，其实也就是两个字：

继承

a、当前⾯字符的前⼀个字符的对称程度为0的时候，只要将当前字符与⼦串第⼀个字符进⾏⽐较。这个很好理解啊，前⾯都是0，说明

都不对称了，如果多加了⼀个字符，要对称的话最多是当前的和第⼀个对称。⽐如agcta这个⾥⾯t的是0，那么后⾯的a的对称程度只需

要看它是不是等于第⼀个字符a了。

b、按照这个推理，我们就可以总结⼀个规律，不仅前⾯是0呀，如果前⾯⼀个字符的next值是1，那么我们就把当前字符与⼦串第⼆

个字符进⾏⽐较，因为前⾯的是1，说明前⾯的字符已经和第⼀个相等了，如果这个⼜与第⼆个相等了，说明对称程度就是2了。有两个字

符对称了。⽐如上⾯agctag，倒数第⼆个a的next是1，说明它和第⼀个a对称了，接着我们就把最后⼀个g与第⼆个g⽐较，⼜相等，

⾃然对称成都就累加了，就是2了。

c、按照上⾯的推理，如果⼀直相等，就⼀直累加，可以⼀直推啊，推到这⾥应该⼀点难度都没有吧，如果你觉得有难度说明我写的太失

败了。

当然不可能会那么顺利让我们⼀直对称下去，如果遇到下⼀个不相等了，那么说明不能继承前⾯的对称性了，这种情况只能说明没有那么

多对称了，但是不能说明⼀点对称性都没有，所以遇到这种情况就要重新来考虑，这个也是难点所在。

如果蓝⾊的部分相同，则当前next数组的值为上⼀个next的值加⼀，如果不相同，就是我们下⾯要说的！

如果不相同，⽤⼀句话来说，就是：

从前⾯来找⼦前后缀

1、如果要存在对称性，那么对称程度肯定⽐前⾯这个的对称程度⼩，所以要找个更⼩的对称，这个不⽤解释了吧，如果⼤那么就继承前

⾯的对称性了。

2、要找更⼩的对称，必然在对称内部还存在⼦对称，⽽且这个必须紧接着在⼦对称之后。

如果看不懂，那么看⼀下图吧！

好了，我已经把该说的尽可能以最浅显的话和最直接的图展⽰出来了，如果还是不懂，那我真的没有办法了！

说了这么多，下⾯是代码实现

#include

#include

#include

#defineN100

voidcal_next(char*str,int*next,intlen)

{

inti,j;

next[0]=-1;

for(i=1;i

{

j=next[i-1];

while(str[j+1]!=str[i]&&(j>=0))

{

j=next[j];

}

if(str[i]==str[j+1])

{

next[i]=j+1;

}

el

{

next[i]=-1;

next[i]=-1;

}

}

}

intKMP(char*str,intslen,char*ptr,intplen,int*next)

{

ints_i=0,p_i=0;

while(s_i

{

if(str[s_i]==ptr[p_i])

{

s_i++;

p_i++;

}

el

{

if(p_i==0)

{

s_i++;

}

el

{

p_i=next[p_i-1]+1;

}

}

}

return(p_i==plen)?(s_i-plen):-1;

}

intmain()

{

charstr[N]={0};

charptr[N]={0};

intslen,plen;

intnext[N];

while(scanf("%s%s",str,ptr))

{

slen=strlen(str);

plen=strlen(ptr);

cal_next(ptr,next,plen);

printf("%dn",KMP(str,slen,ptr,plen,next));

}

return0;

}

⽼实说还是不明⽩，接着看这篇博⽂，⼤概就理解了

kmp算法⼜称“看⽑⽚”算法，是⼀个效率⾮常⾼的字符串匹配算法。不过由于其难以理解，所以在很长的⼀段时间内⼀直没有搞懂。虽然⽹

上有很多资料，但是鲜见好的博客能简单明了地将其讲清楚。在此，综合⽹上⽐较好的⼏个博客（参见最后），尽⾃⼰的努⼒争取将kmp算

法思想和实现讲清楚。

kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。常规⽅法是遍历a的

每⼀个位置，然后从该位置开始和b进⾏匹配，但是这种⽅法的复杂度是O(nm)。kmp算法通过⼀个O(m)的预处理，使匹配的复杂度降为

O(n+m)。

kmp算法思想

我们⾸先⽤⼀个图来描述kmp算法的思想。在字符串O中寻找f，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。常

规⽅法是每次向前移动⼀位，但是它没有考虑前i-1位已经⽐较过这个事实，所以效率不⾼。事实上，如果我们提前计算某些信息，就有可能

⼀次前移多位。假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的f有什么特点。我们可以得到如下的结论：

A段字符串是f的⼀个前缀。

B段字符串是f的⼀个后缀。

A段字符串和B段字符串相等。

所以前移k位之后，可以继续⽐较位置i的前提是f的前i-1个位置满⾜：长度为i-k-1的前缀A和后缀B相同。只有这样，我们才可以前移k位后从

新的位置继续⽐较。

所以kmp算法的核⼼即是计算字符串f每⼀个位置之前的字符串的前缀和后缀公共部分的最⼤长度（不包括字符串本⾝，否则最⼤长度始终是

字符串本⾝）。获得f每⼀个位置的最⼤公共长度之后，就可以利⽤该最⼤公共长度快速和字符串O⽐较。当每次⽐较到两个字符串的字符不

同时，我们就可以根据最⼤公共长度将字符串f向前移动(已匹配长度-最⼤公共长度)位，接着继续⽐较下⼀个位置。事实上，字符串f的前移

只是概念上的前移，只要我们在⽐较的时候从最⼤公共长度之后⽐较f和O即可达到字符串f前移的⽬的。

next数组计算

理解了kmp算法的基本原理，下⼀步就是要获得字符串f每⼀个位置的最⼤公共长度。这个最⼤公共长度在算法导论⾥⾯被记为next数组。在

这⾥要注意⼀点，next数组表⽰的是长度，下标从1开始；但是在遍历原字符串时，下标还是从0开始。假设我们现在已经求得next[1]、

next[2]、……next[i]，分别表⽰长度为1到i的字符串的前缀和后缀最⼤公共长度，现在要求next[i+1]。由上图我们可以看到，如果位置i和位

置next[i]处的两个字符相同（下标从零开始），则next[i+1]等于next[i]加1。如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继

续分割，获得其最⼤公共长度next[next[i]]，然后再和位置i的字符⽐较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造，如果位

置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符

串长度为0为⽌。由此我们可以写出求next数组的代码（java版）：

publicint[]getNext(Stringb)

{

intlen=();

intj=0;

intnext[]=newint[len+1];//next表⽰长度为i的字符串前缀和后缀的最长公共部分，从1开始

next[0]=next[1]=0;

for(inti=1;i

{//j在每次循环开始都表⽰next[i]的值，同时也表⽰需要⽐较的下⼀个位置

while(j>0&&(i)!=(j))j=next[j];

if((i)==(j))j++;

next[i+1]=j;

}

returnnext;

}

上述代码需要注意的问题是，我们求取的next数组表⽰长度为1到m的字符串f前缀的最⼤公共长度，所以需要多分配⼀个空间。⽽在遍历字

符串f的时候，还是从下标0开始(位置0和1的next值为0，所以放在循环外⾯)，到m-1为⽌。代码的结构和上⾯的讲解⼀致，都是利⽤前⾯的

next值去求下⼀个next值。

字符串匹配

计算完成next数组之后，我们就可以利⽤next数组在字符串O中寻找字符串f的出现位置。匹配的代码和求next数组的代码⾮常相似，因为匹

配的过程和求next数组的过程其实是⼀样的。假设现在字符串f的前i个位置都和从某个位置开始的字符串O匹配，现在⽐较第i+1个位置。如

果第i+1个位置相同，接着⽐较第i+2个位置；如果第i+1个位置不同，则出现不匹配，我们依旧要将长度为i的字符串分割，获得其最⼤公共

长度next[i]，然后从next[i]继续⽐较两个字符串。这个过程和求next数组⼀致，所以可以匹配代码如下（java版）：

publicvoidarch(Stringoriginal,Stringfind,intnext[]){

intj=0;

for(inti=0;i<();i++){

while(j>0&&(i)!=(j))

j=next[j];

if((i)==(j))

j++;

if(j==()){

n("findatposition"+(i-j));

n(uence(i-j+1,i+1));

j=next[j];

}

}

}

上述代码需要注意的⼀点是，每次我们得到⼀个匹配之后都要对j重新赋值。

复杂度

kmp算法的复杂度是O(n+m)，可以采⽤均摊分析来解答，具体可参考算法导论。