POJ1035

#include <iostream>   
#include <cstdio>   
#include <cstring>   
#include <vector>   
#include <algorithm>   
using namespace std;  
struct vv  
{  
    char s[20];  
    int id;  
}v[10005];  
int cnt=0;  
int cmp(struct vv x,struct vv y)  
{  
   return strlen(x.s)<strlen(y.s);  
}  
int cmp2(struct vv x,struct vv y)  
{  
    return x.id<y.id;  
}  
void judge(char *s)  
{  
    vector<struct vv> test;  
    int num=strlen(s);  
    test.clear();  
    for(int i=0;i<cnt;i++)  
    {  
        if(!strcmp(s,v[i].s)) {printf("%s is correct\n",s);return;}  
        if(strlen(v[i].s)==num||strlen(v[i].s)==num-1||strlen(v[i].s)==num+1)  
            {  
                test.push_back(v[i]);  
            }  
    }  
    sort(test.begin(),test.end(),cmp2);  
    int ok=0;  
    printf("%s: ",s);  
    for(int i=0;i<test.size();i++)  
    {  
        if(strlen(test[i].s)==num-1)  
        {  
            int ok=0;  
            for(int j=0;j<num;j++)  
            {  
                if(ok==0&&test[i].s[j]==s[j])  
                  continue;  
                if(ok==1&&test[i].s[j-1]==s[j])  
                  continue;  
                else  
                {  
                    if(ok==0) ok=1;  
                    else {ok=2;break;}  
                }  
            }  
            if(ok!=2) printf("%s ",test[i].s);  
        }  
        if(strlen(test[i].s)==num)  
        {  
            int count=0;  
            for(int j=0;j<num;j++)  
                if(test[i].s[j]==s[j]) count++;  
            if(count==num-1)  
                printf("%s ",test[i].s);  
        }  
        if(strlen(test[i].s)==num+1)  
        {  
            int ok=0;  
            for(int j=0;j<num+1;j++)  
            {  
                if(ok==0&&test[i].s[j]==s[j])  
                    continue;  
                if(ok==1&&test[i].s[j]==s[j-1])  
                    continue;  
                else  
                {  
                    if(ok==0) ok=1;  
                    else {ok=2;break;}  
                }  
            }  
            if(ok!=2) printf("%s ",test[i].s);  
        }  
    }  
    printf("\n");  
}  
int main()  
{  
    char temp[20];  
    while(true)  
    {  
         scanf("%s",temp);  
         if(!strcmp(temp,"#")) break;  
         else {  
                strcpy(v[cnt].s,temp);  
                v[cnt].id=cnt;  
                cnt++;  
              }  
    }  
    sort(v,v+cnt,cmp);  
    struct vv check[55];  
    while(true)  
    {  
        scanf("%s",temp);  
        if(!strcmp(temp,"#")) break;  
        else judge(temp);  
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct vv
{
    char s[20];
    int id;
}v[10005];
int cnt=0;
int cmp(struct vv x,struct vv y)
{
   return strlen(x.s)<strlen(y.s);
}
int cmp2(struct vv x,struct vv y)
{
    return x.id<y.id;
}
void judge(char *s)
{
    vector<struct vv> test;
    int num=strlen(s);
    test.clear();
    for(int i=0;i<cnt;i++)
    {
        if(!strcmp(s,v[i].s)) {printf("%s is correct\n",s);return;}
        if(strlen(v[i].s)==num||strlen(v[i].s)==num-1||strlen(v[i].s)==num+1)
            {
                test.push_back(v[i]);
            }
    }
    sort(test.begin(),test.end(),cmp2);
    int ok=0;
    printf("%s: ",s);
    for(int i=0;i<test.size();i++)
    {
        if(strlen(test[i].s)==num-1)
        {
            int ok=0;
            for(int j=0;j<num;j++)
            {
                if(ok==0&&test[i].s[j]==s[j])
                  continue;
                if(ok==1&&test[i].s[j-1]==s[j])
                  continue;
                else
                {
                    if(ok==0) ok=1;
                    else {ok=2;break;}
                }
            }
            if(ok!=2) printf("%s ",test[i].s);
        }
        if(strlen(test[i].s)==num)
        {
            int count=0;
            for(int j=0;j<num;j++)
                if(test[i].s[j]==s[j]) count++;
            if(count==num-1)
                printf("%s ",test[i].s);
        }
        if(strlen(test[i].s)==num+1)
        {
            int ok=0;
            for(int j=0;j<num+1;j++)
            {
                if(ok==0&&test[i].s[j]==s[j])
                    continue;
                if(ok==1&&test[i].s[j]==s[j-1])
                    continue;
                else
                {
                    if(ok==0) ok=1;
                    else {ok=2;break;}
                }
            }
            if(ok!=2) printf("%s ",test[i].s);
        }
    }
    printf("\n");
}
int main()
{
    char temp[20];
    while(true)
    {
         scanf("%s",temp);
         if(!strcmp(temp,"#")) break;
         else {
                strcpy(v[cnt].s,temp);
                v[cnt].id=cnt;
                cnt++;
              }
    }
    sort(v,v+cnt,cmp);
    struct vv check[55];
    while(true)
    {
        scanf("%s",temp);
        if(!strcmp(temp,"#")) break;
        else judge(temp);
    }
    return 0;
}

硬着头皮写下去就OK了。

主要思维量在于少一个字母和多一个字母的情况，

自己的分析还是对的。就是略掉这个字母看继续比较后面的。

不过裸写的速度不够快，二分的思想自己应着重练一下。

补充：软件开发 , C++ ,

上一个：简单匹配算法测试
下一个：POJ 1655 Balancing Act[树的重心]