String matching algorithm has the KMP, horspools, they can only be accurate matching,

So how should match the Levenshtein short edit Distance & lt; String=1?

In string "hereharewereworeherareteartoredeardareearrearehrerheasereseersearrah", for example, the matching mode "ware", will be
[5-7] : motorcycle, 19-21 [] : motorcycle, hare [4-7], [18 to 21] : rare, [34 to 37] : dare and so on, also can match the insertion of a character, such as "dware" this,

This problem should do excuse me?

CodePudding user response:

Wrote a version of the BF, complexity is O (m * n), but the title requires complexity O (n) on average, how can it do

CodePudding user response:

Because m is far less than n I think lz make if time complexity is o (m * n), already meets the requirements

CodePudding user response:

reference 1st floor wjhhaiyang response:

wrote a version of the BF, complexity is O (m * n), but the title requires complexity O (n) on average, how can it do

You use a title says the Levenshtein algorithm of short, you save on a line and the current line, O (m * n) becomes O (m) ah...