wildcard function - search for longest common subsequence and make string with wildcards, e.g. wildcard("hello", "elo") returns "*e*lo"

wcg.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

string
wildcard(const string& a, const string& b)
{
	string res;
	size_t i, j;
	size_t w = a.length() + 1;
	size_t h = b.length() + 1;
	vector<int> lcs(w * h);

	for (i=0; i<w; i++) {
		lcs[i] = 0;
	}
	for (j=0; j<h; j++) {
		lcs[j * w] = 0;
	}

	for (i=1; i<w; i++) {
		for (j=1; j<h; j++) {
			if (a[i-1] == b[j-1]) {
				lcs[i + j * w] = lcs[(i - 1) + (j - 1) * w] + 1;
			} else {
				lcs[i + j * w] = max(lcs[i + (j - 1) * w], lcs[(i - 1) + j * w]);
			}
		}
	}

	i = w - 1;
	j = h - 1;
	bool wc = false;

	for (;;) {
		if ((i == 0) || (j == 0)) {
			break;
		}
		if (a[i - 1] == b[j - 1]) {
			res = a[i - 1] + res;
			i--;
			j--;
			wc = false;
			continue;
		}
		if (lcs[i + (j - 1) * w] > lcs[(i - 1) + j * w]) {
			if (!wc) {
				res = '*' + res;
				wc = true;
			}
			j--;
			continue;
		} else {
			if (!wc) {
				res = '*' + res;
				wc = true;
			}
			i--;
			continue;
		}
	}
	if ((a[0] != b[0]) && (res[0] != '*')) res = '*' + res; /* ??? */

	return res;
}

int
main()
{
	vector<string> lines;
	map<string, int> wcs;
	string line;

	while (getline(cin, line)) {
		for (size_t i=0; i<lines.size(); i++) {
			string wc = wildcard(lines[i], line);
			if (wcs.find(wc) == wcs.end()) {
				wcs[wc] = 1;
			} else {
				wcs[wc]++;
			}
		}
		lines.push_back(line);
	}

	for (map<string, int>::iterator it = wcs.begin(); it != wcs.end(); ++it) {
		cout << it->second << "\t" << it->first << endl;
	}

	return 0;
}