Now 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.
Comments
Now 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.