前缀

前缀

描述

给定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;

}