POJ 1035 Spell checker解题报告

一、问题描述

题目：

题目大意：输入一个字典，然后对于输入的每个字符串判断是不是字典时的单词，如果不是那么找到所有相似的单词，相似比输入的字符串多一个字符，或者少一个字符，或者只有一个字符不同。按字典里的顺序输出结果。比如：
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

二、解题思想

从头到尾查找字典时的单调，如果有相同的则停止，有相近的则先保存起来，查找完所有单词后再输出。

三、代码

 

#include<iostream>
#include<string>
using namespace std;
char str[10005][20];
unsigned ans[10000];
unsigned len[10005];
int N;
int isSame(char * s,int b)
{
    int i,j;
    int slen=strlen(s);
    if(abs(slen-len[b])>1)
    {
        return -1;
    }
    bool flag=false;
    if(slen==len[b])
    {
        for(i=0;i<slen;++i)
        {
            if(s[i]!=str[b][i])
            {
                if(flag ==false)
                    flag=true;
                else
                    return -1;
            }
        }
        if(flag==false)
            return 0;
        else
            return 1;
    }
    else
    {
        i=0;j=0;
        for(;i<slen && j<len[b];)
        {
            if(s[i]!=str[b][j])
            {
                if(flag)
                {
                    return -1;
                }
                else
                {
                    flag=true;
                    if(slen > len[b])
                        i++;
                    else
                        j++;
                }
            }
            else
            {
                i++;
                j++;
            }
        }
        return 1;
    }
}
int main()
{
    int i,j;
    i=0;
    while(scanf("%s",&str[i]))
    {
        
        if(str[i][0]=='#')
            break;
        len[i]=strlen(str[i]);
        i++;
    }
    N=i;
    char word[20];
    int n;
    bool flag=false;
    while(scanf("%s",word))
    {
        if(word[0]=='#')
            break;
        printf("%s",word);
        n=0;
        flag =false;
        for(j=0;j<N;++j)
        {
            int re=isSame(word,j);
            if(re==0)
            {
                printf(" is correct\n");
                flag=true;
                break;
            }
            else
            {
                if(re==1)
                {
                    ans[n++]=j;
                }
            }
        }
        if(flag)
            continue;
        printf(":");
        for(i=0;i<n;++i)
        {
            printf(" %s",str[ ans[i] ]);
        }
        printf("\n");
    }
    
    return 0;
}