「2146 Confusing Login Names」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
**2146 Confusing Login Names
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2146
**解答例
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true){
int n = sc.nextInt();
if(n==0) break;
int d = sc.nextInt();
String[] input = new String[n];
for(int i=0;i<n;i++){
input[i] = sc.next();
}
TreeSet<StringPair> output = new TreeSet<StringPair>();
Object[] input_del = new Object[n];
for(int i=0;i<n;i++){
input_del[i] = new LinkedHashSet<String>();
addAllDelete(input[i],(LinkedHashSet<String>)input_del[i]);
}
if(d==1){
for(int i=0;i<n;i++){
String s1 = input[i];
HashSet<String> del = (LinkedHashSet<String>)input_del[i];
HashSet<String> swap = new HashSet<String>();
addAllSwap(s1,swap);
for(int j=0;j<n;j++){
if(i==j) continue;
String s2 = input[j];
if(s1.length()==s2.length()){
if(i<j) continue;
//S
if(swap.contains(s2)){
output.add(new StringPair(s1,s2));
continue;
}
//R
if(replacedist(s1,s2)<=1){
output.add(new StringPair(s1,s2));
continue;
}
}
else if(s1.length()==s2.length()+1){
//D
if(del.contains(s2)) output.add(new StringPair(s1,s2));
}
}
}
}
else{
for(int i=0;i<n;i++){
String s1 = input[i];
LinkedHashSet<String> del = (LinkedHashSet<String>)input_del[i];
HashSet<String> deldel = new HashSet<String>();
for(String s:del){
addAllDelete(s,deldel);
}
LinkedHashSet<String> swap = new LinkedHashSet<String>();
addAllSwap(s1,swap);
HashSet<String> swap2 = new HashSet<String>();
addAllSwap2(s1,swap2);
HashSet<String> delswap = new HashSet<String>();
for(String s:del){
addAllSwap(s,delswap);
}
for(int j=0;j<n;j++){
if(i==j) continue;
String s2 = input[j];
if(s1.length()==s2.length()){
if(i<j) continue;
//S,SS
if(swap2.contains(s2)){
output.add(new StringPair(s1,s2));
continue;
}
//R,RR
if(replacedist(s1,s2)<=2){
output.add(new StringPair(s1,s2));
continue;
}
//SR
boolean cont = false;
for(String s:swap){
if(replacedist(s,s2)<=1){
output.add(new StringPair(s1,s2));
cont = true;
break;
}
}
if(cont) continue;
//DI
cont = false;
for(String s:del){
if(((LinkedHashSet<String>)input_del[j]).contains(s)){
output.add(new StringPair(s1,s2));
cont = true;
break;
}
}
if(cont) continue;
}
else if(s1.length()==s2.length()+1){
//D
if(del.contains(s2)){
output.add(new StringPair(s1,s2));
continue;
}
//DS
if(delswap.contains(s2)){
output.add(new StringPair(s1,s2));
continue;
}
//DR
for(String s:del){
if(replacedist(s,s2)<=1){
output.add(new StringPair(s1,s2));
}
}
}
else if(s1.length()==s2.length()+2){
if(deldel.contains(s2)) output.add(new StringPair(s1,s2));
}
}
}
}
for(StringPair sp:output){
System.out.println(sp.s1+","+sp.s2);
}
System.out.println(output.size());
}
}
private static int replacedist(String s1,String s2){
if(s1.length()!=s2.length()) return -1;
int ret = 0;
for(int i=0;i<s1.length();i++){
if(s1.charAt(i)!=s2.charAt(i)) ret++;
}
return ret;
}
private static void addAllDelete(String s, HashSet<String> h) {
for(int k=0;k<s.length();k++){
String news = delete(s,k);
if(!h.contains(news)) h.add(news);
}
}
private static void addAllSwap(String s,HashSet<String> h){
for(int k=0;k<s.length()-1;k++){
String news = swap(s,k);
if(!h.contains(news)) h.add(news);
}
}
private static void addAllSwap2(String s,HashSet<String> h){
for(int k=0;k<s.length()-1;k++){
String news = swap(s,k);
if(!h.contains(news)) h.add(news);
for(int l=0;l<s.length()-1;l++){
String news2 = swap(news,l);
if(!h.contains(news2)) h.add(news2);
}
}
}
private static String delete(String s,int index){
char[] ret = new char[s.length()-1];
int p = 0;
for(int i=0;i<s.length();i++){
if(i!=index){
ret[p] = s.charAt(i);
p++;
}
}
return new String(ret);
}
private static String swap(String s,int index){
char[] ret = new char[s.length()];
for(int i=0;i<s.length();i++){
if(i!=index&&i!=index+1) ret[i] = s.charAt(i);
else if(i==index) ret[i] = s.charAt(i+1);
else ret[i] = s.charAt(i-1);
}
return new String(ret);
}
}
class StringPair implements Comparable<StringPair>{
String s1;
String s2;
StringPair(String s1, String s2) {
if(s1.compareTo(s2)<0){
this.s1 = s1;
this.s2 = s2;
}
else{
this.s1 = s2;
this.s2 = s1;
}
}
public boolean equals(Object o){
StringPair sp = (StringPair)o;
return this.s1.equals(sp.s1)&&this.s2.equals(sp.s2);
}
public int compareTo(StringPair sp){
if(!this.s1.equals(sp.s1)) return this.s1.compareTo(sp.s1);
else return this.s2.compareTo(sp.s2);
}
}
