java 由于在nyoj上水过，受之前水过代码的影响，在poj上一直过不了，优化不彻底，各种改各种tle......终于行了，不过还是要注意几点，详见代码
Description
You, as a member of a development team for a new spell checking program, are to write a module that will check the correctness of given words using a known dictionary of all correct words in all their forms.
If the word is absent in the dictionary then it can be replaced by correct words (from the dictionary) that can be obtained by one of the following operations:
?deleting of one letter from the word;
?replacing of one letter in the word with an arbitrary letter;
?inserting of one arbitrary letter into the word.
Your task is to write the program that will find all possible replacements from the dictionary for every given word.
If the word is absent in the dictionary then it can be replaced by correct words (from the dictionary) that can be obtained by one of the following operations:
?deleting of one letter from the word;
?replacing of one letter in the word with an arbitrary letter;
?inserting of one arbitrary letter into the word.
Your task is to write the program that will find all possible replacements from the dictionary for every given word.
Input
The first part of the input file contains all words from the dictionary. Each word occupies its own line. This part is finished by the single character '#' on a separate line. All words are different. There will be at most 10000
words in the dictionary.
The next part of the file contains all words that are to be checked. Each word occupies its own line. This part is also finished by the single character '#' on a separate line. There will be at most 50 words that are to be checked.
All words in the input file (words from the dictionary and words to be checked) consist only of small alphabetic characters and each one contains 15 characters at most.
words in the dictionary.
The next part of the file contains all words that are to be checked. Each word occupies its own line. This part is also finished by the single character '#' on a separate line. There will be at most 50 words that are to be checked.
All words in the input file (words from the dictionary and words to be checked) consist only of small alphabetic characters and each one contains 15 characters at most.
Output
Write to the output file exactly one line for every checked word in the order of their appearance in the second part of the input file. If the word is correct (i.e. it exists in the dictionary) write the message: " is correct".
If the word is not correct then write this word first, then write the character ':' (colon), and after a single space write all its possible replacements, separated by spaces. The replacements should be written in the order of their appearance in the dictionary
(in the first part of the input file). If there are no replacements for this word then the line feed should immediately follow the colon.
If the word is not correct then write this word first, then write the character ':' (colon), and after a single space write all its possible replacements, separated by spaces. The replacements should be written in the order of their appearance in the dictionary
(in the first part of the input file). If there are no replacements for this word then the line feed should immediately follow the colon.
Sample Input
i is has have be my more contest me too if award # me aware m contest hav oo or i fi mre #
Sample Output
me is correct aware: award m: i my me contest is correct hav: has have oo: too or: i is correct fi: i mre: more me
java ac代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String strings[]=new String[10011];
int count=0;
while((strings[count]=scanner.next()).compareTo("#")!=0)
{
count++;
}
while(true)
{
String str=scanner.next();
if(str.compareTo("#")==0)break;
int flag=1;
System.out.print(str);
for(int i=0;i<count;i++)
{
String string1=strings[i];
if(str.length()==str.length()&&str.compareTo(string1)==0)
{
System.out.println(" is correct");flag=0;break;
}
}
if(flag==1){
System.out.print(":");
for(int i=0;i<count;i++)
{
//注意这里如果是 ch1=strings[i].toCharArray();和ch2=str.toCharArray();会出现RE错误，数组长度不够，下面代码中会出现越界问题
char ch1[]=new char[20];
for(int t=0;t<strings[i].length();t++)
{
ch1[t]=strings[i].charAt(t);
}
char ch2[]=new char[20];
for(int t=0;t<str.length();t++)
{
ch2[t]=str.charAt(t);
}
if(str.length()==strings[i].length())
{
int k1=0,num=0;
for(;k1<str.length();k1++)
{
if(ch1[k1]!=ch2[k1])
num++;
}
if(num==1)
{
System.out.print(" "+strings[i]);
}
}
if(str.length()==strings[i].length()-1)
{
int k1=0,k2=0,num=0;
for(;k1<strings[i].length();)
{
if(ch1[k1]!=ch2[k2])
{
num++;k1++;
}
else {
k1++;k2++;
}
}
if(num==1)
{
System.out.print(" "+strings[i]);
}
}
if(str.length()-1==strings[i].length()){
int k1=0,k2=0,num=0;
for(;k1<str.length();)
{
if(ch1[k2]!=ch2[k1])
{
num++;k1++;
}
else {
k1++;k2++;
}
}
if(num==1)
{
System.out.print(" "+strings[i]);
}
}
}
System.out.println();
}
}
}
}
nyoj ac代码（不加任何优化）：
import java.util.Scanner;
public class Main {
public static boolean deleteone(String string1,String string2)
{
for(int j=0;j<string1.length();j++)
{
StringBuffer s=new StringBuffer();
for(int i=0;i<string1.length();i++)
{
if(i==j)continue;
s=s.append(string1.charAt(i));
}
if(string2.compareTo(new String(s))==0)
{
return true;
}
}
return false;
}
public static boolean replaceone(String string1,String string2)
{
int flag=0;
for(int j=0;j<string1.length();j++)
{
if(string1.charAt(j)!=string2.charAt(j))
{
flag++;
if(flag>=2)
{
return false;
}
}
}
if(flag==1)return true;
else return false;
}
public static boolean insertone(String string1,String string2)
{
for(int j=0;j<string2.length();j++)
{
StringBuffer s=new StringBuffer();
for(int i=0;i<string2.length();i++)
{
if(i==j)continue;
s.append(string2.charAt(i));
}
if(string1.compareTo(new String(s))==0)
{
return true;
}
}
return false;
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String strings[]=new String[100011];
int count=0;
while((strings[count]=scanner.next()).compareTo("#")!=0)
{
count++;
}
String string1;
while((string1=scanner.next()).compareTo("#")!=0)
{
int flag=1;
System.out.print(string1);
for(int i=0;i<count;i++)
{
String str=strings[i];
if(string1.length()==str.length()&&str.compareTo(string1)==0)
{
System.out.println(" is correct");flag=0;break;
}
}
if(flag==1){
System.out.print(":");
for(int i=0;i<count;i++)
{
String str=strings[i];
if(Math.abs(string1.length()-str.length())>1)continue;
if(string1.length()==str.length())
{
//replacing of one letter in the word with an arbitrary letter
if(replaceone(str, string1))
System.out.print(" "+str);
}
//deleting of one letter from the word
else if(string1.length()==(str.length()-1))
{
if(deleteone(str, string1))
System.out.print(" "+str);
}
//inserting of one arbitrary letter into the word
else if(string1.length()==str.length()+1)
{
if(insertone(str, string1))
System.out.print(" "+str);
}
}
System.out.println();
}
}
}
}
nyoj 最开始ac代码，数据太弱了
import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
class result implements Comparable<result>
{
String string;
int position;
public result(String string,int pos) {
// TODO Auto-generated constructor stub
this.string=string;
this.position=pos;
}
public int compareTo(result result)
{
return this.position-result.position;
}
}
class node
{
String string;
Vector<String>vector=new Vector<String>();
Vector<Integer>pos=new Vector<Integer>();
}
public class Main {
static node nodes[];
static result results[];
static Vector<String>vector=new Vector<String>();
public static boolean equals(String string)
{
for(int i=0;i<vector.size();i++)
{
if(string.compareTo(vector.get(i))==0)
return true;
}
return false;
}
public static boolean deleteone(String string1,String string2)
{
int flag=0;
for(int j=0;j<string1.length();j++)
{
String s="";
for(int i=0;i<string1.length();i++)
{
if(i==j)continue;
s+=string1.charAt(i);
}
// System.out.println(s);
if(string2.compareTo(s)==0)
{
flag=1;break;
}
}
if(flag==1)return true;
else return false;
}
public static boolean replaceone(String string1,String string2)
{
int flag=0;
for(int j=0;j<string1.length();j++)
{
if(string1.charAt(j)!=string2.charAt(j))
{
flag++;
}
}
if(flag==1)return true;
else return false;
}
public static boolean insertone(String string1,String string2)
{
int flag=0;
for(int j=0;j<string2.length();j++)
{
String s="";
for(int i=0;i<string2.length();i++)
{
if(i==j)continue;
s+=string2.charAt(i);
}
if(string1.compareTo(s)==0)
{
flag=1;break;
}
}
if(flag==1)return true;
else return false;
}
public static void otherconditions(int id,String string)
{
//deleting of one letter from the word
for(int i=0;i<vector.size();i++)
{
String str=vector.get(i);
if(string.length()==(str.length()-1)&&deleteone(str, string))
{
nodes[id].vector.add(str);
nodes[id].pos.add(i);
}
}
//replacing of one letter in the word with an arbitrary letter
for(int i=0;i<vector.size();i++)
{
String str1=vector.get(i);
if(string.length()==1&&str1.length()==1)
{
nodes[id].vector.add(str1);
nodes[id].pos.add(i);
continue;
}
if(string.length()==str1.length()&&replaceone(str1, string))
{
nodes[id].vector.add(str1);
nodes[id].pos.add(i);
}
}
//inserting of one arbitrary letter into the word
for(int i=0;i<vector.size();i++)
{
String str2=vector.get(i);
if(string.length()==str2.length()+1&&insertone(str2, string))
{
nodes[id].vector.add(str2);
nodes[id].pos.add(i);
}
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(true)
{
String string=scanner.next();
if(string.compareTo("#")==0)break;
vector.add(string);
}
nodes=new node[55];
results=new result[100001];
for(int u=0;u<54;u++)
{
nodes[u]=new node();
}
int i=0;
while(true)
{
String string1=scanner.next();
if(string1.compareTo("#")==0)break;
nodes[i]=new node();
nodes[i].string=string1;
i++;
}
for(int j=0;j<i;j++)
{
if(equals(nodes[j].string))
{
System.out.print(nodes[j].string+" is correct");
}
else
{
otherconditions(j,nodes[j].string);
System.out.print(nodes[j].string+":");
int k;
for(k=0;k<nodes[j].vector.size();k++)
{
results[k]=new result(nodes[j].vector.get(k), nodes[j].pos.get(k));
}
Arrays.sort(results,0,k);
for(int p=0;p<k;p++)
{
System.out.print(" "+results[p].string);
}
}
System.out.println();
}
}
}