HDU 6096 String

Problem Description

Bob has a dictionary with N words in it.
Now there is a list of words in which the middle part of the word has continuous letters disappeared. The middle part does not include the first and last character.
We only know the prefix and suffix of each word, and the number of characters missing is uncertain, it could be 0. But the prefix and suffix of each word can not overlap.
For each word in the list, Bob wants to determine which word is in the dictionary by prefix and suffix.
There are probably many answers. You just have to figure out how many words may be the answer.

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each test case contains two integer N and Q, The number of words in the dictionary, and the number of words in the list.
Next N line, each line has a string Wi, represents the ith word in the dictionary (0<|Wi|≤100000)
Next Q line, each line has two string Pi , Si, represents the prefix and suffix of the ith word in the list (0<|Pi|,|Si|≤100000,0<|Pi|+|Si|≤100000)
All of the above characters are lowercase letters.
The dictionary does not contain the same words.

Limits
T≤5
0< N,Q≤100000
∑Si+Pi≤500000
∑Wi≤500000

Output

For each test case, output Q lines, an integer per line, represents the answer to each word in the list.

Sample Input

1
4 4
aba
cde
acdefa
cdef
a a
cd ef
ac a
ce f

Sample Output

2
1
1
0

题目大意：

输入一个数T表示接下来有T组测试数据，输入n，q分别表示文本和要查询的次数，n表示接下来输入n个字符串，q表示有q次查询，每次查询为以输入两个的字符串为开头和结尾的个数。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
//typedef pair<int,int> P;
const int MAXN = 2000010;
int pos[MAXN];
struct Trie{
    int next[MAXN][27], fail[MAXN], LEN[MAXN], ans[MAXN];
    int root, L;
    int insert(char buf[])
    {
        int len = strlen(buf), now = 0;
        for(int i = 0; i < len; i++)
        {
            if(next[now][buf[i] - 'a'] == 0)
            {
                next[now][buf[i] - 'a'] = ++L;
                LEN[L] = i + 1;
            }
            now = next[now][buf[i] - 'a'];
        }
        return now;
    }
    void init()//不要忘记初始化
    {
        memset(next, 0, sizeof(int) * (L + 1) * 27);
        memset(fail, 0, sizeof(int) * (L + 1));
        memset(LEN, 0, sizeof(int) * (L + 1));
        memset(ans, 0, sizeof(int) * (L + 1));
        root = L = 0;
    }
    void build()
    {
        queue<int>q;
        fail[root] = root;
        for(int i = 0; i < 27; i++)
        if(next[root][i] == 0)
        next[root][i] = root;
        else
        {
            fail[next[root][i]] = root;
            q.push(next[root][i]);
        }
        while(!q.empty())
        {
            int now = q.front(); q.pop();
            for(int i = 0; i < 27; i++)
            if(next[now][i] == 0)
            next[now][i] = next[fail[now]][i];
            else
            {
                fail[next[now][i]] = next[fail[now]][i];
                q.push(next[now][i]);
            }
        }
    }
    void query(char buf[], int len)
    {
       int now = root;
        for(int i = 0; buf[i]; i++)
        {
            now = next[now][buf[i] - 'a'];
            int tmp = now;
            while(tmp != root)
            {
                if(LEN[tmp] <=  len) ans[tmp]++;
                tmp = fail[tmp];
            }
        }
    }
}AC;
char str[MAXN];
char *s[100010];
int len[100010];
char s1[100010], s2[100010];
int main()
{
    int T, n, q;
    scanf("%d", &T);
    while(T--)
    {
        AC.init();
        scanf("%d %d", &n, &q);
        int cnt = 0;
        for(int i = 0; i < n; i++)
        {
            s[i] = str + cnt;
            scanf("%s", s[i]);
            len[i] = strlen(s[i]) + 1;
            cnt += len[i];
            strcpy(str + cnt, s[i]);
            str[cnt - 1] = 'z' + 1;
            cnt += len[i];
        }
        for(int i = 0; i < q; i++)
        {
            s1[0] = 'z' + 1;
            scanf("%s %s", s1 + 1, s2);
            strcat(s2, s1);
            pos[i] = AC.insert(s2);
        }
        AC.build();
        for(int i = 0; i < n; i++)
        AC.query(s[i], len[i]);
        for(int i = 0; i < q; i++)
        printf("%d\n", AC.ans[pos[i]]);
    }
    return 0;
}