Knuth-Morris-Pratt算法

Knuth–Morris–Pratt algorithm的解決方案：Haystack：AAAAAAAAAA，Needle：AAA，即：3，是否正確？Knuth-Morris-Pratt算法

因爲，在乾草堆中有8個AAA實例，但據我所知，knuth-morris-pratt算法只能找到3.我在想這個錯誤嗎？

這個問題可以通過找出字符串中每個後綴的邊界來解決嗎？

以下是我實現KMP算法：

public static int occurrenceOfSubstring(char[] target, char[] pattern) { 
     int[] overlay = new int[pattern.length]; 
     overlay[0] = -1; 
     overlay[1] = 0; 

     int i = 0, j = 1; 

     while (j + 1 < pattern.length) { 
      if (pattern[i] == pattern[j]) { 
       if (i == 0) { 
        overlay[j + 1] = 1; 
       } else { 
        overlay[j + 1] = overlay[j] + 1; 
       } 
       i++; 
       j++; 
      } else if (pattern[j] == pattern[0]) { 
       i = 0; 
      } else { 
       j++; 
      } 
     } 

     int l = 0,count=0; 

     for (int k = 0; k < target.length; k++) { 
      if (target[k] == pattern[l]) { 
       if (l == pattern.length - 1) { 
        l = 0; 
        count++; 
       } else { 
        l++; 
       } 
      } else { 
       l = overlay[l] == -1 ? 0 : overlay[l]; 
      } 
     } 
     return count; 
    }

來源

2014-01-29 user1479589

此問題似乎最適合[代碼評論]（http://codereview.stackexchange.com/）網站，因爲它要求進行算法實施審覈。 –

@Slanec這個問題屬於這裏，這是一個關於算法的問題。 OP做了功課，而不是問「如何實施KMP？」介紹他迄今爲止的結果並詢問他們是否正確。 [代碼評論]（http://codereview.stackexchange.com/）用於評論架構或風格。 – Bolo

@bolo肯定算法問題屬於程序員。這取決於真正被問到的內容...... – Pureferret

KMP側重於當全場比賽搜索失敗，但部分匹配可重複使用，以進一步重新啓動搜索下來草垛比優化搜索一種天真的方法。但是，您呈現的案例沒有部分匹配，它總是在每次搜索迭代中查找完整的單詞。所以我確實希望KMP能爲你提出的情況返回3場比賽。請注意，這是一個邊緣案例，可能會試圖修改算法以利用乾草堆或單詞或兩者的上下文信息，但現在您已經超越了KMP。希望這可以幫助。

來源

2014-01-30 01:19:53

Knuth-Morris-Pratt算法

回答

相關問題