用了AC自动机，其实是把KMP和trie结合，每次找单词失配时，用像next数组一样的东西可以进行优化，这个不难理解，若只有一个单词，把它构成字典树，这时AC自动机就是KMP，不过感觉这个题目可以有更好的方法吧，我觉得。因为打完代码提交后，用cin，cout就超时了，改成scanf，printf就刚刚过的样子。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;char str[1000010];const int maxn = 500010;struct ACA{    int ch[maxn][26],fail[maxn],val[maxn],last[maxn],sz,root;    int newnode(){        memset(ch[sz],0,sizeof(ch[sz]));        val[sz] = 0;        return sz++;    }    void init(){        sz = 0;        root = newnode();    }void insert(char *str){    int length = strlen(str);    int now = root;    for(int i = 0;i < length;i++){        int &temp = ch[now][str[i] - 'a'];        if(!temp){            temp = newnode();        }        now = temp;    }    val[now]++;}void getfail(){    queue
         
           p;    fail[root] = root;    for(int i = 0;i < 26;i++){        int u = ch[root][i];        if(u){            fail[u] = last[u] = 0;            p.push(u);        }    }    while(!p.empty()){        int now = p.front();p.pop();        for(int i = 0;i < 26;i++){            int u = ch[now][i];            if(!u){                ch[now][i] = ch[fail[now]][i];            }            else{                fail[u] = ch[fail[now]][i];                last[u] = val[fail[u]] ? fail[u]:last[fail[u]];                p.push(u);            }        }    }}int query(char *str){    int len = strlen(str);    int now = root;    int ret = 0;    for(int i = 0;i < len;i++){        now = ch[now][str[i]-'a'];        int tmp = now;        while(tmp != root && val[tmp]){            ret += val[tmp];            val[tmp] = 0;           tmp = last[tmp];        }    }    return ret;}}ac;int main(){    int kase,n;    scanf("%d",&kase);    while(kase--){        ac.init();        scanf("%d",&n);        for(int i = 0;i < n;i++){            scanf("%s",str);            ac.insert(str);        }        ac.getfail();        scanf("%s",str);        printf("%d\n",ac.query(str));    }    return 0;}