設有主串s和子串t，子串t定位是指在主串s中找到一個與子串t相等的子串。通常把主串s稱為目標串，把子串t稱為模式串，因此定位也稱作模式匹配。模式匹配成功是指在目標串s中找到一個模式串t。

        傳統的字符串模式匹配算法（也就是BF算法）就是對于主串和模式串雙雙自左向右，一個一個字符比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的算法時間復雜度為O（n＊m），其中n和m分別為串s和串t的長度。

        KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt算法，簡稱KMP算法。KMP算法是字符串模式匹配中的經典算法。和BF算法相比，KMP算法的不同點是匹配過程中，主串的位置指針不會回溯，這樣的結果使得算法時間復雜度只為O（n＋m）。下面說說KMP算法的原理。

假設我們有個模式串為“abdabcde”存于數組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]（稱為失效函數）的公式如下：

next[i] =

( 上面的公式中非t字母和數字組成的為數組下標)

        應該如何理解next數組呢？在匹配過程中，如果出現不匹配的情況（當前模式串不匹配字符假定為t[i]），它所對應的next[i]的數值為接下來要匹配的模式串的字符的索引；也就是說，出現不匹配的情況時，模式串的索引指針要回溯到中next[i]所對應的位置，而主串的索引指針保持不變。

        特別的，next數組中的next[0]和next[1]的取值是固定的，為了標識出首字母，需要假定next[0]為－1（取為－1是考慮到C語言中的數組索引以0開始）。在實現的時候，要實現公式中情況的處理需要些技巧，下面給出具體的實現：

        KMP 算法也有需要改進的地方。對于模式串“aaaadd”在匹配時（假定被匹配串為“aaadddd”），可以看到，在匹配到索引3時，主串字符為“d”，模式串字符為“a”，如果按照上面的做法，這時模式串只會回溯一個索引，由于仍不匹配，模式串還會回溯一個索引，直到索引位置到了首字符，主串的索引指針才會前進一位，這樣就會浪費一些不必要的比較時間。出現這種情況的原因是模式串中位置i的字符與next[i]對應的字符相同，需要修正next[i]為next[i]對應的字符的索引。下面列出“aaaadd”修正的nextval數組的內容：

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

        修正函數如下：

謝謝某人的程序：）
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;
 }
 
}