Datahub
数据改变生活

前缀

发表时间:2022-10-27 20:30

前缀

描述

给定n 个字符串,再询问m 次,每个询问给出一个字符串,求出这个字符串是 n 个字符串里,多少个串的前缀。

前缀:从头开始的一段连续子串。比如字符串 ab 是字符串 abcd 的前缀,也是字符串 ab

(自身)的前缀,但不是bab 的前缀。

输入

第一行包含两个正整数 n,m。

接下来 n 行,每行表示一个字符串,表示给定的n 个字符串中的一个。再接下来m 行,每行一个字符串,表示询问的字符串。

输出m 行,每行表示询问的答案。

样例 1 输入

样例 1 输

样例 1 解释

字符串 a 是 ab、abc、ab 的前缀; 字符串 b 是 ba、bb 的前缀;

字符串 ab 是 ab、abc、ab 的前缀; 字符串 abc 是abc 的前缀。

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

对于 50%的数据,n,m ≤ 500; 对于 100%的数据,n,m ≤ 5000。

字符串为 26 个小写字母组成,且单个长度不超过 500,n 个字符串的长度之和不超过

1000000。

时间:10 sec

空间:512 MB

提示

[trie 树基本题。]

代码

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

// ================= 代码实现开始 =================

const int M = 505, L = 1000005;

// c:trie树上的边,c[x][y]表示从节点x出发(x从1开始),字符为y的边(y范围是0到25)

// sz:sz[x]表示x节点的子树中终止节点的数量(子树包括x自身)

// cnt:trie树上节点的数目int c[L][26], sz[L], cnt;

// 将字符串s加入到trie树中

// s:所要插入的字符串void add(char *s) {

int x = 0;

for (; *s; ++s) {

int y = *s - 'a';

if (!c[x][y])

c[x][y] = ++cnt;

x = c[x][y];

}

++sz[x];

}

// 用于计算sz数组

// x:当前节点void dfs(int x) {

for (int y = 0; y < 26; ++y) {

int z = c[x][y];

if (z != 0) {

dfs(z);

sz[x] += sz[z];

}

}

}

// 用字符串s沿着trie树上走,找到相应的节点

// s:所给字符串

// 返回值:走到的节点int walk(char *s) {

int x = 0;

for (; *s; ++s) {

int y = *s - 'a';

if (!c[x][y])

return 0;

x = c[x][y];

}

return x;

}

// ================= 代码实现结束 =================

char s[M];

int main() {

int n, m;

scanf("%d%d", &n, &m);

for (; n--;) {

scanf("%s", s);

add(s);

}

dfs(0);

sz[0] = 0;

for (; m--;) {

scanf("%s", s);

printf("%d\n", sz[walk(s)]);

}

return 0;

}


上一篇最大间隙
下一篇子序列
文章分类: 数据结构例题
分享到:
QQ:258506508                                     联系电话:020-000000    000-000000                                   联系邮箱:xxx@.co.m                                     联系地址:XXX省XXX市XXX县XXX路