极简源码分享网站，简约源码

这篇文章给大家聊聊关于极简源码分享网站，以及简约源码对应的知识点，希望对各位有所帮助，不要忘了收藏本站哦。

【算法图文动画详解系列】KMP字符串查找算法（Knuth-Morris-Pratt）

问题描述：字串匹配搜索

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

暴力匹配算法

如果用暴力匹配的思路，并假设现在文本串S匹配到i位置，模式串P匹配到j位置，则有：

1、如果当前字符匹配成功（即S[i]==P[j]），则i++，j++，继续匹配下一个字符；

2、如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0。相当于每次匹配失败时，i回溯，j被置为0。

理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：

intViolentMatch(char*s,char*p)\n{\nintsLen=strlen(s);\nintpLen=strlen(p);\n\ninti=0;\nintj=0;\nwhile(i<sLen&&j<pLen)\n{\nif(s[i]==p[j])\n{\n//①如果当前字符匹配成功（即S[i]==P[j]），则i++，j++\ni++;\nj++;\n}\nelse\n{\n//②如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0\ni=i-j+1;\nj=0;\n}\n}\n//匹配成功，返回模式串p在文本串s中的位置，否则返回-1\nif(j==pLen)\nreturni-j;\nelse\nreturn-1;\n}\n

KMP算法

Knuth-Morris-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串P的出现位置，这个算法由DonaldKnuth、VaughanPratt、JamesH.Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

ThealgorithmofKnuth,MorrisandPratt[KMP77]makesuseoftheinformationgainedbyprevioussymbolcomparisons.Itneverre-comparesatextsymbolthathasmatchedapatternsymbol.Asaresult,thecomplexityofthesearchingphaseoftheKnuth-Morris-PrattalgorithmisinO(n).However,apreprocessingofthepatternisnecessaryinordertoanalyzeitsstructure.ThepreprocessingphasehasacomplexityofO(m).Sincemlessorequaln,theoverallcomplexityoftheKnuth-Morris-PrattalgorithmisinO(n).

KMP算法核心原理示意图

KMP算法原理详解视频：

算法图文详解：

求解前缀表next[]的核心思想

把前缀P[0:j]当成是P的模式串（P[0:i]），P本身当成是查找的文本。

next[]:前缀表数组，上图中是lps数组。

KMP算法源代码

极简版本的KMP算法源代码：

next数组首位用-1来填充，这样在处理长度的时候，思维上不会很绕。

/**\n*getNext(pattern)函数:计算字符串pattern的最大公共前后缀的长度(maxcommonprefixsuffixlength)\n*/\nfungetNext(P:String):IntArray{\nvalM=P.length\nvalnext=IntArray(M+1,{-1})\n//i:currentindexofP\nvari=0\n//j:currentindexofthelongestprefixofP\nvarj=-1\nnext[0]=-1//next[i]=j\n\n//computenext[i]\nwhile(i<M){\n//如果当前字符匹配失败（即P[i]!=P[j]）&&j!=0，则令i不变，j=next[j]。\n//此举意味着失配时，&34;即前缀P[0:j],不再从0位置开始比对,直接从j=next[j]位置开始比对。\nwhile(j>=0&&P[i]!=P[j]){\nj=next[j]\n}\ni++\nj++\nnext[i]=j\n}\nreturnnext\n}\n\n\n/**\n*kmpsubstringsearchalgorithm\n*@paramS:thesourcetextstring\n*@paramP:thesearchpatternstring\n*/\nfunkmp(S:String,P:String):Int{\nvalN=S.length\nvalM=P.length\n\nif(P.isEmpty()){\nreturn0\n}\n\n//j:thecurrentindexofP\nvarj=0\n//i:thecurrentindexofT\nvari=0\n//nextarray\nvalnext=getNext(P)\n\nwhile(i<N){\nwhile(j>=0&&S[i]!=P[j]){\nj=next[j]\n}\ni++\nj++\n//whenj==M,thenpatternisfoundedintext,returntheindex(i-j)\nif(j==M){\nreturni-j\n}\n}\nreturn-1\n}\n\nfunmain(){\nvartext=&34;\nvarpattern=&34;\nprint(&34;)\n\nvarindex=kmp(text,pattern)\nprintln(&34;)\n\ntext=&34;\npattern=&34;\nprint(&34;)\n\nindex=kmp(text,pattern)\nprintln(&34;)\n\ntext=&34;\npattern=&34;\nprint(&34;)\n\nindex=kmp(text,pattern)\nprintln(&34;)\n\n}\n\n//输出:\n//-1,0,1,0,0,0,1,2,3\n//aabbcaabisthesubstringofaddaabbcaabffffggghhddabcdaaabbbaab,theindexis:3\n//-1,0,1\n//llisthesubstringofhello,theindexis:2\n//-1,0,1,0,1,2,0,1,0\n//aabaacabisthesubstringofabbbbbbcccddddaabaacabdcddaabbbbaad,theindexis:14\n

另外一个版本代码：

/**\n*getNext(pattern)函数:计算字符串pattern的最大公共前后缀的长度(maxcommonprefixsuffixlength)\n*/\nfungetNext(P:String):IntArray{\n\nvalM=P.length\nvalnext=IntArray(M,{-1})\n\n//i:currentindexofP\nvari=1\n//j:currentindexofthelongestprefixofP\nvarj=0\n\nnext[0]=0\n//computenext[i]\nwhile(i<M){\nif(P[i]==P[j]){//①\nvallen=j+1\nnext[i]=len\ni++\nj++\n}else{\n//如果当前字符匹配失败（即P[i]!=P[j]）&&j!=0，则令i不变，j=next[j-1]。\n//此举意味着失配时，&34;即前缀P[0:j],不再从0位置开始比对,直接从next[j-1]位置开始比对。\nif(j!=0){\nj=next[j-1]//jshiftleft,jmp①\n}else{\nnext[i]=0//nowjis0,nexti\ni++\n}\n}\n}\n\nreturnnext\n}\n\n\n/**\n*kmpsubstringsearchalgorithm\n*@paramS:thesourcetextstring\n*@paramP:thesearchpatternstring\n*/\nfunkmp(S:String,P:String):Int{\nvalN=S.length\nvalM=P.length\n\nif(P.isEmpty()){\nreturn0\n}\n\n//j:thecurrentindexofP\nvarj=0\n//i:thecurrentindexofT\nvari=0\n//nextarray\nvalnext=getNext(P)\n\nwhile(i<N-M+1){\nif(S[i]==P[j]){\ni++\nj++\n}else{\nif(j>0){\n//当前字符匹配失败（即S[i]!=P[j]），则令i不变，j=next[j-1]。\n//此举意味着失配时，模式串P不再从0位置开始比对,直接从next[j-1]位置开始比对。\nj=next[j-1]\n}else{\ni++\n}\n}\n\n//whenj==M,thenpatternisfoundedintext\nif(j==M){\nreturni-M\n}\n}\n\nreturn-1\n}\n\nfunmain(){\nvartext=&34;\nvarpattern=&34;\nprint(&34;)\n\nvarindex=kmp(text,pattern)\nprintln(&34;)\n\ntext=&34;\npattern=&34;\nprint(&34;)\n\nindex=kmp(text,pattern)\nprintln(&34;)\n\ntext=&34;\npattern=&34;\nprint(&34;)\n\nindex=kmp(text,pattern)\nprintln(&34;)\n\n}\n\n//输出:\n//0,1,0,0,0,1,2,3\n//aabbcaabisthesubstringofaddaabbcaabffffggghhddabcdaaabbbaab,theindexis:3\n//0,1\n//llisthesubstringofhello,theindexis:2\n//0,1,0,1,2,0,1,0\n//aabaacabisthesubstringofabbbbbbcccddddaabaacabdcddaabbbbaad,theindexis:14\n\n

参考资料

https://www.inf.hs-flensburg.de/lang/algorithmen/pattern/kmpen.htmhttps://blog.csdn.net/v_july_v/article/details/7041827

好了，本文到此结束，如果可以帮助到大家，还望关注本站哦！