Secret Message 秘密信息

https://loj.ac/problem/10054

题目描述

  给出N个字符串,再给出M个字符串,对于M个中每一字符串求出N个中满足是它的前缀或它是这个前缀的数目的总和。

思路

  显然,我们需要解决多个字符串前缀的问题,可以选择字典树维护。首先建出N个字符串的字典树,不过这里有两种情况,前缀和非前缀,我们要分别维护:

  ①如果这个字符串是N中某一个字符串的前缀,那么我们就需要维护两个值,一个是某一个节点的经过次数,一个是某一个节点的结束次数,所以如果是莫大意字符串的前缀我们最后加上pass[u]-ed[u],因为这个节点的pass和ed会重复。

  ②这个字符串不是N中任何一个字符串的前缀,那么只需要在无法找到时返回答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
int s[10010];
int ch[500005][3],tot;
int ed[500005],pass[500005];
void insert(int len)
{
    int u=1;
    for(int i=0;i<len;i++)
    {
        int num=s[i];
        if(!ch[u][num])ch[u][num]=++tot;
        u=ch[u][num];
        pass[u]++;
    }
    ed[u]++;
}
int find(int len)
{
    int sum=0,u=1;
    for(int i=0;i<len;i++)
    {
        int num=s[i];
        if(!ch[u][num])return sum;
        u=ch[u][num];
        sum+=ed[u];
    }
    return sum+pass[u]-ed[u];
}
int main() 
{
    int n,m;
    scanf("%d%d",&n,&m);
    tot=1;
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        for(int i=0;i<k;i++)
            scanf("%d",&s[i]);
        insert(k);
    }
    for(int i=1;i<=m;i++)
    {
        int k;
        scanf("%d",&k);
        for(int i=0;i<k;i++)
            scanf("%d",&s[i]);
        printf("%d\n",find(k));
    }
    return 0;
}

 

上一篇:PAT 天梯赛 L2-1 紧急救援


下一篇:活动安排