一道经典的Trie Tree模板题,通过维护一个cnt数组记录在当前节点结束的字符串数量,最后统计全部搜索过程中每个节点cnt值得累加即可得到答案。

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

int n,m,tot;
int tire[MAXN][26];
int cnt[MAXN];

void insert(string x) {
    int p = 0;
    for(unsigned long int i = 0; i < x.length(); ++i) {
        int ch = x[i] - 'a';
        if(!tire[p][ch])
            tire[p][ch] = ++tot;
        p = tire[p][ch];
    }
    ++cnt[p];
}

int search(string x) {
    int p = 0,sum = 0;
    for(unsigned long int i = 0; i < x.length(); ++i) {
        p = tire[p][x[i] - 'a'];
        if(!p)
            break;

        sum += cnt[p];
    }

    return sum;
}

int main() {
    scanf("%d%d",&n,&m);

    string x;
    char temp[MAXN];
    for(int i = 1; i <= n; ++i) {
        scanf("%s",temp);
        x = temp;
        insert(x);
    }

    for(int i = 1; i <= m; ++i) {
        scanf("%s",temp);
        x = temp;
        printf("%d\n",search(x));
    }

    return 0;
}
Last modification:March 5th, 2020 at 12:13 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏