20pts求助！悬关！！！

hnxxwpf @ 2024-10-06 14:50:48

#include<iostream>
#include<algorithm>
using namespace std;
const int len = 3e6 + 1, maxn = 1e5 + 1;
int nxt[len][65], exist[len], cnt;
struct Trie
{
    void init()
    {
        cnt = 0;
        for(int i = 0; i <= len; ++i)
        {
            exist[i] = 0;
            for(int j = 0; j <= 65; ++j)
            {
                nxt[i][j] = 0;
            }
        }
    }
    void insert(string s)
    {
        int p = 0, l = s.length();
        for(int i = 0, c; i < l; ++i)
        {
            if(s[i] >= 'A' && s[i] <= 'Z')
            {
                c = s[i] - 'A' + 1;
            }
            else if(s[i] >= 'a' && s[i] <= 'z')
            {
                c = s[i] - 'a' + 26;
            }
            else
            {
                c = s[i] - '0' + 52;
            }
            if(!nxt[p][c])
            {
                nxt[p][c] = ++cnt;
            }
            p = nxt[p][c];
            exist[p]++; 
        }
    }
    int find(string s)
    {
        int p = 0, l = s.length();
        for(int i = 0, c; i < l; ++i)
        {
            if(s[i] >= 'A' && s[i] <= 'Z')
            {
                c = s[i] - 'A' + 1;
            }
            else if(s[i] >= 'a' && s[i] <= 'z')
            {
                c = s[i] - 'a' + 26;
            }
            else
            {
                c = s[i] - '0' + 52;
            }
            if(!nxt[p][c])
            {
                return 0;
            }
            p = nxt[p][c];
        }
        return exist[p];
    }
};
int T;
int main(){
    scanf("%d", &T);
    while(T--)
    {
        Trie trie;
        int n, q;
        scanf("%d %d", &n, &q);
        trie.init();
        for(int i = 0; i < n; ++i)
        {
            string s;
            cin >> s;
            trie.insert(s);
        }
        for(int i = 0; i < q; ++i)
        {
            string t;
            cin >> t;
            printf("%d\n", trie.find(t));
        }
    }
    return 0;
}

by lbh123 @ 2024-10-06 15:01:27

我的代码

#include<bits/stdc++.h>
using namespace std;
int tt,n,q,t[3000010][65],cnt[3000010],idx;
char s[3000010]; 
int sa(char x){
    if(x<='Z'&&x>='A'){
        return x-'A';
    }else if(x<='z'&&x>='a'){
        return x-'a'+26;
    }else{
        return x-'0'+52;
    }
}
void is(char x[]){
    int p=0,si=strlen(x);
    for(int i=0;i<si;i++){
        int y=sa(x[i]);
        if(!t[p][y]){
            t[p][y]=++idx;
        }
        p=t[p][y];
        cnt[p]++;
    }
}
int found(char x[]){
    int p=0,si=strlen(x);
    for(int i=0;i<si;i++){
        int y=sa(x[i]);
        if(!t[p][y]){
            return 0;
        }
        p=t[p][y];
    }
    return cnt[p];
}
int main(){
    scanf("%d",&tt);
    while(tt--){
        for(int i=0;i<=idx;i++){
            for(int j=0;j<=122;j++){
                t[i][j]=0;
            }
        }
        for(int i=0;i<=idx;i++){
            cnt[i]=0;
        }
        idx=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            is(s);
        }
        for(int i=1;i<=q;i++){
            scanf("%s",s);
            printf("%d\n",found(s));
        }
    }
    return 0;
}

by WangSiHan_2011 @ 2024-10-13 08:38:47

两个错误：

1. c = s[i] - 'A' + 1; 改成 c = s[i] - 'A';

2.

void init()
{
  for(int i = 0; i <= cnt; ++i)
  {
    exist[i] = 0;
    for(int j = 0; j <= 65; ++j)
    {
      nxt[i][j] = 0;
    }
  }
  cnt = 0;
}

要不然会TLE

by WangSiHan_2011 @ 2024-10-13 08:39:03

#include<iostream>
#include<algorithm>
using namespace std;
const int len = 3e6 + 1, maxn = 1e5 + 1;
int nxt[len][65], exist[len], cnt;
struct Trie
{
    void init()
    {
        for(int i = 0; i <= cnt; ++i)
        {
            exist[i] = 0;
            for(int j = 0; j <= 65; ++j)
            {
                nxt[i][j] = 0;
            }
        }
        cnt = 0;
    }
    void insert(string s)
    {
        int p = 0, l = s.length();
        for(int i = 0, c; i < l; ++i)
        {
            if(s[i] >= 'A' && s[i] <= 'Z')
            {
                c = s[i] - 'A';
            }
            else if(s[i] >= 'a' && s[i] <= 'z')
            {
                c = s[i] - 'a' + 26;
            }
            else
            {
                c = s[i] - '0' + 52;
            }
            if(!nxt[p][c])
            {
                nxt[p][c] = ++cnt;
            }
            p = nxt[p][c];
            exist[p]++; 
        }
    }
    int find(string s)
    {
        int p = 0, l = s.length();
        for(int i = 0, c; i < l; ++i)
        {
            if(s[i] >= 'A' && s[i] <= 'Z')
            {
                c = s[i] - 'A';
            }
            else if(s[i] >= 'a' && s[i] <= 'z')
            {
                c = s[i] - 'a' + 26;
            }
            else
            {
                c = s[i] - '0' + 52;
            }
            if(!nxt[p][c])
            {
                return 0;
            }
            p = nxt[p][c];
        }
        return exist[p];
    }
};
int T;
int main(){
    scanf("%d", &T);
    while(T--)
    {
        Trie trie;
        int n, q;
        scanf("%d %d", &n, &q);
        trie.init();
        for(int i = 0; i < n; ++i)
        {
            string s;
            cin >> s;
            trie.insert(s);
        }
        for(int i = 0; i < q; ++i)
        {
            string t;
            cin >> t;
            printf("%d\n", trie.find(t));
        }
    }
    return 0;
}