Content deleted Content added
→Quadratic?: Reply |
Al-Quaknaa (talk | contribs) →Quadratic?: Reply |
||
Line 71:
:::I've made one more clarification. I think it's important to point out that, unlike with Knuth-Morris-Pratt, you cannot expect complexity linear in the length of the input, so linear in the length of input + output is the best possible. [[User:Al-Quaknaa|Martin Koutecký]] ([[User talk:Al-Quaknaa|talk]]) 11:11, 10 October 2024 (UTC)
::::Undid a part of your change. I do not understand the "longer" part: the input and output of the algorithm are two different data structures, comparing their lengths is definitely nontrivial. [[User:Викидим|Викидим]] ([[User talk:Викидим|talk]]) 17:58, 10 October 2024 (UTC)
:::::I don't understand what's the issue.
:::::The input is a collection of strings and we measure its length by counting the characters in it.
:::::The output is a set of pairs (i,j) such that string i appears at index j. The number of such pairs may be (much) larger than the length of the input.
:::::Since you were not happy with my phrasing, could you please come up with a better phrasing communicating the same fact? In my opinion, the current state is a downgrade from the incorrect statement that there may be quadratically many matches, but at least that conveyed that the "number of matches" really has to be a part of the complexity. This has now gotten lost. [[User:Al-Quaknaa|Martin Koutecký]] ([[User talk:Al-Quaknaa|talk]]) 13:10, 23 October 2024 (UTC)
| |||