题目大意

给定 n 个模式串，m次询问，每次给出一个文本串，问这些模式串在文本串的前缀里出现了几次。

思路

对于 “前缀” 和字符串，很容易想到用 Trie 去做。与模板不同的是查询内容不一样。
首先，对 n个模式串构建 Trie树，并且记录 endpos，也就是 Trie 的当前节点是多少个模式串的结尾。
然后，由于每次查询的是前缀，就在 Trie 里面遍历文本串，累加途径的每个节点的 endpos 值即可，不能继续就退出。

（作为一道练手题是很好的选择，但是对于正式比赛而言，这样不给 n 和 m的范围还是有点不负责任的……万一 Trie 就不能用了呢）

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
char s[N];

int tr[N][26],cnt=1,endpos[N];
struct Trie
{
        void insert( char *s )
        {
                int p=1,len=strlen(s);
                for ( int i=0; i<len; i++ )
                {
                        int ch=s[i]-'a';
                        if ( tr[p][ch]==0 ) cnt++,tr[p][ch]=cnt;
                        p=tr[p][ch];
                }
                endpos[p]++;
        }
        int find( char *s )
        {
                int p=1,len=strlen(s),res=0;
                for ( int i=0; i<len; i++ )
                {
                        int ch=s[i]-'a'; p=tr[p][ch];
                        if ( p==0 ) return res;
                        res+=endpos[p];
                }
                return res;
        }
}T;

int main()
{
        scanf( "%d%d\n",&n,&m );
        while ( n-- )
                scanf( "%s\n",s ),T.insert( s );
        while ( m-- )
                scanf( "%s\n",s ),printf( "%d\n", T.find( s ) );
}