POJ_1035_水题_字符串

题目链接：
http://poj.org/problem?id=1035




思路是，拿每个带检测字符串和整个字典里的字进行比较，如果有一样的即为correct,如果没有一样的分三种情况:
1.长度相同.
2.带检测字长度比字典里的字少1
3.带检测字长度比字典里的字多1

长度相同时检查不同字符的个数（为1时即可以替换），长度不同时拿较短的字去匹配较长的字，较短字每个字符在较长字中的位置存放在一个数组里，匹配完成后，扫描数组看是否为递增的，并且每一个字符都在较长字中出现。

#include<stdio.h>
#include<string.h>
#define SIZE 11000
char dic[SIZE][20];
int cnt;
void read_dic()//读取字典
{
     cnt = 0;
     while(scanf("%s%*c",dic[cnt]))
     {
        if(dic[cnt][0]=='#')
        break;
        else
        cnt++;
     }
}
bool isCor(char *str)//是否正确 
{
     int i;
     for(i=0;i<cnt;i++)
     if(strcmp(dic[i],str)==0)return true;
     return false;
} 
void Replace(char *str)//替换
{
     printf("%s:",str);
     int i,j,k,arr[20],diff,isSort;
     int ls = strlen(str),ld;
     for(i=0;i<cnt;i++)
     {
        ld = strlen(dic[i]);
        if(ls==ld)//如果长度相同 
        {
            diff = 0;
            for(j=0;j<ld;j++)
            {
               if(str[j]!=dic[i][j]) diff++;
            }
            if(diff==1)printf(" %s",dic[i]);
        }
        else if(ls==ld+1)//delete
        {
            memset(arr,-1,sizeof(arr));
            for(j=0;j<ld;j++)
            {
               for(k=j==0?0:arr[j-1]+1;k<ls;k++)
               {
                  if(str[k]==dic[i][j])
                  {
                      arr[j] = k;
                      break;
                  }
               }
            }
            isSort = 1;
            //检查arr是否有序
            for(j=0;j<ld-1;j++)
            {
               if(arr[j+1]<arr[j]||arr[j]==-1)
               {
                  isSort = 0;
                  break;
               }
            } 
            if(arr[ld-1]==-1)isSort = 0;
            if(isSort)printf(" %s",dic[i]);
        }
        else if(ls+1==ld)//add
        {
            memset(arr,-1,sizeof(arr));
            for(j=0;j<ls;j++)
            {
               for(k=j==0?0:arr[j-1]+1;k<ld;k++)
               {
                  if(str[j]==dic[i][k])
                  {
                      arr[j] = k;
                      break;
                  }
               }
            }
            isSort = 1;
            //检查arr是否有序
            for(j=0;j<ls-1;j++)
            {
               if(arr[j+1]<arr[j]||arr[j]==-1)
               {
                  isSort = 0;
                  break;
               }
            } 
            if(arr[ls-1]==-1)isSort = 0;
            if(isSort)printf(" %s",dic[i]);
        }
     }
} 
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    read_dic();
    char str[20];
    while(scanf("%s%*c",str),str[0]!='#')
    {
        if(isCor(str))
        printf("%s is correct\n",str);
        else
        {
           Replace(str);
           printf("\n");
        }
    }
}