Talk:Rabin–Karp algorithm: Difference between revisions

Revision as of 23:13, 26 September 2019

Revision as of 01:12, 27 September 2019

Line 231:

I could go on, but that's enough for now. The article needs to be redrafted entirely for [[WP:TONE]], and it ''must, must, must'' be cited inline, every paragraph, factoid, piece of code or pesudocode, formula, or anything else that might constitute researched and referenceable content. [[User:Sbalfour|Sbalfour]] ([[User talk:Sbalfour|talk]]) 15:46, 26 September 2019 (UTC)

==Infeasability==

The algorithm as given is infeasable: it does ''m'' mods (i.e. divides) including doing the exponentiation, forto everysubtract characterthe positionhigh incharacter of the substring from the running hash, times ''n'' character positions in the text string = ''nm'' mods. Divide is microprogrammed on modern architectures, and is maybe 3-5 timers slower than multiply, and maybe 50-100 times slower than ADD/XOR/SHIFT. You'll give back all or most of the advantage over linear hashing. [[User:Sbalfour|Sbalfour]] ([[User talk:Sbalfour|talk]]) 23:13, 26 September 2019 (UTC)