傳統(tǒng)的字符串模式匹配算法（也就是BF算法）就是對(duì)于主串和模式串雙雙自左向右，一個(gè)一個(gè)字符比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的算法時(shí)間復(fù)雜度為O（n＊m），其中n和m分別為串s和串t的長(zhǎng)度。
KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt算法，簡(jiǎn)稱KMP算法。KMP算法是字符串模式匹配中的經(jīng)典算法。和BF算法相比，KMP算法的不同點(diǎn)是匹配過(guò)程中，主串的位置指針不會(huì)回溯，這樣的結(jié)果使得算法時(shí)間復(fù)雜度只為O（n＋m）。下面說(shuō)說(shuō)KMP算法的原理。
假設(shè)我們有個(gè)模式串為“abdabcde”存于數(shù)組t，我們要求的就是模式串的next值，見下表所示：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| t[i] | a | b | d | a | b | c | d | e |
| next[i] | -1 | 0 | 0 | 0 | 1 | 2 | 0 | 0 |
求模式t的next[i]（稱為失效函數(shù)）的公式如下：
next[i] =
( 上面的公式中非t字母和數(shù)字組成的為數(shù)組下標(biāo))
應(yīng)該如何理解next數(shù)組呢？在匹配過(guò)程中，如果出現(xiàn)不匹配的情況（當(dāng)前模式串不匹配字符假定為t[i]），它所對(duì)應(yīng)的next[i]的數(shù)值為接下來(lái)要匹配的模式串的字符的索引；也就是說(shuō)，出現(xiàn)不匹配的情況時(shí)，模式串的索引指針要回溯到中next[i]所對(duì)應(yīng)的位置，而主串的索引指針保持不變。
特別的，next數(shù)組中的next[0]和next[1]的取值是固定的，為了標(biāo)識(shí)出首字母，需要假定next[0]為－1（取為－1是考慮到C語(yǔ)言中的數(shù)組索引以0開始）。在實(shí)現(xiàn)的時(shí)候，要實(shí)現(xiàn)公式中情況的處理需要些技巧，下面給出具體的實(shí)現(xiàn)：
#include <stdlib.h>
typedef struct QString {
char * cs;
int len;
}String;
void GetNext(String s , int next []){
int len = s . len;
int i = 0 ;
int k = - 1 ;
next [ 0 ] = - 1 ;
while (i < len - 1 ){
if (k ==- 1 || s . cs[i] == s . cs[k]){
i ++ ;
k ++ ;
next [i] = k;
} else {
k = next [k];
}
}
}
int KMPIndex(String s , String m){
int next [m . len] , i = 0 , j = 0 ;
int k;
GetNext(m , next );
while (i < s . len && j < m . len){
if (j ==- 1 || s . cs[i] == m . cs[j]){
i ++ ;
j ++ ;
} else {
j = next [j];
}
}
if (j >= m . len) return i - m . len;
else return - 1 ;
}
KMP 算法也有需要改進(jìn)的地方。對(duì)于模式串“aaaadd”在匹配時(shí)（假定被匹配串為“aaadddd”），可以看到，在匹配到索引3時(shí)，主串字符為“d”，模式串字符為“a”，如果按照上面的做法，這時(shí)模式串只會(huì)回溯一個(gè)索引，由于仍不匹配，模式串還會(huì)回溯一個(gè)索引，直到索引位置到了首字符，主串的索引指針才會(huì)前進(jìn)一位，這樣就會(huì)浪費(fèi)一些不必要的比較時(shí)間。出現(xiàn)這種情況的原因是模式串中位置i的字符與next[i]對(duì)應(yīng)的字符相同，需要修正next[i]為next[i]對(duì)應(yīng)的字符的索引。下面列出“aaaadd”修正的nextval數(shù)組的內(nèi)容：
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| t[i] | a | a | a | a | d | d |
| next[i] | -1 | 0 | 1 | 2 | 3 | 0 |
| nextval[i] | -1 | -1 | -1 | -1 | 0 | 0 |
修正函數(shù)如下：
int len = s . len , i = 0 , k = - 1 ;
nextval[ 0 ] = - 1 ;
while (i < len - 1 ){
if (k ==- 1 || s . cs[i] == s . cs[k]){
i ++ ;
k ++ ;
if (s . cs[i] != s . cs[k]){
nextval[i] = k;
} else nextval[i] = nextval[k];
} else {
k = nextval[k];
}
}
}
謝謝某人的程序：）
public class CyclicExe
{
private int[] next=null;
CyclicExe()
{
}
public static void main(String[] args)
{
CyclicExe c=new CyclicExe();
StringBuffer mainString=new StringBuffer("abbabbbaaaaaccd");
StringBuffer oldString=new StringBuffer("abc");
String newString=new String("mmm");
c.initial(oldString);
int pos=0;
int index=0;
while(pos<mainString.length()){
index=c.findIndex(mainString, oldString, pos);
if(index!=0){
mainString.replace(pos, pos+oldString.length()-1, newString);
pos=pos+oldString.length();
}
}
}
void initial(StringBuffer oldString)
{
next=new int[oldString.length()];
int i=1;
next[1]=0;
int j=0;
while(i<oldString.length()){
if(j==0||oldString.charAt(i)==oldString.charAt(j)){
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int findIndex(StringBuffer mainString,StringBuffer oldString,int pos)
{
int i=pos;
int j=1;
while(i<mainString.length()&&j<oldString.length())
{
if(j==0||mainString.charAt(i)==oldString.charAt(j)) {
i++;
j++;
}
else
j=next[j];
}
if(j>oldString.length()) return i-oldString.length();
else return 0;
}
}
