本文共 1011 字，大约阅读时间需要 3 分钟。

题目大意

给n个字符串。

解

Trie树。详见代码。

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int n, m, len, w, f[1000009][30], End[1000009], ans, tot;char ch;string s;int main() {       scanf("%d%d", &n, &m);    for (int i = 1; i <= n; ++i) {           cin >> s;        len = s.size();        w = 0;  //建一个0点用于出发...        for (int j = 0; j < len; ++j) {               ch = s[j] - 'a';            if (f[w][ch] == 0)  //w号点是否后面有连向的字符ch？否。                f[w][ch] = ++tot;  //新建一个点tot，w号点连点tot。（tot点代表字符ch）            w = f[w][ch];  //走向下一个点        }        ++End[w];  //标记结尾    }    for (int i = 1; i <= m; ++i) {           cin >> s;        len = s.size();        w = ans = 0;        for (int j = 0; j < len; ++j) {               ch = s[j] - 'a';            if (f[w][ch] == 0)  //如果已经没有前缀到w的点了                break; //直接退出            w = f[w][ch]; //往后走一个点            ans += End[w]; //加上以这个点为结尾的子串数        }        printf("%d\n", ans);  //输出    }}