KMP匹配算法

先来说一下回溯法匹配字符串：

对于主字符串有一个target_index，以target_index（不动）为起点，匹配字符串pattern的长度+target_index为终点，逐个进行比较，当发现不符合时，将target_index加1，进行下一轮比较，也就是说最坏的情况需要遍历target中length(target)-length(pattern)个元素。

这种回溯法没有很有效的利用已经得到的信息：当比较到了target_index+j个元素，发现都一样，但是第target_index+j+1个元素不一样时，我们直接就从target_index+1开始重新比较，没有很好的利用target_index+j已经之前的元素一样的信息了。

KMP算法在一定的程度上用到了该信息。

已经知道（target_index，target_index+j）这中间的元素是一样的了，那么target_index该移动多少距离才是效率更高的呢。

比如说target：{"a","n","n","a","c","d","a","n","a","c","a","d","s","a","n","n","a","n","n","a","c","a","n","n","a"}

pattern：{"a","n","n","a","b","a","n","n","a"}

在target_index=0，j=3,的情况下，target=pattern，当j=4时，开始不匹配了

现在将已经匹配的"a","n","n","a"分为数组A和B，即A={"a","n","n","a"}；B={"a","n","n","a"}；

B从后面与A开始比较

A："a","n","n","a"

B： "a","n","n","a"

有一个字符是一样的,统计这种一样字符的个数，设为count（本例中count为0（有一个元素），如果没有这样的个数，则count为-1）

于是target_index移动target_index+length(A)-count

可以这么移动而不是逐个逐个移动的原因在于：在本例中A自我覆盖的个数count为0，如果在target中找到了pattern，也必然是以count中元素开头的，所以length(A)-count不可能是pattern的开头，所以这些元素可以直接略过去。

public class KMPalgorithm {



   public static void main(String[] args) {
       String []word = {"a","n","n","a","c","a","n","n","a"};
       String []target = {"a","n","n","b","c","d","a","n","a","c","a","d","s","a","n","n","a","n","n","a","c","a","n","n","a"};
       //String []word = {"a","b","a"};
       System.out.print(kmp_find(target,word));
   }

   public static int overlayFunction(String[]word){
       int length = word.length;
       for(int i = 1;i<length;i++){
           boolean flag = true;
           String[] newWord = new String[length-i];
           int count = -1;
           for(int j = 0;j<length-i;j++){
               newWord[j] = word[j+i];
               if(word[j+i]!=word[j]){
                   flag = false;
                   break;
               }
               count = j;
           }
           if(flag == true){
               return count;
           }
       }
       return -1;
   }


   public static int kmp_find(String[]target,String []word){
       int lengthT = target.length;
       int lengthW = word.length;
       for(int i = 0;i<lengthT-lengthW+1;){
           boolean flag = true;
           int j1 = 0;
           for(int j = 0;j<lengthW;j++){
               if(target[i+j]!=word[j]){
                   flag = false;
                   j1 = j;
                   break;
               }

           }
           if(!flag&&j1 == 0){
               i = i+1;
           }else if(flag==true){
               return i;
           }else{
               String[]pattern2 = new String[j1];
               for(int k = 0;k<j1;k++){
                   pattern2[k] = word[k];
               }
               i = i+j1-1-overlayFunction(pattern2);

           }
           System.out.println("查找的target的index"+i);
       }
       return -1;
   }
}

巴特西

KMP匹配算法

最新文章

热门文章