poj 1035 Spell checker（查找）

Memory: 508K

Time: 563MS

解题思路

题意：

    检查单词。检查一系列单词，如果存在在字典中输出“is correct”，如果跟字典中的某些单词长度相同但只是其中一个字母不同，或者比字典中某些单词少个字母或多一个字母，都把字典中那个单词输出来。

 

思路：

   分类讨论，①，用二分搜索查找是否有相同的单词，②枚举字典中每个单词，如果长度跟被检查单词相同，那么两个单词中的字母一一对照，如果有一个字母不同那么输出那个单词，③，如果长度相差一，那么长的那个单词把每个字母去掉试试，如果少个字母后跟另一个相同，那么输出。后面两种情况可能输出多个单词，要注意按给出的字典顺序输出。

源程序

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define N 10004

typedef struct
{
    char word[16];
    int lens;
}d;
d dic[N];

int cmp(const void *p, const void *q)
{
    return strcmp((char *)p, (char *)q);
}

int main()
{
    int i, j, n, count, k, clen;
    char ch[16], dic2[N][16], check[16],*p;
    i = 0;

    freopen("in.txt", "r", stdin);
    while(strcmp(gets(dic[i].word), "#"))
    {
        dic[i].lens = strlen(dic[i].word);
        i++;
    }
    
    n = i;
    for(i=0; i<n; i++)
        strcpy(dic2[i], dic[i].word); //用bsearch的时候需要把数组排序，

    qsort(dic2, n, sizeof(dic2[0]), cmp); //而后面处理各种情况的时候又要用到原来的顺序，所以把字典备份一个

    while(strcmp(gets(check), "#"))
    {
        p = (char *)bsearch(&check, dic2, i, sizeof(dic2[0]), cmp);
        if(p)
            printf("%s is correct", check); //找到有相同的
        else
        {
            clen = strlen(check);
            printf("%s:", check);
            
            for(i=0; i<n; i++)
            {
                count = 0;
                if(dic[i].lens == clen) //长度相同
                {
                    for(j=0; j<dic[i].lens; j++) //看看不同的字母有几个
                    {
                        if(dic[i].word[j] != check[j])
                            count++;
                        if(count > 1)
                            break;
                    }            
                    if(count == 1) //如果只有一个
                        printf(" %s", dic[i].word);
                }
                else if(dic[i].lens == clen+1) //被检查的长度小
                {
                    strcpy(ch, dic[i].word);
                    for(j=0; j<dic[i].lens; j++)
                    {                        
                        for(k=j; k <dic[i].lens; k++)
                            dic[i].word[k] = dic[i].word[k+1]; //从第一个到最后一个字母去掉试试

                        if(strcmp(dic[i].word, check) == 0) //如果跟被检查的单词相同了，就输出

                        {
                            printf(" %s", ch);
                            strcpy(dic[i].word, ch);
                            break;
                        }
                        strcpy(dic[i].word, ch);
                    }

                }
                else if(dic[i].lens == clen-1) //被检查的长度大 原理同上
                {
                    strcpy(ch, check);
                    for(j=0; j<clen; j++)
                    {
                        for(k=j; k<clen; k++)
                            check[k] = check[k+1];
                        if(strcmp(dic[i].word, check) == 0)
                        {
                            printf(" %s", dic[i].word);
                            strcpy(check, ch);
                            break;
                        }
                        strcpy(check, ch);
                    }
                }
            }        
        }
        printf("\n");
    }
    getch();
    return 0;
}