1惕蹄、BF算法
假設現(xiàn)有一字符串，“BBC ABCDAB ABCDABCDABDE”將其稱為給定串抬闯，相應有一匹配串“ABCDABD”呼巴。
兩個串的第一個字母先相互比較:
可得第一個字符不相同，則繼續(xù)向后比較患民，直到比較到第一個字符相同缩举，如下圖：
然后繼續(xù)比較，直到發(fā)現(xiàn)給定串中的字符與匹配串中的不同，這時BF算法的思想是將匹配串與給定串的當前位置的下一位進行比較仅孩，這會導致很多重復比較托猩，時間復雜度到達O（n*m）,n代表給定串的長度，m代表匹配串的長度辽慕。
2京腥、KMP算法
此種算法，后面需要用到部分匹配表溅蛉，所以先講一下部分匹配表公浪。我們都知道前綴就是一個字符串中除了最后一個字符之外的所有字符組合，后綴是一個字符串中除了第一個字符之外的所有字符的組合船侧。
以匹配串“ABCDABD”為例欠气，"A"的前綴和后綴都為空集，共有元素的長度為0镜撩； "AB"的前綴為[A]预柒，后綴為[B]，共有元素的長度為0袁梗；"ABC"的前綴為[A, AB]宜鸯，后綴為[BC, C]，共有元素的長度0遮怜；"ABCD"的前綴為[A, AB, ABC]淋袖，后綴為[BCD, CD, D]，共有元素的長度為0锯梁；"ABCDA"的前綴為[A, AB, ABC, ABCD]即碗，后綴為[BCDA, CDA, DA, A]，共有元素為"A"涝桅，長度為1拜姿；"ABCDAB"的前綴為[A, AB, ABC, ABCD,ABCDA]烙样，后綴為[BCDAB, CDAB, DAB, AB, B]冯遂，共有元素為"AB"，長度為2谒获；"ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]蛤肌，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0批狱。因此裸准，可以得到匹配串的部分匹配表:
此種算法前半部分和BF算法一樣，都是從第一個字符開始比較赔硫，然直到找到與匹配串第一個字符相匹配的位置炒俱，然后再繼續(xù)比較，直到與給定串不匹配，此時权悟，KMP的做法是通過部分匹配表來進行移位砸王，有公式：移動位數(shù) = 已匹配的字符數(shù) - 對應的部分匹配值（已匹配字符的最后一個字符）。
以到達此步為例：已匹配的字符數(shù)為6峦阁，B的部分匹配值為2谦铃，所以移動6-2=4位，到如下:
此時移動2-0=2位榔昔，到如下:
此時移動1位驹闰，到如下:
此時移動6-2=4位，到如下：
達到完美匹配撒会，此時如果還想找出字符串的全部匹配串嘹朗，則移動7-0=7位。
時間復雜度是O（n+m）茧彤。
3骡显、Boyer-Moore算法
（暫且不管壞字符和好后綴的定義，后文介紹）
壞字符規(guī)則：移動為數(shù) = 壞字符的位置 - 匹配串中上一次出現(xiàn)的位置（若壞字符不出現(xiàn)在匹配串中曾掂，則上一次出現(xiàn)位置為-1）
好后綴規(guī)則：移動為數(shù) = 好后綴的位置（以好后綴最后一個位置為準） - 匹配串中上一次出現(xiàn)的位置（若好后綴在匹配串中不重復出現(xiàn)惫谤，則上一次出現(xiàn)位置為-1）
假設現(xiàn)有一字符串，“HERE IS A SIMPLE EXAMPLE”將其稱為給定串珠洗，相應有一匹配串“EXAMPLE”溜歪。
先從尾部開始比較，可以看到S與E不匹配许蓖，則將S稱為壞字符蝴猪，此時用壞字符規(guī)則，則移動為數(shù)為6-（-1）=7位膊爪，得到如下：
此時用壞字符規(guī)則自阱，則移動為數(shù)為6 - 4=2位，得到如下：
此時的MPLE,PLE,LE,E都稱為好后綴米酬，此時用好后綴規(guī)則沛豌，則移動為數(shù)為6 - 0 = 6位，得到：
此時用壞字符規(guī)則赃额，則移動為數(shù)為6 - 4 = 2位加派，得到：
此時達到完美匹配，如果還想找出字符串的全部匹配串跳芳，則移動6-0=6位芍锦。
end。
