1.樸素算法
2.RK算法
3.kmp算法
詳細(xì)講解:
主要在于搜索字符串相對(duì)原字符串需要后移多少位.對(duì)比字符串與搜索字符串的第一個(gè)字符，若不相同，則講搜索字符串向后移一位.若相同則對(duì)比兩者的第二個(gè)字符串.當(dāng)移動(dòng)到第n個(gè)字符時(shí),發(fā)現(xiàn)不相同，這是需要就算出部分匹配表,目的在于決定將搜索字符串后移多少位,若還是按老規(guī)矩只向后移一位,其實(shí)是效率低下的一種做法.因?yàn)榇藭r(shí)已經(jīng)知道前n-1個(gè)字符是什么了.
至于如何計(jì)算部分匹配表,與字符串前綴 后綴有關(guān)系.前綴和后綴字符串最長(zhǎng)的共同的字符個(gè)數(shù)就是該字符的部分匹配值.

kmp.png

4.BM算法
5.Sunday算法