知識總覽：

什么是字符串的模式匹配：

主串：想從該串獲取結果的串

模式串：想搜索的內容，不一定在主串中能搜到，子串一定能在主串中搜到

字符串模式匹配：在主串找模式串并返回找到的第一個模式串所在位置

?樸素模式匹配算法：

暴力匹配，從主串選取跟模式串長度一樣的子串去跟模式串對比，倆串相等返回首字符下標，倆串不相等繼續找，直到找到為止返回首字符下標或者找完也找不到為止。

實現方法1：Index()函數定位操作

跟上一節找主串的子串函數一樣

注意目前的串都是用的靜態數組且是數組第一個字符位置不適用的形式，即數組存儲字符的下標跟字符位序相同，且找模式串可尋找的次數為n-m+1(n為主串，m為模式串)

實現方法2：不用Index()函數定位，使用指針

?第一輪：

設置2個掃描指針，分別掃描主串和模式串，指針指到哪則2個串的字符比較到哪，開始i和j分別指向主串S和模式串T的下標為1的第一個字符，分別為a和a即相等，則倆指針后移指向下標為2的第2個字符，都為b繼續后移，來指針都指向第3個字符a都相等，繼續后移指向第4個字符a相等，繼續后移指向第5個字符都為b相等，繼續后移此時倆指針都指向第6個字符，i指向主串S的a，j指向模式串的T的c，則倆字符不相等，指向主串的指針i回到指向下一個子串的第一個位置，即主串S的第2個字符位置，指向模式串的指針j回到模式串的第一個位置

i=i-j+2；//即此時i=6,j=6，下一輪i=i-j+2=2

//倆指向字符不相等時，j當前的值表示匹配到了子串的第幾個字符，i-j就可以讓i的值回到目前這個子串的前邊一個位置，i和j都是統一往前移的，因為指針i要指向下一個子串的第一個位置，所以要在此基礎上+2，如下圖現在j指向了當前子串的第6個字符,i=6,j=6,i=i-j=0即i回到了這個子串的前邊一個位置(注意是當前子串的前邊一個位置，不是當前子串的第一個位置，這意味著要指向下一個子串的第一個位置要+2，因為+1就又指向當前子串的第一個位置了)，然后還要刨除這個子串的第一個位置指向下一個字串的第一個位置，則要i=i+2=2

j=1；//即此時j=6,下一輪j=1，j指向模式串起始位置

第2輪：?

i的值恢復為2即i==2，j的值恢復為1即j==1，倆指針指向的值為b和a不相等，即i指向的當前子串和模式串不相等，則i=i-j=2-1=1即i回到當前子串b的前一個位置，i=i+2=3為指向下一個子串的第一個位置，指向模式串T的指針j回到模式串第一個位置即j==1

i=i-j+2；//即此時i=2,j=1，下一輪i=i-j+2=2-1+2=3

j=1；//即此時j=6,下一輪j=1，j指向模式串起始位置

?

第3輪：

上同，i從第3個字符開始的子串和j=1開始的模式串比較，每當發現i和j所指的字符相同的時候，讓i和j分別+1，當i==4，j==2時不相等，i回到下一個子串的第一個位置，j回到起始位置

i=i-j+2；//即此時i=4,j=2，下一輪i=i-j+2=4-2+2=4

j=1；//即此時j=2,下一輪j=1，j指向模式串起始位置

?

第4輪：

每當發現i和j所指的字符相同的時候，讓i和j分別+1，當j所指的位置超出了模式串的長度，就說明匹配成功，則返回當前子串的第一個字符位置即讓i-j即可，注意沒有+1，因為在匹配成功的時候i和j都已經往前移動了1個位置，所以當i-j的時候其實指向的位置為當前子串的第一個字符位置

?

代碼版：

2個指針i和j，i指向主串，j指向模式串，初始值都為1即指向主串和模式串的第一個字符，如下while循環

if(S.ch[i]==T.ch[j]); ++i;++j；即當前2個指針指向的字符相等，讓i和j都+1

i=i-j+2;j=1；即當前2個指針指向的字符不相等則讓i回到下一個子串的第一個字符位置，j回到模式串第1個位置

return i-T.length；如果匹配成功，則說明j>T.length，已跳出while循環

return 0;；即匹配失敗，即i已經把整個主串走了一遍，即在走到主串的最后一個字符時，不相等，i的下一輪下標為S.length+1（我怎么感覺S.length要比實際的字符個數多1個，因為S數組中存儲的第一個位置沒有存元素啊，比說最后一個字符index=3,實際S.length=4吧，那下一個位置i不就是4嗎，那這個while循環不是還能走一遍嗎，但是走的話if第一個語句就數組下標越界了吧。。。。。。。。。。。。。。。。）

?

最壞時間復雜度：

假如有如下長度為n的主串，長度為m的模式串，子串和模式串匹配的時候每次只有最后一個字符不相等，且主串n只有在最后一個m長度的子串中才和模式串匹配，即要總共匹配n-m+1次，每次都要匹配m個長度，則時間開銷為(n-m+1)m=nm-m2+m，即時間開銷為O(nm)，因為一般n>>m，所以把m2舍去

?

?知識回顧：

。。。。。。。。。。。。。。。?