Problem
在仓库里有很多商品，你需要检索某一个商品出现的次数。
Input
第一行读入 \(P(1 \le P \le 10^4)\) 表示仓库里商品的数量，然后 \(P\) 行每行是一个字符串;
然后一行一个整数 \(Q(1 \le Q \le 10^5)\) 表示检索的次数。接下来 \(Q\) 行每行一个字符串表示一次检索。
保证所有输入的字符串长度不超过 \(20\)，仅由小写字母构成。
Output
对于每一个检索，输出有多少个商品的字符串包含查询的字符串（包含即为某一个子串）
Sample
Input 1
20
ad
ae
af
ag
ah
ai
aj
ak
al
ads
add
ade
adf
adg
adh
adi
adj
adk
adl
aes
5
b
a
d
ad
s
Output 1
0
20
11
11
2
Solution
对于这种检索字符串的题，容易想到把字符串都塞到字典树上。同时观察到每一个字符串长度很小，总状态数不会很大，这是可行的。
对于一个字符串的子串，可以将它视为一个后缀串的前缀。于是我们将每一个串的后缀串插入字典树，并且遍历每一位时都要累加，这样就插入好了每一个子串。
但直接统计答案会出问题，可能对同一个字符串统计到多次答案。所以每次累计数量的时候判一下这个子串是否在当前串中统计过了。
剩下的就是字典树常规操作了，不多言。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int kmax = 1e5 + 3;
const int kmaxM = 26;
int n, m;
string str;
int ch[kmax][kmaxM], ct = 1;
int s[kmax * kmaxM];
int l[kmax * kmaxM];
void Insert(int p, int t) { // Trie 树插入
int x = 1;
for (int i = p; i < str.size(); i++) {
int c = str[i] - 'a';
if (!ch[x][c])
ch[x][c] = ++ct;
x = ch[x][c];
s[x] += l[x] != t; // 若未在当前串出现过，则累加
l[x] = t;
}
}
int Calc() {
int x = 1;
for (int i = 0; i < str.size(); i++) {
int c = str[i] - 'a';
if (!ch[x][c])
return 0;
x = ch[x][c];
}
return s[x]; // 计算答案
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> str;
for (int p = 0; p < str.size(); p++) {
Insert(p, i);
}
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> str;
cout << Calc() << '\n';
}
return 0;
}