题目地址：POJ 1035

题意：输入一部字典。输入若干单词。 若某个单词能在字典中找到，则输出corret。若某个单词能通过 变换 或 删除 或 加入一个字符后。在字典中找得到。则输出这些单词。输出顺序依据 输入的那部字典的字典序；若某个单词不管操作与否都无法在字典中找得到，则输出空。

思路：关于全然匹配的就直接输出就好。解题关键在不全然匹配的情况：比較时我们先算两个单词长度差之差，有三种情况：len1=strlen(str)len2=strlen(mp[n]]

假设len1==len2则是可能有一个字符不一样；逐个字符比較。统计不同字符数

假设len1+1==len2则是少一个字符。逐个字符比較，假设有字符不同。则mp[n]字符下标往下移动一位。str不变，不同字符数加1

假设len1-1==len2则是多一个字符，逐个字符比較。假设有字符不同。则str字符下标往下移动一位。mp[n]不变。不同字符数加1

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <map>

#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef __int64  LL;

const int inf=0x3f3f3f3f;

const double pi= acos(-1.0);

const double esp=1e-7;

const int maxn=10010;

char mp[maxn][20];

char str[20];

int check(int n)

{

    int i,j;

    int cnt;

    int len1=strlen(str);

    int len2=strlen(mp[n]);

    if(len1-len2==1) {

        cnt=0;

        i=j=0;

        for(; i<len1;) {

            if(str[i]!=mp[n][j]) {

                cnt++;

                i++;

            } else {

                i++;

                j++;

            }

        }

        if(cnt==1)

            return 1;

        return 0;

    } else if(len1==len2) {

        cnt=0;

        i=j=0;

        for(; i<len1;) {

            if(str[i]!=mp[n][j])

                cnt++;

            i++,j++;

        }

        if(cnt==1)

            return 1;

        return 0;

    } else if(len1-len2==-1) {

        cnt=0;

        i=j=0;

        for(; j<len2;) {

            if(str[i]!=mp[n][j]) {

                cnt++;

                j++;

            } else {

                i++;

                j++;

            }

        }

        if(cnt==1)

            return 1;

        return 0;

    }

    return 0;

}

int main()

{

    int n=0,i;

    while(~scanf("%s",mp[n])) {

        if(mp[n][0]=='#')

            break;

        n++;

    }

    while(~scanf("%s",str)) {

        if(str[0]=='#')

            break;

        for(i=0; i<n; i++) {

            if(strcmp(str,mp[i])==0) {

                printf("%s is correct\n",str);

                break;

            }

        }

        if(i==n) {

            printf("%s:",str);

            for(i=0; i<n; i++)

                if(check(i))

                    printf(" %s",mp[i]);

            puts("");

        }

    }

    return 0;

}