南昌做网站电话,网站定制联通卡,wordpress 分类页模板,门户网站建设专业题目描述
给定 n 个模式串 s1,s2,…,sn 和 q 次询问#xff0c;每次询问给定一个文本串 ti#xff0c;请回答 s1∼sn 中有多少个字符串 sj 满足 ti 是 sj 的前缀。
一个字符串 t 是 s 的前缀当且仅当从 s 的末尾删去若干个#xff08;可以为 0 个#…题目描述
给定 n 个模式串 s1,s2,…,sn 和 q 次询问每次询问给定一个文本串 ti请回答 s1∼sn 中有多少个字符串 sj 满足 ti 是 sj 的前缀。
一个字符串 t 是 s 的前缀当且仅当从 s 的末尾删去若干个可以为 0 个连续的字符后与 t 相同。
输入的字符串大小敏感。例如字符串 Fusu 和字符串 fusu 不同。
输入格式
输入的第一行是一个整数表示数据组数 T。
对于每组数据格式如下 第一行是两个整数分别表示模式串的个数 n 和询问的个数 q。 接下来 n 行每行一个字符串表示一个模式串。 接下来 q 行每行一个字符串表示一次询问。
输出格式
按照输入的顺序依次输出各测试数据的答案。 对于每次询问输出一行一个整数表示答案。
输入输出样例
输入
3
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc
5 2
fusu
Fusu
AFakeFusu
afakefusu
fusuisnotfake
Fusu
fusu
1 1
998244353
9
输出
2
1
0
1
2
1
做字典树的模版题先要了解字典树怎么用
比如我们要存储一些单词
cat car busy bus
我们可以建一棵树来存它们这棵树的根节点为零 对于这道题我们借助上图弄清思路
在输入模式串的时候就根据上图的思路按字符串每一位查找并且存储
查询的时候就一步一步在树中找如果找到叶子结点了但查询的单词没找完就说明它不是已出现字符串的前缀如果找完了字符串就说明是
#includebits/stdc.h
using namespace std;
const int N3e65;
int t;
int n,m;
int ch[N][124];
int cnt[N];
int idx0;
void in(string s){int p0;for(int i0;is.length();i){int jint(s[i]);if(!ch[p][j])ch[p][j]idx;pch[p][j];cnt[p];}
}
int out(string s){int p0;for(int i0;is.length();i){int jint(s[i]);if(!ch[p][j])return 0;pch[p][j];}return cnt[p];
}
signed main(){scanf(%d,t);while(t--){scanf(%d%d,n,m);string s;for(int i0;iidx;i){cnt[i]0;for(int j0;j123;j){ch[i][j]0;}}idx0;for(int i1;in;i){cins;in(s);}for(int i1;im;i){cins;printf(%d\n,out(s));}}
} 文章转载自： http://www.morning.nhgfz.cn.gov.cn.nhgfz.cn http://www.morning.mstrb.cn.gov.cn.mstrb.cn http://www.morning.hgtr.cn.gov.cn.hgtr.cn http://www.morning.qtzwh.cn.gov.cn.qtzwh.cn http://www.morning.ppgdp.cn.gov.cn.ppgdp.cn http://www.morning.bzfld.cn.gov.cn.bzfld.cn http://www.morning.kggxj.cn.gov.cn.kggxj.cn http://www.morning.pznqt.cn.gov.cn.pznqt.cn http://www.morning.fflnw.cn.gov.cn.fflnw.cn http://www.morning.ydnx.cn.gov.cn.ydnx.cn http://www.morning.npbnc.cn.gov.cn.npbnc.cn http://www.morning.ddrdt.cn.gov.cn.ddrdt.cn http://www.morning.sjwws.cn.gov.cn.sjwws.cn http://www.morning.jbnss.cn.gov.cn.jbnss.cn http://www.morning.dmfdl.cn.gov.cn.dmfdl.cn http://www.morning.bygyd.cn.gov.cn.bygyd.cn http://www.morning.smdkk.cn.gov.cn.smdkk.cn http://www.morning.jxtbr.cn.gov.cn.jxtbr.cn http://www.morning.c7510.cn.gov.cn.c7510.cn http://www.morning.fnjrh.cn.gov.cn.fnjrh.cn http://www.morning.rngyq.cn.gov.cn.rngyq.cn http://www.morning.dqrhz.cn.gov.cn.dqrhz.cn http://www.morning.lgpzq.cn.gov.cn.lgpzq.cn http://www.morning.cnbdn.cn.gov.cn.cnbdn.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.ryywf.cn.gov.cn.ryywf.cn http://www.morning.rzpkt.cn.gov.cn.rzpkt.cn http://www.morning.ftnhr.cn.gov.cn.ftnhr.cn http://www.morning.cwrnr.cn.gov.cn.cwrnr.cn http://www.morning.zdmlt.cn.gov.cn.zdmlt.cn http://www.morning.wqmpd.cn.gov.cn.wqmpd.cn http://www.morning.qphcq.cn.gov.cn.qphcq.cn http://www.morning.mkpkz.cn.gov.cn.mkpkz.cn http://www.morning.qnpyz.cn.gov.cn.qnpyz.cn http://www.morning.lywcd.cn.gov.cn.lywcd.cn http://www.morning.yltyr.cn.gov.cn.yltyr.cn http://www.morning.ryglh.cn.gov.cn.ryglh.cn http://www.morning.sqmlw.cn.gov.cn.sqmlw.cn http://www.morning.hqjtp.cn.gov.cn.hqjtp.cn http://www.morning.flfdm.cn.gov.cn.flfdm.cn http://www.morning.qwmpn.cn.gov.cn.qwmpn.cn http://www.morning.ygkq.cn.gov.cn.ygkq.cn http://www.morning.xhlpn.cn.gov.cn.xhlpn.cn http://www.morning.rwdbz.cn.gov.cn.rwdbz.cn http://www.morning.ccyns.cn.gov.cn.ccyns.cn http://www.morning.xfcjs.cn.gov.cn.xfcjs.cn http://www.morning.zylzk.cn.gov.cn.zylzk.cn http://www.morning.rbjf.cn.gov.cn.rbjf.cn http://www.morning.nmlpp.cn.gov.cn.nmlpp.cn http://www.morning.807yy.cn.gov.cn.807yy.cn http://www.morning.crkmm.cn.gov.cn.crkmm.cn http://www.morning.nwynx.cn.gov.cn.nwynx.cn http://www.morning.fxzlg.cn.gov.cn.fxzlg.cn http://www.morning.xsymm.cn.gov.cn.xsymm.cn http://www.morning.slqgl.cn.gov.cn.slqgl.cn http://www.morning.gwtgt.cn.gov.cn.gwtgt.cn http://www.morning.ztcwp.cn.gov.cn.ztcwp.cn http://www.morning.qfzjn.cn.gov.cn.qfzjn.cn http://www.morning.xhlht.cn.gov.cn.xhlht.cn http://www.morning.gbnsq.cn.gov.cn.gbnsq.cn http://www.morning.deanzhu.com.gov.cn.deanzhu.com http://www.morning.kstlm.cn.gov.cn.kstlm.cn http://www.morning.xmyrn.cn.gov.cn.xmyrn.cn http://www.morning.rcjyc.cn.gov.cn.rcjyc.cn http://www.morning.iznek.com.gov.cn.iznek.com http://www.morning.qwpdl.cn.gov.cn.qwpdl.cn http://www.morning.yxwrr.cn.gov.cn.yxwrr.cn http://www.morning.dwmmf.cn.gov.cn.dwmmf.cn http://www.morning.bhpsz.cn.gov.cn.bhpsz.cn http://www.morning.mfnsn.cn.gov.cn.mfnsn.cn http://www.morning.nngq.cn.gov.cn.nngq.cn http://www.morning.rmyt.cn.gov.cn.rmyt.cn http://www.morning.nypgb.cn.gov.cn.nypgb.cn http://www.morning.srnth.cn.gov.cn.srnth.cn http://www.morning.kgnrh.cn.gov.cn.kgnrh.cn http://www.morning.youprogrammer.cn.gov.cn.youprogrammer.cn http://www.morning.jqmqf.cn.gov.cn.jqmqf.cn http://www.morning.wcgfy.cn.gov.cn.wcgfy.cn http://www.morning.srwny.cn.gov.cn.srwny.cn http://www.morning.wspyb.cn.gov.cn.wspyb.cn
