我試圖了解Sliding Window模式匹配的演算法。我遇到了KMP，Rabin-Karp這些看起來是在使用Sliding Window在文本中查找模式的方式。我們可以對 s 進行分類KMP和Rabin-Karp型別Sliding window algorithm嗎？
uj5u.com熱心網友回復：
分類總是很棘手。如果不對我們所談論的內容進行嚴格定義，我們就無法真正做到這一點，而這樣的定義通常是相當武斷的。
話雖如此，在我的腦海中，滑動視窗演算法有一個固定大小的視窗，它沿著序列移動，在每次迭代中，將視窗左側的一部分移出并從右側移入相同的數量。有了這個定義，Rabin-Karp 顯然是一個滑動視窗演算法。在每次迭代中，它會洗掉左側的一個字符并從右側添加一個字符以更新哈希值。
Knuth-Morris-Pratt 不這樣做。你當然可以認為它有一個視窗，但是這個視窗是你當前匹配的模式前綴的邊框，當你可以擴展匹配時，視窗大小會增長，而當你無法匹配時，它會縮小到較短邊框的長度。在演算法運行期間，大小從零變化到模式的長度。
話雖如此，我對滑動視窗演算法的定義是任意的，其他人肯定會不同意。
有這個定義有用嗎？我認為是這樣。滑動視窗的想法是一種抽象，可以讓我們構建新的演算法。我們會因為允許可變大小的視窗而失去任何東西嗎？也許不是。但是 KMP 和 RK 有什么共同點，我們可以抽象成可能有用的東西？
我不認為有很多。他們從左到右掃描字串（不像Boyer-Moore），但除此之外他們沒有共享太多。一種是基于散列的，另一種是基于邊界的。細節完全不同。
您總是可以提出一個它們都適合的分類，但是除非該類告訴您一些瑣碎的事情，否則它沒有多大用處，這是我的看法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/471189.html
上一篇：無法在片段的recyclerview中獲取實時資料庫
下一篇：對負指數產生錯誤結果的n實作的冪