char? ? cStr[] = "abc";串長為3 數(shù)組的長度為4（應(yīng)為有個'\0'）
串的存儲結(jié)構(gòu) ，對于我來說怎么都不會定義一個數(shù)據(jù)結(jié)構(gòu)屿愚，書上這么說溉箕，就多寫一遍加深記憶
typedef struct str
{
? ? ? ? int? ? str[maxSize+1];
? ? ? ? int? ? nLength;
}str;
或者
typedef struct str
{
? ? ? ? char *ch;
? ? ? ? int? ? nLength;
}str;
KMP算法
????????這個真是拒炎，看了別人的書感覺寫的怪怪的，不符合自己的思維方式择葡〗粑洌看視頻，知道怎么用敏储，怎么寫阻星，還是感覺自己的理論并沒有那么清晰，所以還是自己整理一下已添，加深印象妥箕。以前對這些算法不太重視，真看進(jìn)去感覺還是挺有意思的更舞。
?如在a b a b c a b c a c b a b查找是否有a b a b a b b
? ? 術(shù)語：
? ? 1畦幢、模式匹配：對一個串中某子串的定位操作
? ? 2、模式串：待定位的子串缆蝉，既（a b a b a b b?）
普通匹配比較宇葱，挨個比較會比較慢，如下圖
? p1? ? ? ? ? ? ? a b a b???? c ????a b c a c b a b
? ?p2? ? ? ? ? ? ?a b a b???? a ????b b?
當(dāng)開始比較的的時候abab都相等刊头，到c處才發(fā)現(xiàn)不等黍瞧，這時p2需從頭開始與p1的b處開始的地方進(jìn)行比較，即：
? p1? ? ? ? ? ? ? a b a b c a b c a c b a b? ? ?
? p2? ? ? ? ? ? ? ? ?a b a b a b b?
依次類推原杂，知道查到有子串或者沒有子串與模式串完全相等
KMP算法
? p1? ? ? ? ? ? ? a b a b?????c?????a b c a c b a b? ?
? p2? ? ? ? ? ? ? a b a b?????a?????b b?
當(dāng)p1雷逆，p2在不等的位置，p2往后移污尉，與p1匹配的過程中，有些步驟完全可以省略掉往产，如在p2總被碗，只看a前面的字母，即下圖加粗的地方
? ?p1? ? ? ? ? ? ? a b a b?????c?????a b c a c b a b? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）? ? ? ? ? ? ? ??
? ?p2? ? ? ? ? ? ??a b a b?????a?????b b? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）?
? ? ? p2? ? ? ? ? ? ? a b a? ? ? b???? a b b? ?（p2往后移了1個位置）? ? ? ? ? （3）
? ?????????p2? ? ? ? ? ? a b? ? ? a???? b a b b? ?（p2往后移了2個位置）? ? ? （4）
????????????會發(fā)現(xiàn)仿村，并不是所有的字符都匹配p1總的前面的字符都匹配锐朴，例如（3）。如果能從（2）直接跳躍到（4）蔼囊，然后對下圖（1）和（4）中的c和a進(jìn)行比較則能夠省去很多步驟焚志。
? ?p1? ? ? ? ? ? ??a b a b?????c?????a b c a c b a b? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）? ?
? ?????????p2? ? ? ? ? ??a b? ? ? a???? b a b b? ?（p2往后移了2個位置）?? ? ? （4）
怎樣才能保證從（2）跳到（4）呢衣迷，這里，必須保證（4）中a前加黑的地方相等與（2）中p2的a前面的加黑部分酱酬，以為如果加黑的部分不相等壶谒，根本就走不到（4）的? ? a? ? 處，也就無從談匹配了膳沽。其實也就是說abab這四個字母汗菜，前面的順序ab必須等于后面的ab。
? ?p2? ? ? ? ? ? ??a b a b?????a?????b b? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）?
? ?????????p2? ? ? ? ? ??a b? ? ??a???? b a b b? ?（p2往后移了2個位置）?? ? ? （4）?
{
? ? ? ? 附錄：
? ? ? ? ? ? ? ? 最長公共前后綴的求法挑社，如a b a b a b b陨界，下面所有的例子也拿書上這一串代碼做說明
? ? ? ? ? ? ? ? 前綴? ? ? ? ? ? ? ? 公共前后綴? ? ? ? 長度
? ? ? ? ? ? ? ? a? ? ? ? ? ? ? ? ? ? ? ? 無? ? ? ? ? ? ? ? ? ? ? ? ?0
? ? ? ? ? ? ? ? ab? ? ? ? ? ? ? ? ? ? ? ?無? ? ? ? ? ? ? ? ? ? ? ? 0
? ? ? ? ? ? ? ? aba? ? ? ? ? ? ? ? ? ? a? ? ? ? ? ? ? ? ? ? ? ? ? ?1
? ? ? ? ? ? ? ? ab?ab? ? ? ? ? ? ? ? ? ?ab? ? ? ? ? ? ? ? ? ? ? ?2（加粗部分上這一串字符前后最長相等的字符串，其長度為2）
? ? ? ? ? ? ? ? ababa? ? ? ? ? ? ? ? ?aba? ? ? ? ? ? ? ? ? ? ? 3
? ? ? ? ? ? ? ? ababab? ? ? ? ? ? ? ? abab? ? ? ? ? ? ? ? ? ?4
我們把公共前后綴的長度+1（為啥要+1呢痛阻，一位前面的都匹配了菌瘪，做的是+1位置與當(dāng)前主串位置匹配的地方的比較），保存到數(shù)組next[]中阱当，改數(shù)組從next[1] = 0開始俏扩，也就是
next[]數(shù)組中從1-7分別保存了0,1,1,2,3,4,5。
}
其實求出next[]的信息斗这，也就把kmp算法最難得部分解決了动猬，其他的就是根據(jù)next[]做相應(yīng)的比較運(yùn)算。
KMP算法的改進(jìn)
{
????????????????對于字符串a(chǎn) a a a a b
? ? ? ? ? ? next[]的信息為0 1 2 3 4 5?
列出來如下表
字符串????????a? ? a? ? a? ? a? ? a? ? b
????j? ? ? ? ? ? ? 1? ? 2? ? 3? ? 4? ? 5? ? ?6
?next[ j ]? ? ? ?0? ?1? ? ?2? ? 3? ? 4? ? 5(j的值就是上面加粗的對應(yīng)的表箭，next[6] == 5赁咙，next[2] == 1)
根據(jù)kmp算法，如果在b處發(fā)生不匹配免钻，這返回next[6]處彼水，即j=5處與字母a進(jìn)行比較，如果又發(fā)生不匹配极舔，這返回到next[5],即j=4處進(jìn)行比較凤覆；如果又發(fā)生不匹配，這返回到next[4],即j=3處進(jìn)行比較拆魏，依次盯桦，知道next[j]==0或者找到發(fā)生匹配的地方。
這里我們會發(fā)現(xiàn)另外一個問題渤刃，如果在j=5處與字母a不匹配拥峦，則相應(yīng)的與j=4處的字母a也不發(fā)生匹配，這樣分析的話卖子，我們在kmp的時候多做了很多的無用功略号，所以呢，我們可以作為改進(jìn)，求另外一個nextval[]數(shù)組玄柠，來知道算法比較的時候跳躍到的地方突梦。
字符串????????a? ? b? ? a? ? b? ? a? ? a? ? b?
????j? ? ? ? ? ? ? ?1? ? 2? ? 3? ? 4? ? 5? ? ?6? ?7?
?next[?j?]? ? ? ?0? ? 1????1? ? 2? ? 3? ? 4? ? 2?
nextval[ j ]? ? 0? ? 1? ? 0? ? 1? ? 0? ? 4? ? 1
j=2對應(yīng)的nextval[2]的值為1是怎么來的呢：在j=2處如果發(fā)生不匹配，根據(jù)kmp算法首先跳到next[ 2 ],即j=1的地方進(jìn)行匹配羽利，這時我們發(fā)現(xiàn)j=1對應(yīng)的是字母a宫患，因為a不等于b，所以給nextval賦值為j铐伴，即為1（加粗的地方就是要賦值給nextval的值）撮奏。
j=2對應(yīng)的nextval[3]的值為0是怎么來的呢 :
在j=3處如果發(fā)生不匹配，根據(jù)kmp算法首先跳到next[ 3],即j=1的地方進(jìn)行匹配当宴，這時我們發(fā)現(xiàn)j=1對應(yīng)的是字母a畜吊，因為a==a，發(fā)現(xiàn)相同户矢，這時候nextval[ 3 ]的值=nextval[ 1 ]的值玲献，即為0。
j=6對應(yīng)的nextval[6]的值為4是怎么來的呢 ： 在j=6處如果發(fā)生不匹配梯浪，根據(jù)kmp算法首先跳到next[ 6],即j=4的地方進(jìn)行匹配捌年，這時我們發(fā)現(xiàn)j=4對應(yīng)的是字母b，因為a挂洛！=b礼预，這時候nextval[ 6 ]的值等于j的值，即為4虏劲。?
就這么來的……不寫了……算出這些玩意托酸，其他的就沒意思了。
發(fā)現(xiàn)自己寫的估計除了我看柒巫，比人看更蛋疼励堡。
}
