假設現在我們面臨這樣一個問題：有一個文本串S，和一個模式串P，現在要查找P在S中的位置，怎么查找呢？

Ps:文本串S可以類比為一篇文章，P為其中某個單詞，查找這個單詞在文章中哪里出現過。

方法1：暴力匹配

如果用暴力匹配的思路，并假設現在文本串S匹配到 i 位置，模式串P匹配到 j 位置，則有：

如果當前字符匹配成功（即S[i] == P[j]），則i++，j++，繼續匹配下一個字符；

如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相當于每次匹配失敗時，i 回溯，j 被置為0。

方法2：kmp算法

假設現在文本串S匹配到 i 位置，模式串P匹配到 j 位置

如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++，繼續匹配下一個字符；

如果j != -1，且當前字符匹配失敗（即S[i] != P[j]），則令 i 不變，j = next[j]。此舉意味著失配時，模式串P相對于文本串S向右移動了j - next [j] 位。

換言之，當匹配失敗時，模式串向右移動的位數為：失配字符所在位置 - 失配字符對應的next 值（next 數組的求解會在下文的詳細闡述），即移動的實際位數為：j - next[j]，且此值大于等于1。

【next 數組】的含義：

代表當前字符之前的字符串中，有多大長度的相同前綴后綴。例如如果 next [j] = k ，代表j 之前的字符串中有最大長度為 k 的相同前綴后綴。意味著在某個字符失配時，該字符對應的next 值會告訴你下一步匹配中，模式串應該跳到哪個位置（跳到next [j] 的位置），如果next [j] 等于0或-1，則跳到模式串的開頭字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某個字符，而不是跳到開頭，且具體跳過了k 個字符。

按暴力匹配是這樣子滴：然而可以更快一些，直接將D和E比較 T_T

當匹配失敗時，j要移動的下一個位置k。存在著這樣的性質：最前面的k個字符和j之前的最后k個字符是一樣的。

用數學公式來表示是這樣的

P[0 ~ k-1] == P[j-k ~ j-1]

void cal_next(char *str,int *next,int len) {next[0]=-1;//-1表示不存在相同的最大前綴和最大后綴int k=-1;for(int q=1;q<len;q++){//如果下一個不同，k就變成next[k]while(k>-1&&str[k+1]!=str[q])k=next[k];//向前回溯//無論k取何值，next[k]都是小于k的if(str[k+1]==str[q]) ++k;next[q]=k;} }

有了next數組，我們就可以來進行字符串的快速匹配啦

int KMP(char *str,int slen,char *ptr,int plen) {int *next=new int[plen];cal_next(ptr,next,plen);//計算next數組int j=-1;for(int i=0;i<slen;i++){while(j>-1&&ptr[j+1]!=str[i]){//ptr和str不匹配，且j>-1,表示ptr和str有部分匹配j=next[j];//往前回溯}if(ptr[j+1]==str[i])j=j+1;if(j==plen-1)//j移動到ptr的末端return i-plen+1;}return -1; }

?

總結

以上是生活随笔為你收集整理的KMP字符串搜索算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。