3 ms·
That's a nice soundbite but it's not correct. The worst case performance with the DFA is linear, the same as them.
by jules 11y ago
That's a nice soundbite but it's not correct. The worst case performance with the DFA is linear, the same as them.
- lorenzhs 11y agoNo that's just not true. Your step function takes time linear in the length of string. For example, `newstate = [0 for x in state]` takes θ(|state|) time, and because you initialise the state with `range(len(string)+1)`, that's linear in the string length.
- jules 11y agoNow you're talking about the cost of constructing the DFA, not searching the index with the resulting DFA. The cost of construcing the DFA is irrelevant, and even then you can construct the DFA in O(n) with my method for fixed max edit distance and fixed alphabet. Same as that paper.