假設(shè)現(xiàn)在我們面臨這樣一個問題:有一個文本串 S,和一個模式串 P,現(xiàn)在要查找 P 在 S 中的位置,怎么查找呢?
如果用暴力匹配的思路,并假設(shè)現(xiàn)在文本串 S 匹配到 i 位置,模式串 P 匹配到 j 位置,則有:
理清楚了暴力匹配算法的流程及內(nèi)在的邏輯,咱們可以寫出暴力匹配的代碼,如下:
int ViolentMatch(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{
if (s[i] == p[j])
{
//①如果當(dāng)前字符匹配成功(即S[i] == P[j]),則i++,j++
i++;
j++;
}
else
{
//②如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0
i = i - j + 1;
j = 0;
}
}
//匹配成功,返回模式串p在文本串s中的位置,否則返回-1
if (j == pLen)
return i - j;
else
return -1;
}
舉個例子,如果給定文本串 S“BBC ABCDAB ABCDABCDABDE”,和模式串 P“ABCDABD”,現(xiàn)在要拿模式串 P 去跟文本串 S 匹配,整個過程如下所示:
1.S[0] 為 B,P[0] 為 A,不匹配,執(zhí)行第 ② 條指令:“如果失配(即 S[i]! = P[j]),令 i = i - (j - 1),j = 0”,S[1] 跟 P[0] 匹配,相當(dāng)于模式串要往右移動一位(i=1,j=0)
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/1.png" alt="" />
2.S[1] 跟 P[0] 還是不匹配,繼續(xù)執(zhí)行第 ② 條指令:“如果失配(即 S[i]! = P[j]),令 i = i - (j - 1),j = 0”,S[2] 跟 P[0] 匹配(i=2,j=0),從而模式串不斷的向右移動一位(不斷的執(zhí)行“令 i = i - (j - 1),j = 0”,i 從 2 變到 4,j 一直為 0)
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/2.png" alt="" />
3.直到 S[4] 跟 P[0] 匹配成功(i=4,j=0),此時按照上面的暴力匹配算法的思路,轉(zhuǎn)而執(zhí)行第 ① 條指令:“如果當(dāng)前字符匹配成功(即 S[i] == P[j]),則 i++,j++”,可得 S[i] 為 S[5],P[j] 為 P[1],即接下來 S[5] 跟 P[1] 匹配(i=5,j=1)
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3.png" alt="" />
4.S[5] 跟 P[1] 匹配成功,繼續(xù)執(zhí)行第 ① 條指令:“如果當(dāng)前字符匹配成功(即 S[i] == P[j]),則 i++,j++”,得到 S[6] 跟 P[2] 匹配(i=6,j=2),如此進(jìn)行下去
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/4.png" alt="" />
5.直到 S[10] 為空格字符,P[6] 為字符 D(i=10,j=6),因?yàn)椴黄ヅ?,重新?zhí)行第 ② 條指令:“如果失配(即 S[i]! = P[j]),令 i = i - (j - 1),j = 0”,相當(dāng)于 S[5] 跟 P[0] 匹配(i=5,j=0)
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/5.png" alt="" />
6.至此,我們可以看到,如果按照暴力匹配算法的思路,盡管之前文本串和模式串已經(jīng)分別匹配到了 S[9]、P[5],但因?yàn)?S[10] 跟 P[6] 不匹配,所以文本串回溯到 S[5],模式串回溯到 P[0],從而讓 S[5] 跟 P[0] 匹配。
http://wiki.jikexueyuan.com/project/kmp-algorithm/images/6.png" alt="" />
而 S[5] 肯定跟 P[0] 失配。為什么呢?因?yàn)樵谥暗?4 步匹配中,我們已經(jīng)得知 S[5] = P[1] = B,而 P[0] = A,即 P[1] != P[0],故 S[5] 必定不等于 P[0],所以回溯過去必然會導(dǎo)致失配。那有沒有一種算法,讓 i 不往回退,只需要移動 j 即可呢?
答案是肯定的。這種算法就是本文的主旨 KMP 算法,它利用之前已經(jīng)部分匹配這個有效信息,保持 i 不回溯,通過修改 j 的位置,讓模式串盡量地移動到有效的位置。