Revision as of 03:27, 22 July 2024 edit Викидим (talk \| contribs) Autopatrolled, Extended confirmed users, New page reviewers 27,348 edits m Викидим moved page Talk:Aho–Corasick Automaton to Talk:Aho–Corasick algorithm over redirect: Per Google ngrams, algorithm is much more popular, move reverted. A WP:move discussion is needed to rename ← Previous edit		Revision as of 19:27, 9 October 2024 edit undo Al-Quaknaa (talk \| contribs) 27 edits →Quadratic?: Reply Tag: Reply Next edit →
Line 66: : Note that because all matches are found, there can be a <u>quadratic</u> number of matches if every substring matches puzzled me. Quadratic with respect to what? Surely there cannot be more matches than strings, so it seems linear WRT the strings. [[User:Викидим\|Викидим]] ([[User talk:Викидим\|talk]]) 03:06, 22 July 2024 (UTC) :The statement is meant to be "quadratic in length of input", where length of input is total number of characters. But that claim is wrong, it cannot be quadratic - it is a nice exercise to show that there's an instance with <math>\Theta(n \sqrt(n))</math> matches, and that it cannot be asymptotically more. [[User:Al-Quaknaa\|Martin Koutecký]] ([[User talk:Al-Quaknaa\|talk]]) 19:27, 9 October 2024 (UTC)

Talk:Aho–Corasick algorithm: Difference between revisions