poj 1035

总时间限制:

2000ms

内存限制:

65536kB

描述

现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词A与单词B相似的情况有三种：

1、删除单词A的一个字母后得到单词B；

2、用任意一个字母替换单词A的一个字母后得到单词B；

3、在单词A的任意位置增加一个字母后得到单词B。

你的任务是发现词典中与给定单词相同或相似的单词。

 

输入

第一部分是词典中的单词，从第一行开始每行一个单词，以"#"结束。词典中的单词保证不重复，最多有10000个。
第二部分是需要查询的单词，每行一个，以"#"结束。最多有50个需要查询的单词。
词典中的单词和需要查询的单词均由小写字母组成，最多包含15个字符。

输出

按照输入的顺序，为每个需要检查的单词输出一行。如果需要检查的单词出现在词典中，输出“?x is correct"，?x代表需要检查的单词。如果需要检查的单词没有出现在词典中，则输出"?x: ?x1 ?x2 ...?xn"，其中?x代表需要检查的单词，?x1...?xn代表词典中与需要检查的单词相似的单词，这些单词中间以空格隔开。如果没有相似的单词，输出"?x:"即可。

样例输入

i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#

样例输出

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

import java.util.Scanner;
public class Main{
	String str[] = new String[10001];
	

	public static void main(String[] args) {
		new Main().test();

	}

	public void test() {
		Scanner sc = new Scanner(System.in);
		int index = 0;
		String s;
		while (sc.hasNext()) {// 读入字典中的单词
			s = sc.next();
			if (s.equals("#"))
				break;
			else
				str[index++] = s;
		}
		while (sc.hasNext())// 读入写入的单词
		{
			s = sc.next();
			if (s.equals("#"))
				break;
			else
				strCompare(s, index);
		}

	}
   /*
   删除字符中的一个元素
   */
    public String strChange(String s,int index,int len)
    {    String temp, temp1;
    	 if(index==0){
    		temp = s.substring(index+1) ;
    	 }else if(index==len-1){
    		 temp = s.substring(0, index);
    	 }else{
    		 temp = s.substring(0,index) ;
    		 temp1 = s.substring(index+1) ;
    		 temp =temp +temp1 ;
    	 }
    //	 System.out.println(temp);
    	return temp ;
    }
   /*
   *字符串比较
   */
	public void strCompare(String s, int index) {
		int i, j;
		for (i = 0; i < index; i++) {//相等后返回
			if (s.equals(str[i])) {
				System.out.println(s + " is correct");
				return;
			}
		}
		System.out.print(s + ":");
		//不相等时
		for (i = 0; i < index; i++) {//遍历字典
			if (s.length() == (str[i].length() + 1)) {//待测单词长度为字典单词加1
				for (j = 0; j < s.length(); j++) {
				//	System.out.println(str[i]);
				String temp = strChange(s,j,s.length());
					if (temp.equals(str[i])) {
						System.out.print(" " + str[i]);
						break;
					}

				}
			}else if(s.length() == (str[i].length()-1))
			{
				for (j = 0; j < str[i].length(); j++) {
					//System.out.println(str[i]) ;
				String s1 = strChange(str[i],j,str[i].length()) ;
				if(s1.equals(s))
				{   
				//	System.out.print("哈哈");
					System.out.print(" " + str[i]);
					break ;
				}
				}
			}
			else if(s.length() == str[i].length())
			{
				for(j=0;j<s.length();j++)
				{ 
					//System.out.println(str[i]);
				String	s1 = strChange(s,j,s.length());
				String	s2 = strChange(str[i],j,str[i].length()) ;
					if(s1.equals(s2))
					{
						System.out.print(" " + str[i]);
						break ;
					}
				}
			}
		}
		System.out.println();
	}
}

 解决二 ： G++：

#include <stdio.h>
#include <string.h>
int Find(int a);
int n;
int lend[10001];
char Dt[10001][20],In[20],len;
int Find(int a)
{
    int i,t;
    t=lend[a]-len;
    if (t==-1)
    {
       for (i=0;i<lend[a]&&Dt[a][i]==In[i];i++);
        for (;i<lend[a]&&Dt[a][i]==In[i+1];i++);
        if (i==lend[a])
            return 0;
    }
    else if (t==0)
    {
        for (i=0;i<len&&Dt[a][i]==In[i];i++);
        for (i++;i<len&&Dt[a][i]==In[i];i++);
        if (i==len)
            return 0;
    }
    else if (t==1)
    {
        for (i=0;i<len&&Dt[a][i]==In[i];i++);
        for (;i<len&&Dt[a][i+1]==In[i];i++);
        if (i==len)
            return 0;
    }
    return 1;
}
int main()
   {
    int i;
    scanf("%s",&Dt[0][0]);
    while (Dt[n][0]!='#')
    {
        lend[n]=strlen(Dt[n]);
        scanf("%s",&Dt[++n][0]);
    }
    scanf("%s",In);
    while (In[0]!='#')
    {
        len=strlen(In);
        for (i=0;i<n;i++)
            if (lend[i]==len&&strcmp(Dt[i],In)==0)
            {
                    printf("%s is correct\n",In);
                break;
          }
            if (i==n)
            {
                printf("%s:",In);
                for (i=0;i<n;i++)
                    if (Find(i)==0) printf(" %s",Dt[i]);
                    printf("\n");
            }
            scanf("%s",In);
    }    return 0;
}