Content deleted Content added
→Why does this work?: Reply |
AmirOnWiki (talk | contribs) →Probabilistic analysis: new section |
||
| (One intermediate revision by one other user not shown) | |||
Line 259:
:::::::Just keep running the algorithm and it will find multiple instances of the same pattern. Use a separate hash table to store the hashes of the patterns and it will be able to find multiple different patterns. The same idea, easily generalized. We need published sources for that of course but they don't have to be in the original paper. The subtlety is that the expected time becomes O(n + sum of lengths of matches), which could be larger than n for some inputs. (Also technically I'm not a distinguished professor; that's a specific job title that I don't currently have.) —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:32, 28 September 2019 (UTC)
== Why does this work? (resolved) ==
The hash function suggested in [[Rabin–Karp algorithm#Hash function used]] goes over each character. So I don't see how using the hash is faster than just comparing each character [[User:AltoStev|<span style='color: orange;'>'''AltoStev'''</span>]] ([[User Talk:AltoStev|<span style='color: #448cff'>talk</span>]]) 23:00, 28 September 2024 (UTC)
Line 267:
::Oh I see what you mean. I meant, for each index i, the pair (s[i], s_2[i]). [[User:AltoStev|<span style='color: orange;'>'''AltoStev'''</span>]] ([[User Talk:AltoStev|<span style='color: #448cff'>talk</span>]]) 12:20, 30 September 2024 (UTC)
:::But that would only test two strings for equality. This algorithm tests whether one is a substring of the other, at any position. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 20:17, 30 September 2024 (UTC)
== Probabilistic analysis ==
There is a vauge statement that the expected time of the algorithm is linear. It would be nice if someone can flesh this out. [[User:AmirOnWiki|AmirOnWiki]] ([[User talk:AmirOnWiki|talk]]) 14:09, 23 June 2025 (UTC)
| |||