前缀统计

一、题目

题目链接：https://www.acwing.com/problem/content/144/

相关题目：https://www.acwing.com/problem/content/837/

给定 $N$ 个字符串 $S_1,S_2…S_N$，接下来进行 $M$ 次询问，每次询问给定一个字符串 $T$，求 $S_1 \sim S_N$ 中有多少个字符串是 $T$ 的前缀。

输入字符串的总长度不超过 $10^6$，仅包含小写字母。

输入格式

第一行输入两个整数 $N，M$。

接下来 $N$ 行每行输入一个字符串 $S_i$。

接下来 $M$ 行每行一个字符串 $T$ 用以询问。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$1 \le N,M \le 10^5$

输入样例：

3 2
ab
bc
abc
abc
efg

输出样例：

2
0

二、Trie树

1. insert()操作

从根节点开始，同时遍历字符串，每次判断其相关的儿子节点是否存在。如果不存在，则给相关儿子节点赋值为++idx，即让其值不为 $0$ 同时指定一个节点存储该儿子；如果存在，则让p指向其儿子节点，继续遍历。当遍历结束后，计数数组cnt[p]自增，此时，p指向的是字符串的末尾节点。

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

2. query()操作

与insert()操作类似，但其在遍历过程中，遇到不存在的节点直接返回ans的值。遍历到每个节点的时候，都让ans加上以当前节点为结尾的字符串的个数，即cnt[p]。在字符串遍历结束后，ans未加上以遍历最后节点为结尾的字符串的个数，故for循环后再次添加。

int query(char str[])
{
    int p = 0;
    int ans = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        ans += cnt[p];
        if (!son[p][u]) return ans;
        p = son[p][u];
    }
    ans += cnt[p];
    return ans;
}

三、代码

#include <iostream>

using namespace std;

const int N = 1000010, M = 26;	// 全为小写字母M=26

int n, m;
int son[N][M], cnt[N], idx;		// idx相当于每个节点的身份证号(大于0)

void insert(char str[])
{
    int p = 0; 	// 始终指向当前节点，始终判断儿子节点
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;	// 赋予当前节点的儿子节点身份
        p = son[p][u];	// 继续看儿子节点
    }
    cnt[p] ++ ;     // 以编号p为结尾的字符串个数
}

int query(char str[])
{
    int p = 0;
    int ans = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        ans += cnt[p];
        if (!son[p][u]) return ans;
        p = son[p][u];
    }
    ans += cnt[p];
    return ans;
}

int main()
{
    cin >> n >> m;
    while ( n -- )
    {
        char str[N];
        cin >> str;
        insert(str);
    }
    while ( m -- )
    {
        char str[N];
        cin >> str;
        cout << query(str) << endl;
    }
    return 0;
}