洛谷题单指南-字符串-P2922 [USACO08DEC] Secret Message G

原题链接：https://www.luogu.com.cn/problem/P2922

题意解读：已知M个01串，给出N个01串，对于N个串的每一个，求在M个串中有多少与其有公共前缀，且前缀长度是两个串中较小者。

解题思路：

用Trie树存储M个01串，用cnt1[]记录某个节点结束的01串个数，cnt2[]记录经过某个节点的01串的数量

对于N个01串，在Trie树中查找，累加路径上01串的个数cnt1[u]，这覆盖了M个串是前缀的情况

对于N个串中有前缀的情况，要在查找结束时，判断待查找串是否到末尾，如果到达末尾匹配的前缀数量要加上cnt2[u] - cnt1[u]，避免重复计算。

100分代码：

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

const int MAXN = 500005;
int m, n;
int trie[MAXN][2], idx, cnt1[MAXN], cnt2[MAXN];
int len, s[100005];

void add(int len, int s[100005])
{
    int u = 0;
    for(int i = 1; i <= len; i++)
    {
        if(!trie[u][s[i]]) trie[u][s[i]] = ++idx;
        u = trie[u][s[i]]; 
        cnt2[u]++; //记录经过u的01串个数
    }
    cnt1[u]++; //记录以节点u结束的01串个数
}

int find(int len, int s[100005])
{
    int u = 0, res = 0;
    for(int i = 1; i <= len; i++)
    {
        if(!trie[u][s[i]]) return res;
        u = trie[u][s[i]];
        res += cnt1[u]; //trie中找到一个完整01串，累加数量
    }
    if(u) res += cnt2[u] - cnt1[u]; //要查找的01串到末尾了，应该加上trie中经过u的所有01串数量，同时减去以u结束的01串数量，因为前面已经加过了
    return res;
}

int main()
{
    cin >> m >> n;
    while(m--)
    {
        cin >> len;
        for(int i = 1; i <= len; i++) cin >> s[i];
        add(len, s);
    }
    while(n--)
    {
        cin >> len;
        for(int i = 1; i <= len; i++) cin >> s[i];
        cout << find(len, s) << endl;;
    }
}