Analyze text (lemmatization, edit distance)

there’re two possible solutions as far as I know algorithms.

You could try to use dynamic programming , LCS (longest common subsequence). It will search original text for the desired word as pattern, I believe it’s O(mn):

Although the easier would be to use text search algorithm. The best I know is KMP and it’s O(n). For character comparison you could group them into sets like {i I l(L) 1}, {o O 0} and so on. Yet you could modify this for not matching all letters (forbid -> forbad).

So now you could compare benefits of these two and yours suggestion.

Leave a Comment