拉賓卡普字符串匹配算法複雜度

如何採取模在拉賓算法在降低複雜性上相對本地horners有助於排除串match.Anybody請解釋拉賓卡普字符串匹配算法複雜度

2014-03-13 Vishal

定義「本地horners規則字符串匹配」 –

horner的規則是，如果你有一個基數x的數字，所以最大限度地減少乘法的數量，它可以被寫爲-X（X（X（..）+。）+。）+。例如：1234可以寫成10（10（10（1）+2）+3）+4 – Vishal

我想通過Horners治你的意思是處理字符串作爲數一些基數（「abcd」='a'* p^3 +'b'* p^2 +'c'* p^1 +'d'* p^0）並將字符串作爲數字進行比較，並通過Rabin算法意味着基本上相同的東西，但以某種其他數字爲模。

這個事情是使用Horners規則，你只能比較短的字符串 - 否則你會溢出（你可以使用大整數來避免它，但這就是你在複雜性中失去的地方。將具有O（n）位，所以算術運算不會在O（1）中完成）。

而在Rabin-Karp算法中，與我們的字符串相對應的數字將保持較小，因爲我們將它們取模爲其他數字。它可能會導致碰撞，但如果我們幸運的話，碰撞是非常罕見的。

2014-03-13 19:44:05

在任何一種情況下，我們都在計算數字Ist，我們直接比較它IInd我們比較它的mod，所以它如何降低複雜度?? – Vishal

隨着數字變大，您不能再進行比較，在O（1）時間內進行相加和相乘。比較和加法需要O（m）操作，其中m是數字的位數，乘法的複雜度可能更大，並且m將與子串長度成比例。 –

假設您試圖在一個長度爲100000的字符串中查找長度爲50000的子字符串。您將使用什麼數字來表示子字符串？ –

回答