主串與模式串的匹配
（1）BF算法：
BF算法比較簡單直觀，其匹配原理是主串S.ch[i]和模式串T.ch[j]比較，若相等，則i和j分別指示串中的下一個位置，繼續比較后續字符，若不相等，從主串S的下一個字符（i=i-j+2）起再重新和模式串T的第一個字符（j=1）比較。
?
（2）KMP算法：
KMP算法相對BF會復雜一些，但對于計算機而言，這其實是減少很多不必要的匹對。在匹配失敗時最大的移動模式串，以減少匹配次數，即當匹配失敗時（S.ch[i]!=T.ch[j]），在模式串中已匹配的字符找出其長度最長的相同前后綴，假設其長度為k，則模式串T回溯到T.ch[k+1]與S.ch[i]匹對。
| 模式串 | 前后綴 | 相同個數 |
| a | 無 | 0 |
| ab | 無 | 0 |
| aba | a | 1 |
| abab | a、ab | 2 |
| ababa | a、ab、aba | 3 |
在作業題中，我用的是KMP算法進行匹配。考慮的當模式串第一位字符與主串字符不匹配時，若按原方法回溯會陷入死循環，所以講next[0]初始為-1? ??
?
定義晚next函數后則定義KMP函數，僅需匹配時i++和j++，不匹配時i不變，j=next[j]（將模式串回溯至k）重新開始進行匹配，直至匹配完成輸出i-j+1（主串中的子串的第一個字符所在位置）
?
?
?
?
