#include <stdio.h >
#include <stdlib.h>
#include <string.h>
#define  true  1
#define  false 0
#define  MAX 26
typedef struct TrieNode{
        int     isStr;
        struct TrieNode*  next[MAX];
        int      page;
}Trie;

typedef struct OutPut{
    char s[20];
    int  order;
}OutPut;
int cmp(const void* a,const void*  b)
{
    return  ((OutPut*)a)->order-((OutPut*)b)->order;
}
void insert(Trie *root,char *s,int k)
{
    int  i;
    Trie *p=root;
    if(root==NULL||*s=='\0')return;
    while(*s!='\0')
    {
        if(p->next[*s-'a']==NULL)        //如果不存在，则建立结点
        {
            Trie *temp=(Trie *)malloc(sizeof(Trie));
            for(i=0;i<MAX;i++)
                temp->next[i]=NULL;
            temp->isStr=false;
            p->next[*s-'a']=temp;
            p=p->next[*s-'a'];
        }
        else
            p=p->next[*s-'a'];
        s++;
    }
    p->isStr=true;
    p->page=k;
}
int search(Trie *root,char *s)
{
    Trie *p=root;
    while(p!=NULL&&*s!='\0')
    {
        p=p->next[*s-'a'];
        s++;
    }
    if(p!=NULL&&p->isStr==true)
    return p->page;
    else return false;
}
void del(Trie *root)
{
    int i;
    for(i=0;i<MAX;i++)
    {
        if(root->next[i]!=NULL)
        {
            del(root->next[i]);
        }
    }
    free(root);
}
void solve(Trie *root,const char *s)
{
    int  len,position,i,j;
    char sTemp[20];
    OutPut prt[20];
    int  status;
    len =strlen(s);

   // printf("%d",status=search(root,s));
    if(search(root,s))
    printf("%s is correct",s);

    else{
        printf("%s: ",s);
        for(position=0,j=0;position<len;position++)//position
        {
            for(i=0;i<position;i++)sTemp[i]=s[i];
            for(++i;i<len;i++)sTemp[i-1]=s[i];
            sTemp[i-1]='\0';
            if(status=search(root,sTemp))
            {
                strcpy(prt[j].s,sTemp);
                prt[j].order=status;
                j++;
            }
        }
        /*********接下来考虑替换一个单词的情况*****/
        for(position=0;position<len;position++)
        {
            strcpy(sTemp,s);
            for(i=0;i<26;i++)
            {   sTemp[position]='a'+i;
                if(status=search(root,sTemp))
                {
                    //printf("Replace......................\n");
                    strcpy(prt[j].s,sTemp);
                    prt[j].order=status;
                    j++;
                }
            }
        }
        /***接下来考虑最复杂的情况：增添一个单*****/
        for(position=0;position<=len;position++)
        {
           for(i=0;i<position;i++)
           sTemp[i]=s[i];
           for(++i;i<=(len+1);i++)//=代表将'\0'一起copy
           sTemp[i]=s[i-1];
           for(i=0;i<26;i++)//分别插入26个字母的情况
           {
              sTemp[position]='a'+i;
              if(status=search(root,sTemp))
              {
                //printf("Add.......................\n");
                strcpy(prt[j].s,sTemp);
                prt[j].order=status;
                j++;
              }
           }
        }
        qsort(prt,j,sizeof(prt[0]),cmp);
        for(i=0;i<j;i++)
        {
            printf("%s ",prt[i].s);
            if(prt[i].order==prt[i+1].order)i++;
        }
    }
    printf("\n");
}
int main()
{
    Trie *root;
    int  i;
    char s[20];
    //printf("%d",i=3);
    root=(Trie*)malloc(sizeof(Trie));
    memset(root->next,0,MAX*sizeof(Trie*));
    root->isStr=false;
    i=1;
    while(scanf("%s",s)&&strcmp(s,"#")!=0)
    {insert(root,s,i);i++;}
    while(scanf("%s",s)&&strcmp(s,"#")!=0)
    {
        solve(root,s);
    }
    return 0;
}

• Re:有神牛来检查下我的程序么？试了discuss里的所有数据，不知WA在何处 (29) StepByStepCnmLife 2015-05-09 14:34:02
• Re:蠢死了 (76) StepByStepCnmLife 2015-05-09 15:54:43