https://nanti.jisuanke.com/t/17122
Barty have a computer, it can do these two things.
Add a new string to its memory, the length of this string is even.
For given 44 strings a,b,c,da,b,c,d, find out how many strings that can be product by a+s1+b+c+s2+da+s1+b+c+s2+d, and |a| + |s1| + |b| = |c| + |s2| + |d|∣a∣+∣s1∣+∣b∣=∣c∣+∣s2∣+∣d∣. |s|∣s∣ means the length of string ss, s1s1 and s2s2 can be any string, including "".
Please help your computer to do these things.
Test cases begins with T(T \le 5)T(T≤5).
Then TT test cases follows.
Each test case begins with an integer Q(Q \le 30000)Q(Q≤30000).
Then QQ lines,
1 s: add a new string ss to its memory.
2 a b c d: find how many strings satisfying the requirement above.
\sum |s| + |a| + |b| + |c| + |d| \le 2000000∑∣s∣+∣a∣+∣b∣+∣c∣+∣d∣≤2000000.
For type 22 query. Output the answer in one line.
1 10 1 abcqaq 1 abcabcqaqqaq 2 ab bc qa aq 2 a c q q 1 abcabcqaqqwq 2 ab bc qa aq 2 a c q q 1 abcq 2 a c q q 2 a b c q
1 2 1 3 3 1
首先对于每一个主串，都把它对半砍，前缀加入字典树0，前缀逆序加入字典树1，后缀加入字典树2，后缀逆序加入字典树3
所以每一个节点都开一个vector存着有哪些主串能经过这个节点。内存复杂度玄学
然后每次询问，用a去字典树0找，就能知道有哪些主串能匹配a
同理b、c、d，然后求一个交集即可。
这样会有些不合法
比如就是会使得
ab bc这样，结合成abc
所以要用长度来判断是否合法，
lenstr(a) + lenstr(b)不能大于lenstr (s) / 2
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int N = 26, maxn = 2e6 + 2; struct Node { vector<int> vc; struct Node * pNext[N]; } tree[4][500000 + 2]; int t[4]; int len[maxn]; char str[maxn]; char a[maxn], b[maxn], c[maxn], d[maxn]; struct Node * create(int id) { struct Node * p = &tree[id][t[id]++]; p->vc.clear(); for (int i = 0; i < N; ++i) p->pNext[i] = NULL; return p; } void toInset(struct Node **T, char str[], int be, int en, int flag, int id, int which) { struct Node *p = *T; if (p == NULL) { p = *T = create(id); } if (flag == -1) { for (int i = en; i >= be; --i) { int tid = str[i] - ‘a‘; if (!p->pNext[tid]) p->pNext[tid] = create(id); p = p->pNext[tid]; p->vc.push_back(which); } } else { for (int i = be; i <= en; ++i) { int tid = str[i] - ‘a‘; if (!p->pNext[tid]) { p->pNext[tid] = create(id); } p = p->pNext[tid]; p->vc.push_back(which); } } } int vis[4][maxn], DFN; bool flag; void ask(struct Node *T, char str[], int be, int en, int flag, int which) { struct Node *p = T; if (p == NULL) { flag = true; return; } if (flag == -1) { for (int i = en; i >= be; --i) { int id = str[i] - ‘a‘; if (!p->pNext[id]) { flag = true; return ; } p = p->pNext[id]; } for (int i = 0; i < p->vc.size(); ++i) { vis[which][p->vc[i]] = DFN; } } else { for (int i = be; i <= en; ++i) { int id = str[i] - ‘a‘; if (!p->pNext[id]) { flag = true; return ; } p = p->pNext[id]; } // printf("fff"); // printf("%d * * ** \n", p->vc.size()); for (int i = 0; i < p->vc.size(); ++i) { vis[which][p->vc[i]] = DFN; } } } void work() { t[0] = t[1] = t[2] = t[3] = 0; struct Node *T[4]; for (int i = 0; i < 4; ++i) T[i] = NULL; int q; scanf("%d", &q); int now = 0; while (q--) { int op; scanf("%d", &op); if (op == 1) { scanf("%s", str + 1); len[++now] = strlen(str + 1); toInset(&T[0], str, 1, len[now] / 2, 1, 0, now); toInset(&T[1], str, 1, len[now] / 2, -1, 1, now); toInset(&T[2], str, len[now] / 2 + 1, len[now], 1, 2, now); toInset(&T[3], str, len[now] / 2 + 1, len[now], -1, 3, now); } else { scanf("%s%s%s%s", a + 1, b + 1, c + 1, d + 1); ++DFN, flag = false; int lena = strlen(a + 1), lenb = strlen(b + 1), lenc = strlen(c + 1), lend = strlen(d + 1); ask(T[0], a, 1, lena, 1, 0); if (flag) { printf("0\n"); continue; } ask(T[1], b, 1, lenb, -1, 1); if (flag) { printf("0\n"); continue; } ask(T[2], c, 1, lenc, 1, 2); if (flag) { printf("0\n"); continue; } ask(T[3], d, 1, lend, -1, 3); if (flag) { printf("0\n"); continue; } int ans = 0; // for (int i = 1; i <= now; ++i) { // printf("%d %d %d %d\n", vis[0][i], vis[1][i], vis[2][i], vis[3][i]); // } // printf("*************\n"); for (int i = 1; i <= now; ++i) { if (vis[0][i] == DFN && vis[1][i] == DFN && vis[2][i] == DFN && vis[3][i] == DFN && lena + lenb <= len[i] / 2 && lenc + lend <= len[i] / 2) ans++; } printf("%d\n", ans); } } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
原文：http://www.cnblogs.com/liuweimingcprogram/p/7534818.html
