tre树！

前缀统计

思路

首先，这个算法提示是tre树，这就给了思路：先将s挂上tre树，再将询问的便利一下树，就可以AC拉！

有人会问：这部会超时吗？但字符串总长$10^6$，不会超时的！

代码

#include<bits/stdc++.h>
using namespace std;

char s[1000005], t[1000005];
int tot = 1, n, m, ans;
int cnt[1000005], trie[1000005][26];

void ins() {
    scanf("%s",s+1);
    int len=strlen(s+1),p=1;
    for (int i=1;i<=len;++i){
        int ch=s[i]-'a';
        if(!trie[p][ch])
            trie[p][ch] = ++tot;
        p=trie[p][ch];
    }
    cnt[p]++;
}

int main() {
    cin>>n>>m;
    for (int i = 1; i <= n; ++i){
    	ins();
	}
    for (int i = 1; i <= m; ++i) {
        ans = 0;
        scanf("%s", t + 1);
        int len = strlen(t + 1), p = 1;
        for (int j = 1; j <= len; ++j) {
            int ch = t[j] - 'a';
            if (trie[p][ch])
                p = trie[p][ch], ans += cnt[p];
            else
                break;
        }
        printf("%d\n", ans);
    }
    return 0;
}