大家好,欢迎来到IT知识分享网。
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;
}
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/34351.html