Knuth-Morris-Pratt算法混淆

我試圖實現KMP算法。我的算法工作正常用下面的例子Knuth-Morris-Pratt算法混淆

文字：121121
模式：121
結果：1,4

但是，當文本是12121和模式是一樣的上面，結果只是：1.我不知道這是算法還是我的實現問題？

其他例如：

文字：1111111111
模式：111
結果：1,4,7

我的代碼是：

public class KMP { 
    public static void main(String[] args) throws IOException{ 
     BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 
     String text = reader.readLine(); 
     String pattern = reader.readLine(); 
     search(text,pattern); 
    } 
    private static void search(String text,String pattern) 
    { 
     int[] Pi = Pi(pattern); 
     for (int i = 0,q=0; i <text.length()&&q<pattern.length() ; i++,q++) { 
      while (q>=0 && pattern.charAt(q)!=text.charAt(i)) 
      { 
       q=Pi[q]; 
      } 
      if(q==pattern.length()-1) { 
       System.out.println(i-pattern.length()+2); 
       q=Pi[q]; 
      } 

     } 
    } 

    private static int[] Pi(String p) { 
     int[] Pi = new int[p.length()]; 
     Pi[0]=-1; 
     int i=0; 
     int j=-1; 
     while (i<p.length()-1) { 
      while (j>=0 && p.charAt(j)!=p.charAt(i)) 
      { 
       j=Pi[j]; 
      } 
      i++; 
      j++; 
      if(p.charAt(j)==p.charAt(i)) Pi[i]=Pi[j]; 
      else Pi[i]=j; 
     } 
     return Pi; 
    } 

}

來源

2014-10-01 Dmytro

您的算法會查找模式的所有非重疊實例。你想找到所有重疊的實例嗎？ – 2014-10-01 15:46:10

我想查找模式的所有實例。對於文本1111和模式111，必須給出2個結果。 – Dmytro 2014-10-01 15:51:13

KMP算法查找所有不重疊的實例。您必須修改算法才能在上次搜索結果開始後重新開始搜索。 – 2014-10-01 16:46:20

希望幫你。

public int strStr(String source, String target) { 

    if (source == null || target == null){ 
     return -1; 
    } 
    if (source.isEmpty() && !target.isEmpty()){ 
     return -1; 
    } 
    if (source.isEmpty() && target.isEmpty()){ 
     return 0; 
    } 
    if (target.isEmpty()){ 
     return 0; 
    } 

    int index = 0; 
    int compare_index = 0; 
    int compare_start_index = 0; 
    int compare_same_length = 0; 
    List<Integer> answers = new ArrayList<Integer>(); 

    while (true){ 
     if (compare_same_length ==0){ 
      compare_start_index = compare_index; 
     } 

     if (source.charAt(compare_index) == target.charAt(index)){ 
      compare_same_length++; 
      index++; 
     } else { 
      if (compare_same_length >0){ 
       compare_index--; 
      } 
      compare_same_length = 0; 
      index = 0; 
     } 

     compare_index++; 
     if (compare_same_length == target.length()){ 
      answers.add(compare_start_index+1); 
      compare_same_length=0; 
      index=0; 
     } 

     if (compare_index == source.length()){ 
      //here are answers 
      for (int i = 0; i < answers.size(); i++) { 
       int value = answers.get(i); 
      } 
      return 1; 
     } 
    } 
}

來源

2016-05-26 13:14:02 beehuang

Knuth-Morris-Pratt算法混淆

回答

相關問題