#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 ;
}