Kmp字符串模式匹配算法.docx

Kmp中查找一个字符串中是否包含另外一个字符串
#iｎｃluｄe<〉
2　#ｉncｌｕdｅ〈>
3 voｉｄ makeNeｘｔ（ｃoｎst　cｈar　P[]，int neｘｔ［］）
　4 ｛
5 　 int ｑ，k；
6　 int m =　strlen（Ｐ）；
7 　neｘt［０］ = 0；
　8　 　 for　(ｑ = 1，k ＝ 0；　q ＜ ｍ；　+＋ｑ）
9 ｛
1０ 　ｗhile（k ＞ 0 &＆ P［q］ ！=　P［k]）
１1 　　 　 　 k =　next［ｋ—１］；
1２　 　　 if　（P[ｑ］ == P[ｋ］)
13 　 　｛
14 　 　 　k＋+；
15　 　 }
16　 　 　　　next[ｑ］ = k；
1７ 　 ｝
18 ｝
19
20 iｎt kmp(const ｃhar T［]，consｔ cｈaｒ P[]，int　neｘt[］）
2１ ｛
22　 　 int n,m；
２３ int i，q；
24 ｎ = ｓtｒleｎ(Ｔ）;
2５ 　 ｍ =　ｓｔｒlen(P）;
26 ｍakeNeｘt(Ｐ,neｘt);
27　 　　 for （i =　0,q = 0; i ＜ n; +＋ｉ）
28 　 {
２9 ｗhile(q 〉 ０　＆＆　P［q] != T[ｉ］）
３0 　 　　 q　=　nexｔ［q-1];
３1 　 　 if （P[q] == Ｔ［i]）
3２　 　 　 　｛
33 　 　 　 　ｑ＋+;
3４ 　 　　 　 ｝
3５ 　　 if　（ｑ == m)
36 {
3７ 　 　 　　prｉntf（”Patteｒn oｃcurs with shift：%ｄ\n",(ｉ-ｍ+1))；
38 　 　 ｝
３9 　　 　｝
４0 ｝
４1
42 int　maｉn(）
４3 ｛
4４　 　iｎt　i；
45 int next［2０]=｛０｝;
46 ｃhａr Ｔ[］ = "abａｂxbababcadfdsｓs＂;
47　 　 cｈａｒ P[］ = "aｂcdabｄ";
４8　 　 ｐrｉｎｔf（"%ｓ\ｎ”，T)；
49 priｎｔｆ（"％s\n＂,P ）；
5０ /／　makeＮext（P，ｎext）；
51 kｍp（T，P，ｎext）；
５2 　 　fｏr （i = 0； i <　stｒlen(P）; +＋i)
53　 　｛
５4 　 printf（”%d　",nｅxt［ｉ］）；
5５　 　}
5６　 　　 priｎtf（＂\n"）；
57
58 　　 returｎ 0;
59　}
　已知前一步计算时最大相同的前后缀长度为k（k>0),即P［０]···Ｐ[ｋ-1］；
此时比较第ｋ项P［k]与Ｐ［q］，如图1所示
　 如果Ｐ[K］等于P［q］，那么很简单跳出ｗｈiｌe循环;
　　关键！关键有木有!关键如果不等呢？？？那么我们应该利用已经得到的neｘt［０］···ｎexｔ[k－1]来求P[0]···Ｐ［k-1]这个子串中最大相同前后缀,可能有同学要问了——为什么要求Ｐ[0］···P[k-1]的最大相同前后缀呢？?？是啊！为什么呢? 原因在于P［k]已经和P［ｑ］失配了,而且Ｐ[ｑ—k] ··· P［q－１］又与P［0］ ···P［k—1］相同，看来P［０］···P［k-1］这么长的子串是用不了了，那么我要找个同样也是P［0]打头、P[k-1]结尾的子串即P［0]···P[j-1]（ｊ==ｎｅxt［k—1])，看看它的下一项P［j］是否能和Ｐ[ｑ］匹配。如图2所示
 
 
　 　 　 　　 　　 　 最大子序列
最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5，－3,4，2}的最大子序列就是 ｛5,—3，4,2｝，它的和是８，达到最大；而 ｛5，-6，4,2｝的最大子序列是｛4,2},它的和是６。你已经看出来了,找最大子序列的方法很简单，只要前i项的和还没有小于０那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列,同时我们要记下各个子序列的和，最后找到和最大的子序列。
代码如下:
#inｃlude<iosｔrｅam〉
us