经典算法kmp，大神级的存在

　　对于字符串匹配，如用一个长度为m的模式串去匹配一个长度为n的主串，我们可以使用暴力法（BF，BruteForce），其时间复杂度为O（mn）。
　　字符串匹配kmp算法的时间复杂度只需要O（mn）。
　　使用变量i，j表示主串s〔〕和模式串t〔〕的下标，第一轮匹配：
　　kmp算法认为，i可以不回退（BF要求退回到主串的第2个位置（第几轮就是第几个位置）），而j可以回退到第2个位置，即j2（BF要求退回到每1个字符的位置）。
　　即使使用暴力破解，几轮迭代后，也会迭代匹配到此位置，所以上述i，j的回退不影响整体结果的正确性。
　　模式串此时回退为什么是2呢？
　　看下面已匹配的公共部分：
　　主串以不匹配的位置为基准，考虑前面的字符abaab，有后缀ab与模式串abaabe最前面的字符前缀ab相等。
　　也就是模式串本身abaab，有最大后缀部分ab与最大前缀ab相等，相等字符的长度为2。
　　从上图可见，假设一个字符串长度为n，其最大前缀和后缀相等的字符数量不会超过n2，例如：
　　abcdabcd，长度为8，824，其最大前缀和后缀相等的字符串abcd最大可能的长度为4。
　　如何暴力计算下面字符的最大前缀和后缀字符串的长度L呢？
　　abcdaabbcdeabcd，长度n为15，其L不会超过n27，暴力匹配的思路可以描述为：前1个字符与后1个字符是否相等？
　　前2个字符与后2个字符是否相等？
　　前3个字符与后3个字符是否相等？
　　前n2个字符与后n2个字符是否相等？
　　暴力匹配的思路也可以描述为：
　　前n27个字符与后n27个字符是否相等？
　　abcdaabbcdeabcd
　　前n216个字符与后n216个字符是否相等？
　　abcdaabbcdeabcd
　　前n225个字符与后n225个字符是否相等？
　　abcdaabbcdeabcd
　　abcdaabbcdeabcd
　　前n234个字符与后n234个字符是否相等？
　　abcdaabbcdeabcd
　　此时相等，则L为4。
　　对于模式串abaabe，如何计算各个子串对应的最大前缀与后缀字符串数量（j回退到的位置）？
　　abaab
　　2hrabaa
　　1hraba
　　1hrab
　　0hra
　　1
　　图示：
　　对应代码：intgetNextArray（chart〔〕）动态规划｛intnstrlen（t）；intnext（int）malloc（sizeof（int）n）；next〔0〕1；next〔1〕0；intk；for（intj2；jn；j）｛knext〔j1〕；先假设while（k！1）｛if（t〔j1〕t〔k〕）｛next〔j〕k1；break；｝elseknext〔k〕；回退next〔j〕0；当k1而跳出循环时，next〔j〕0，否则next〔j〕会在break之前被赋值｝｝returnnext；｝
　　对于模式串T的下标j回退位置next〔〕的求解方法，KMP算法应用的动态规划的思想：
　　首先大胆假设next〔j〕k，则
　　那么next〔j1〕？
　　也就是以上子串再分别多考虑一个随后的字符：
　　可以区分这两个字符在相等和不等的情况下分别考虑：
　　有了确定模式串回退位置的数组，字符串匹配剩下的代码就相对较容易了。
　　democcode：includestdio。hincludemalloc。hincludestring。h对主串s和模式串t进行KMP模式匹配计算模式串t需要回退的位置（BF是回退到0）intgetNextArray（chart〔〕）动态规划｛intnstrlen（t）；intnext（int）malloc（sizeof（int）n）；next〔0〕1；next〔1〕0；intk；for（intj2；jn；j）｛knext〔j1〕；先假设while（k！1）｛if（t〔j1〕t〔k〕）｛next〔j〕k1；break；｝elseknext〔k〕；回退next〔j〕0；当k1而跳出循环时，next〔j〕0，否则next〔j〕会在break之前被赋值｝｝returnnext；｝对主串s和模式串t进行KMP模式匹配params主串paramt模式串return若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回1intkmpMatch（chars，chart）｛intnextgetNextArray（t）；inti0，j0；while（i（int）strlen（s）j（int）strlen（t））｛if（j1s〔i〕t〔j〕）｛i；j；｝elsejnext〔j〕；｝printf（ijddd，i，j，ij）；if（j（int）strlen（t））returnij；elsereturn1；｝intmain（）｛charstr〔〕｛ACBACAACAACACAACAB，ACAACAB｝；charstr〔〕｛abaabaabeca，abaabe｝；charstr〔〕｛abaabaeabaabea，abaabe｝；intnextgetNextArray（str〔1〕）；inti，j；printf（主串s〔〕）；for（i0；i（int）strlen（str〔0〕）；i）printf（c，str〔0〕〔i〕）；printf（）；for（i0；i2；i）｛printf（模式串t〔〕）；for（j0；j（int）strlen（str〔1〕）；j）printf（c，str〔1〕〔j〕）；printf（）；｝printf（next〔〕）；for（i0；istrlen（str〔1〕）；i）printf（d，next〔i〕）；intnkmpMatch（str〔0〕，str〔1〕）；printf（模式串t首次匹配到主串s的位置：d，n）；getchar（）；｝主串s〔〕abaabaabeca模式串t〔〕abaabe模式串t〔〕abaabenext〔〕100112模式串t首次匹配到主串s的位置：3主串s〔〕ACBACAACAACACAACAB模式串t〔〕ACAACAB模式串t〔〕ACAACABnext〔〕1001123模式串t首次匹配到主串s的位置：11主串s〔〕abaabaeabaabea模式串t〔〕abaabe模式串t〔〕abaabenext〔〕100112模式串t首次匹配到主串s的位置：7
　　demojavacode：classIdeone｛publicstaticint〔〕getNextArray（char〔〕t）｛int〔〕nextnewint〔t。length〕；next〔0〕1；next〔1〕0；intk；for（intj2；jt。length；j）｛knext〔j1〕；while（k！1）｛if（t〔j1〕t〔k〕）｛next〔j〕k1；break；｝else｛knext〔k〕；｝next〔j〕0；当k1而跳出循环时，next〔j〕0，否则next〔j〕会在break之前被赋值｝｝returnnext；｝对主串s和模式串t进行KMP模式匹配return若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回1publicstaticintkmpMatch（Stringsarr，Stringtarr）｛char〔〕ssarr。toCharArray（）；char〔〕ttarr。toCharArray（）；int〔〕nextgetNextArray（t）；for（inti0；it。length；i）System。out。print（next〔i〕）；inti0，j0；while（is。lengthjt。length）｛if（j1s〔i〕t〔j〕）｛i；j；｝elsejnext〔j〕；｝System。out。printf（ddd，i，j，t。length）；if（jt。length）returnij；elsereturn1；｝publicstaticvoidmain（String〔〕args）throwsjava。lang。Exception｛intnkmpMatch（ACBACAACAACACAACAB，ACAACAB）；System。out。printf（d，n）；｝｝1001123187711
　　End