Language: C++

// ACM-ICPCà\I2010 F. Ã¢L¯

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int INF = 100000000;

int d;
string mes, cur;
vector<string> piece;
vector<int> connect[30][20];
vector<string> ans;
set<string> mem[43];
int dp[43][43];
int cost[30][20];
int curdist;

int getMinedit(string s, string t){
	int n = s.size(), m = t.size();
	int cost[43], newcost[43];
	for(int i=0;i<=n;i++) cost[i] = 0;
	for(int j=1;j<=m;j++){
		newcost[0] = j;
		for(int i=1;i<=n;i++){
			newcost[i] = 1+min(newcost[i-1],cost[i]);
			newcost[i] = min(newcost[i],cost[i-1]+(s[i-1]!=t[j-1]));
		}
		memcpy(cost, newcost, sizeof(cost));
	}
	return *min_element(cost, cost+n+1);
}

bool editDist(int s, int e){
	for(int i=s+1;i<=e;i++){
		curdist = INF;
		for(int j=max(1,i-d);j<=min((int)mes.size(),i+d);j++){
			if(cur[i-1]==mes[j-1]) dp[i][j] = dp[i-1][j-1];
			else {
				dp[i][j] = dp[i-1][j-1]+1;
				dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
				dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
			}
			curdist = min(curdist, dp[i][j]);
		}
		if(curdist > d) return false;
	}
	return true;
}

void dfs(int pIdx, int p1, int p2){
	int len = piece[0].size();
	int csize = cur.size();
	if(dp[csize][mes.size()] <= d) ans.push_back(cur);
	int start = min(len-1, csize-p2-1);
	cur += string(len-1-start, ' ');
	int ccost = curdist;
	for(int i=start;i>=0;i--){
		int nsize = csize+len-i;
		if(nsize > mes.size() + d) break;
		cur += ' ';
		for(int j=0;j<connect[pIdx][i].size();j++){
			if(ccost + cost[connect[pIdx][i][j]][i] > d) continue;
			bool flag = true;
			for(int k=i;k<len;k++){
				cur[csize+k-i] = piece[connect[pIdx][i][j]][k];
				if(!editDist(csize+k-i, csize+k-i+1)){
					flag = false;
					break;
				}
			}
			if(!flag) continue;
			if(mem[nsize].count(cur)) continue;
			mem[nsize].insert(cur);
			dfs(connect[pIdx][i][j], nsize, p1);
		}
	}
	cur = cur.substr(0, csize);
}

int main(){
	int n, len;
	for(int i=0;i<=42;i++) dp[i][0] = dp[0][i] = i;
	while(cin >> d >> n, n){
		cin >> mes;
		piece.clear();
		for(int i=0;i<n;i++){
			string str; cin >> str;
			if(getMinedit(mes, str) > d) continue;
			piece.push_back(str);
		}
		sort(piece.begin(), piece.end());
		piece.erase(unique(piece.begin(), piece.end()), piece.end());
		len = piece[0].size();
		for(int i=1;i<=mes.size()+d;i++)
			for(int j=1;j<=mes.size()+d;j++)
				if(abs(i-j) > d) dp[i][j] = INF;
		for(int i=0;i<piece.size();i++){
			for(int j=0;j<len;j++){
				connect[i][j].clear();
				for(int k=0;k<piece.size();k++){
					if(piece[i].substr(len-j) == piece[k].substr(0,j)){
						connect[i][j].push_back(k);
						cost[k][j] = getMinedit(mes, piece[k].substr(j));
					}
				}
			}
		}
		for(int i=0;i<=mes.size()+d;i++)
			mem[i].clear();
		ans.clear();
		for(int i=0;i<piece.size();i++){
			cur = piece[i];
			if(!editDist(0, len)) continue;
			dfs(i, len, 0);
		}
		sort(ans.begin(), ans.end());
		cout << ans.size() << endl;
		if(ans.size() <= 5){
			for(int i=0;i<ans.size();i++)
				cout << ans[i] << endl;
		}
	}
}

Compiler output:
a.cc: In function 'int getMinedit(std::string, std::string)':
a.cc:33:17: error: 'memcpy' was not declared in this scope
   33 |                 memcpy(cost, newcost, sizeof(cost));
      |                 ^~~~~~
a.cc:8:1: note: 'memcpy' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    7 | #include <algorithm>
  +++ |+#include <cstring>
    8 |