求助,WA第一个和最后一个点

P8306 【模板】字典树

Aakkosetsumussa @ 2023-06-29 10:09:08

#include<bits/stdc++.h>
using namespace std;
typedef long long inr;
typedef unsigned long long unr;
#define fur(y) for(inr i=1;i<=y;i++)
#define fru(i,s,e) for(inr i=s;i<=e;i++)
#define frd(i,s,e) for(inr i=s;i>=e;i--)
#define el <<endl
#define sp <<" "<<
inr n,m,q,T;
inr trie[500005][205],num[500005]= {0},pos=1;
inline void Insert(string str) {
    inr p=0;
    for(inr i=0; i<str.size(); i++) {
        inr n=str[i];
        if(trie[p][n]==0) trie[p][n]=pos++;
        p=trie[p][n];
        num[p]++;
    }
}
inline inr find(string str) {
    inr p=0;
    for(inr i=0; i<str.size(); i++) {
        inr n=str[i];
        if(trie[p][n]==0) return 0;
        p=trie[p][n];
    }
    return num[p];
}
string ch;
main() {
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--) {
        cin>>n>>q;
        for(inr i=0; i<=pos; i++)
            for(inr j=0; j<=200; j++) trie[i][j]=0;
        for(inr i=0; i<=pos; i++) num[i]=0;
        pos=1;
        for(inr i=1; i<=n; i++) {
            cin>>ch;
            Insert(ch);
        }
        for(inr i=1; i<=q; i++) {
            cin>>ch;
            cout<<find(ch)<<endl;
        }
    }
    return 0;
}

by Muh_Yih @ 2023-07-12 16:43:13

数组开小了(我也是这个问题,调了一天才发现())


by Muh_Yih @ 2023-07-12 16:43:50

注意到

输入字符串的总长度不超过 3 \times 10^6


by Muh_Yih @ 2023-07-12 16:46:08

另外数组开int类型足够,long long会太大而 CE


by Muh_Yih @ 2023-07-12 16:46:27

AC 记录


by Muh_Yih @ 2023-07-12 21:01:03

@Aakkosetsumussa


by Aakkosetsumussa @ 2023-07-13 08:05:35

@Muh_Yih

大佬不用了,我后来把数组开大然后把string换成char[]就过了()


by Muh_Yih @ 2023-07-13 18:55:33

@Aakkosetsumussa 是这样(不过其实用string也可以,关键是数组大小)


|