1252-Confusing Login Names

問題概要

ある2文字列の距離は"二つの文字列を以下の操作を何回行なって別の文字列に変更出来るか"という用に定義されるとする．
二つの文字列の距離がd以下のペアを全て求めよ．

解法

レーベンシュタイン距離が2*D以下の文字列に対して，
交換を全探索して，それに対するレーベンシュタイン距離を求める．

実装(C++)

PKUで通すための枝刈りが多い

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[20][20];
int n,d;
int LevenshteinDistance(const string &a,const string &b){
	int la=a.size(),lb=b.size();
	if(abs(la-lb)>d)return 999;
	for(int i=0;i<=la;i++)dp[i][0]=i;
	for(int i=0;i<=lb;i++)dp[0][i]=i;
	for(int i=0;i<la;i++)
		for(int j=0;j<lb;j++){
			int cost=!(a[i]==b[j]);
			dp[i+1][j+1]=min(min(dp[i][j+1]+1,dp[i+1][j]+1),dp[i][j]+cost);
		}
	return dp[la][lb];
}

string name[200];
bool check2(const string &a,const string &b){
	if(a.size()>b.size())return check2(b,a);
	int la=a.size(),lb=b.size();
	int i;
	if(la==lb){
		int c=0;
		for(int i=0;i<la;i++){
			if(a[i]!=b[i]){
				c++;
				if(c>=2)return false;
			}
		}
	}else{
		for(i=0;i<la;i++){
			if(a[i]!=b[i])break;
		}
		for(;i<la;i++){
			if(a[i]!=b[i+1])return false;
		}
	}
	return true;
}
bool check(string &a,string &b){
	if(LevenshteinDistance(a,b)<=d)return true;
	if(LevenshteinDistance(a,b)>d*2)return false;
	int la=a.size(),lb=b.size();
	if(abs(la-lb)>d-1)return false;
	if(d==2){
		for(int i=0;i<la-1;i++){
			swap(a[i],a[i+1]);
			int r=check2(a,b);
			swap(a[i],a[i+1]);
			if(r)return true;
		}
		for(int i=0;i<lb-1;i++){
			swap(b[i],b[i+1]);
			int r=check2(a,b);
			swap(b[i],b[i+1]);
			if(r)return true;
		}
	}else if(d==1){
		for(int i=0;i<la-1;i++){
			swap(a[i],a[i+1]);
			int r=a==b;
			swap(a[i],a[i+1]);
			if(r)return true;
		}
		for(int i=0;i<lb-1;i++){
			swap(b[i],b[i+1]);
			int r=a==b;
			swap(b[i],b[i+1]);
			if(r)return true;
		}
	}
	if(d<2)return false;
	if(abs(la-lb)>d-2)return false;
	for(int j=0;j<la-1;j++){
		swap(a[j],a[j+1]);
		for(int i=0;i<la-1;i++){
			swap(a[i],a[i+1]);
			if(a==b){
				swap(a[i],a[i+1]);
				swap(a[j],a[j+1]);
				return true;
			}
			swap(a[i],a[i+1]);
		}
		for(int i=0;i<lb-1;i++){
			swap(b[i],b[i+1]);
			if(a==b){
				swap(b[i],b[i+1]);
				swap(a[j],a[j+1]);
				return true;
			}
			swap(b[i],b[i+1]);
		}
		swap(a[j],a[j+1]);
	}
	for(int j=0;j<lb-1;j++){
		swap(b[j],b[j+1]);
		for(int i=0;i<la-1;i++){
			swap(a[i],a[i+1]);
			if(a==b){
				swap(a[i],a[i+1]);
				swap(b[j],b[j+1]);
				return true;
			}
			swap(a[i],a[i+1]);
		}
		for(int i=0;i<lb-1;i++){
			swap(b[i],b[i+1]);
			if(a==b){
				swap(b[i],b[i+1]);
				swap(b[j],b[j+1]);
				return true;
			}
			swap(b[i],b[i+1]);
		}
		swap(b[j],b[j+1]);
	}
	return false;
}
int main() {
	while(cin>>n>>d){
		if(!n)break;
		for(int i=0;i<n;i++)cin>>name[i];
		std::sort(name,name+n);
		int ans=0;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				if(check(name[i],name[j])){
					cout<<name[i]<<","<<name[j]<<endl;
					ans++;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}