﻿HDU 6096 String-Ocrosoft

# String

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 414    Accepted Submission(s): 137

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



Solution

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 1e5 + 10;
const int MAXN = maxn * 4;
const int MOD = 1000000007;
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
{
char CH; bool F = false;
for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
F && (num = -num);
return num;
}
{
T num;
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
int stk[70], tp = 0;
if (p < 0) { putchar('-'); p = -p; }
if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
while (p) stk[++tp] = p % 10, p /= 10;
while (tp) putchar(stk[tp--] + '0');
if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
print(t, '\0');
if (sizeof...(args))putchar(' ');
else putchar('\n');
print(args...);
}
#endif
#pragma endregion

vector<Vi*> M;
char pre[500001], suf[500001], cmb[500001 * 2];

struct Node
{
Node *children[26];
Vi v;
int ed;
Node(bool root = false)
{
for (int i = 0; i < 26; i++)
children[i] = nullptr;
v.clear();
ed = 0;
if (!root)M.push_back(&v);
}
void Delete()
{
for (int i = 0; i < 26; i++)
if (children[i] != nullptr)
children[i]->Delete();
v.clear();
delete this;
}
}*root = nullptr;

int main()
{
while (N--)
{
int n, m;
if (root != nullptr)root->Delete();
M.clear();
root = new Node(true);
for (int i = 0; i < n; i++)
{
scanf("%s", pre);
int len = strlen(pre);
Node *p = root;
for (int i = 0, j = len - 1; i < len; i++, j--)
{
for (int k = 0; k < 2; k++)
{
int id = pre[(!k ? i : j)] - 'a';
if (p->children[id] == nullptr)
p->children[id] = new Node();
p = p->children[id];
p->v.push_back(len);
p->ed++;
}
}
}
for (auto each : M)
sort(begin(*each), end(*each));
for (int i = 0; i < m; i++)
{
scanf("%s%s", pre, suf);
int lenPre = strlen(pre), lenSuf = strlen(suf);
for (int i = 0, j = lenSuf - 1; i < lenPre || j >= 0; i++, j--)
{
cmb[i * 2] = i < lenPre ? pre[i] : '*';
cmb[i * 2 + 1] = j >= 0 ? suf[j] : '*';
}
int len = max(lenPre, lenSuf) * 2;
//printf("::"); for (int i = 0; i < len; i++)printf("%c", cmb[i]); printf("\n");
queue<Node*> q[2];
q[0].push(root);
for (int i = 0; i < len; i++)
{
int id = cmb[i] - 'a';
while (!q[i & 1].empty())
{
Node *p = q[i & 1].front();
q[i & 1].pop();
if (cmb[i] == '*')
{
for (int j = 0; j < 26; j++)
if (p->children[j] != nullptr)
q[~i & 1].push(p->children[j]);
}
else if (p->children[id] != nullptr)
q[~i & 1].push(p->children[id]);
}
}
LL ans = 0;
while (!q[~len - 1 & 1].empty())
{
Node *p = q[~len - 1 & 1].front();
q[~len - 1 & 1].pop();
ans += p->ed;
ans -= lower_bound(begin(p->v), end(p->v), lenPre + lenSuf) - begin(p->v);
}
print(ans);
}
}
return 0;
}