Difference string matching

Question

With string matching, you look for exact matches.

There are algorithms that account for up to k binary differences included omission of a character, the addition of a character, or replacement of a character (forgot the algorithm name), in O(n) time complexity.

Is there an algorithm that instead returns the total difference between the strings - as opposed to the number of differences.

In effect, this algorithm is a more generalised version of the other algorithm, where the other algorithm registers the value 1 for every difference (a != d), as opposed to the amount they differ by i.e. 3 for d - a.

In the original algorithm, a string matches if it has a total numbers of mismatches less than k, in the algorithm I'm looking for, I want the condition to be that the string has a total difference less than a value e.

Answer 1

•Search the Web by using Google •“efficient string matching algorithm” •17,100,000 results in 0.53 Seconds •Workout how Google manage this? So many results with string matching with many documents. •Assume the size of one document is 100 characters, and string size 35 characters •17,100,000 * 100 * 35 comparisons •59,850,000,000 •One comparison in 1 nano second, 59 Seconds