hdu1251,为什么我的代码是WA的，哪位大佬帮我看看？

Question

这是我的代码：

#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>

using namespace std;

struct trie {
    int nex[100000][26], cnt;
    bool exist[1000000];//该结点结尾的字符串是否存在

    void insert(char *s, int l) {//插入字符串
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) {
                nex[p][c] = ++cnt;
            }
            p = nex[p][c];
            exist[p]+=1;
        }
    }

    bool find(char *s, int l) {//查找字符串
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) return 0;
            p = nex[p][c];
        }
        return exist[p];
    }
};

trie tri;
char str[23];
int len;

int main() {
    while (gets(str)) {
        len = strlen(str);
        if (len == 0) break;
        tri.insert(str, len);
    }
    while (gets(str)) {
        len = strlen(str);
        printf("%d\n", tri.find(str, len));
    }

    return 0;
}

这是别人的代码：

#include<cstring>
#include<cstdio>

using namespace std;

const int maxn=500000;
char wen[20];

struct node{
    int tot;
    int child[26];
    node(){
        tot=0;
        memset(child,0,sizeof(child));
    }
}tree[maxn];

int sz=0;

void insert(char *s){
    int u=0;
    int h=strlen(s);
    for(int i=0;i<h;i++){
        int pos=s[i]-'a';
        if(tree[u].child[pos]==0){
            tree[u].child[pos]=++sz;
        }
        u=tree[u].child[pos];
        tree[u].tot++;
    }
}

int find(char *t){
    int u=0;
    int h=strlen(t);
    for(int i=0;i<h;i++){
        int pos=t[i]-'a';
        if(tree[u].child[pos]==0){
            return 0;
        }
        u=tree[u].child[pos];
    }
    return tree[u].tot;
}

int main(){
    while(gets(wen)){
        if(strlen(wen)==0)  break;
        insert(wen);
    }
    while(gets(wen)){
        printf("%d\n",find(wen));
    }
    return 0;
}

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 关于该问题，我找了一篇非常好的博客，你可以看看是否有帮助，链接：字典树（HDU1251，1247）

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 以帮助更多的人 ^-^