RE求调

P8306 【模板】字典树

visit @ 2024-11-20 06:44:01

#include<bits/stdc++.h>
using namespace std;
int t,n,q,csl;
char cs[3000100];
char Trie[3001000][100];
bool ed[3000100];//标记结尾
int sum[3000100];//count(每个点对应几个字符串)
int m=1;
void biuld_Trie()
{
    //建立Trie出现过就直接放,没出现过就让总数(下标位)+1 储存
    //Trie大小与字符串总长度有关<=sum_len
    //root=1   ->   k
    int k=1;
    for(int i=1;i<=csl;i++)
    {
        char cc=cs[i];
        int c=cc-'0';
        if(!Trie[k][c])//从第k个点做向c的边
            Trie[k][c]=++m;     
        k=Trie[k][c];
        sum[k]++;
    }
    ed[k]=1;
}
int find_Trie()
{
    int k=1;
    for(int i=1;i<=csl;i++)
    {
        char cc=cs[i];
        int c=cc-'0';
        if(!Trie[k][c])
        {
            k=1;
            break;
        }
        k=Trie[k][c];
    }
    return sum[k];
}
int main()
{
    cin>>t;
    while(t--)
    {
        memset(sum,0,sizeof(sum));
        memset(Trie,0,sizeof(Trie));
        memset(ed,0,sizeof(ed));
        m=1;
        cin>>n>>q;
        for(int i=1;i<=n;i++)
        {
            cin>>cs+1;
            csl=strlen(cs+1);
            biuld_Trie();
        }
        for(int i=1;i<=q;i++)
        {
            cin>>cs+1;
            csl=strlen(cs+1);
            cout<<find_Trie()<<endl;
        }
    }
    return 0;
}

by 立柱已选162534 @ 2024-11-20 07:50:25

@visit 把char Trie改为int Trie并把endl改为'\n'即可。

999555 qp


by visit @ 2024-11-20 17:26:39

@立柱已选162534 好的谢谢,调好了,(好像数组还开大了,然后memset还得手动。。。 底子差了


|