poj1035Spell_checker

字符串的模拟题,先给定一个字典.如果给定的单词在字典中出现过,那么输出 XXX is correct

否则尝试删除,替换,插入一个字母,如果变换后的单词在字典中出现,则按先后顺序输出.

大体思路:

字符串的模拟题.暴力就可以过.分析见代码注释

//bnu1154
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dlen[10005],clen[55];
char dir[10005][20];
char check[55][20];

int n,m;

//替换一个字母
bool replace(char *s1,char *s2)
{
    int cc=0,i=0;
    while(s1[i]!='\0')
    {
        if(s1[i]!=s2[i])
        {
            cc++;
            if(cc>1) return false;
            //不同字母数目大于1,直接退出
        }
        i++;
    }
    return true;
}

//删除一个字母和添加一个字母是相同的操作
//替换一下两个单词的顺序就可以了
bool myadd(char *s1,char *s2)
{
    int cc=0,i=0,j=0;
    while(s1[i]!='\0')
    {
        if(s1[i]!=s2[j])
        {
            i++;
            cc++;
        }
        else
        {
            i++;
            j++;
        }
        if(cc>1) return false;
    }
    return true;
}

bool judge(int kk)
{
    int flag=0;
    for(int i=0;i<n;i++)
        dlen[i]=strlen(dir[i]);
    for(int i=0;i<n;i++)
    {
        if(strcmp(check[kk],dir[i])==0)
        {
            printf("%s is correct",check[kk]);
            return true;
        }
    }
    printf("%s:",check[kk]);
    for(int i=0;i<n;i++)
    {
        if(dlen[i]-clen[kk]==0)//单词长度相同,可以尝试替换字母
        {
            if(replace(dir[i],check[kk]))
                printf(" %s",dir[i]);
        }
        //下面两种情况都是长度只差为一的,可以进行添加或者删除一个字母的操作
        else if(dlen[i]-clen[kk]==1)
        {
            if(myadd(dir[i],check[kk]))
                printf(" %s",dir[i]);
        }
        else if(clen[kk]-dlen[i]==1)
        {
            if(myadd(check[kk],dir[i]))
                printf(" %s",dir[i]);
        }
    }
    return true;
}
int main()
{
    char tt[20];
    n=m=0;
    while(1)
    {
        scanf("%s",dir[n]);
        if(dir[n++][0]=='#') 
            break;
    }
    while(1)
    {
        scanf("%s",check[m]);
        if(check[m++][0]=='#') 
            break;
    }
    n--;
    m--;
    for(int j=0;j<m;j++)
    {
        clen[j]=strlen(check[j]);
        judge(j);
        printf("\n");
    }
    return 0;
}