1806.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1806 on 2006-02-04 at 14:03:23 */ 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAX = 256;
const int L_MAX = 16;

bool near(const char*, const char*, int);

int main()
{
	char id[MAX][L_MAX];
	int n, d, i, j;

	while(scanf("%d %d", &n, &d) != EOF && n != 0) {
		for(i = 0; i < n; i++) scanf("%s", id[i]);
		qsort(id, n, sizeof(id[0]), (int(*)(const void*, const void*))strcmp);
		int login = 0;
		for(i = 0; i < n; i++)
			for(j = i+1; j < n; j++)
				if(near(id[i], id[j], d)) printf("%s,%s\n", id[i], id[j]), login++;
		printf("%d\n", login);
	}
	
	return 0;
}

bool near(const char* id1, const char* id2, int dis)
{
	int d[L_MAX][L_MAX], i, j, k;
	int l1 = strlen(id1), l2 = strlen(id2);
	if(!strcmp(id1, id2) || abs(l1-l2) > dis) return false;
	for(i = 0; i < L_MAX; i++) d[0][i] = d[i][0] = i;
	for(i = 1; i <= l1; i++)
		for(j = 1; j <= l2; j++) {
			d[i][j] = min(d[i][j-1], d[i-1][j]) + 1;
			d[i][j] = min(d[i][j], d[i-1][j-1]+(id1[i-1]==id2[j-1]?0:1));
			for(k = 0; k < dis; k++) {
				if(i >= 2+k && j >= 2) {
					int cost = 1 + k;
					if(id1[i-1] != id2[j-2]) cost++;
					if(id1[i-2-k] != id2[j-1]) cost++;
					d[i][j] = min(d[i][j], d[i-2-k][j-2]+cost);
				}
				if(i >= 2 && j >= 2+k) {
					int cost = 1 + k;
					if(id1[i-1] != id2[j-2-k]) cost++;
					if(id1[i-2] != id2[j-1]) cost++;
					d[i][j] = min(d[i][j], d[i-2][j-2-k]+cost);
				}
			}
		}
	
	return d[l1][l2] <= dis;
}