Language: C C++ D Haskell Lua OCaml PHP Perl Plain Text Python Ruby Scheme Tcl #include <vector> #include <iostream> using namespace std; int fuzzy_substring(const string needle, const string haystack) { const int nlen = needle.size(), hlen = haystack.size(); if (hlen == 0) return -1; if (nlen == 1) return haystack.find(needle); vector<int> row1(hlen+1, 0); for (int i = 0; i < nlen; ++i) { vector<int> row2(1, i+1); for (int j = 0; j < hlen; ++j) { const int cost = needle[i] != haystack[j]; row2.push_back(std::min(row1[j+1]+1, std::min(row2[j]+1, row1[j]+cost))); } row1.swap(row2); } return *std::min_element(row1.begin(), row1.end()); } int main() { cout << "Substring match ('aa', 'bb aca bb'): " << fuzzy_substring("aa", "bb aca bb") << endl ; return 0 ; } Private [?] Run code