KMP故障功能的應用

許多關於KMP的文章都提到，KMP本身的故障功能有很多應用。KMP故障功能的應用

一個這樣的應用程序是找到最小的字符串，當連續k次給出原始字符串（句點）時。

但我找不到任何其他。還有哪些其他問題涉及KMP故障功能？

2012-05-09 Jonh

KMP計算字符串所有前綴的邊界，它們本身就是字符串算法中的關鍵概念。（計算全詞本身是平凡的邊界，和KMP（故障功能）是這樣做的標準！）

的小號邊框很簡單，既是一個前綴和S後綴的單詞。

正如你正確地注意到，以計算邊界能力的優秀應用是計算最小的字符串u這樣的可能性，即對一些自然ķ瓦特^K = 小號對於給定的字符串小號。這被稱爲s的原始根。

原因是邊界和字符串週期之間的對偶性。一個字符串小號的期是任何字符串瓦特比小號這樣小號是字符串WWWW ...例如前綴，ABC不再是一個句點abcabcab。事實證明，一個詞的邊界和句點之間有1：1的對應關係;在上例中，請注意abcab是的邊界abcabcab。在一般情況下，只要瓦特是一段小號，然後串的，從一開始W¯¯去除後仍從小號（瓦特^-1 小號）是小號邊框。同樣，如果瓦特是從小號仍然當您刪除後綴瓦特是一段小號小號，那麼這個詞的邊界。

期間是分析字符串屬性的重要工具。例如，它們用於查找字符串中重複（運行）的算法;概述參見this paper.

來源

2012-08-14 05:24:33 devnum

KMP故障功能的應用

回答

相關問題