/* gyt
Live up to every day */
#include < cstdio > #include < cmath > #include < iostream > #include < algorithm > #include < vector > #include < stack > #include < cstring > `#include < queue > #include < set > #include < string > #include < map > #include < time.h > #define PI acos( - 1) using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 6000005;
const ll maxm = 1e7;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f;
const ll inf = 1e15 + 5;
const db eps = 1e-9;
const int kind = 26;
struct node {
node * fail;
node * next[kind];
int coun;
void nodee() {
fail = NULL;
coun = 0;
for (int i = 0; i < kind; i++) next[i] = NULL;
}
} * root;
char str[maxn];
char tmp[maxn];
int ans = 0;
void updata() {
node * p = root;
int len = strlen(str);
for (int i = 0; i < len; i++) {
int pos = str[i] - ‘A‘;
if (p - >next[pos] == NULL) {
p - >next[pos] = new node;
p - >next[pos] - >nodee();
p = p - >next[pos];
} else p = p - >next[pos];
}
p - >coun++;
}
void getfail() {
node * p = root,
*son,
*tmp;
queue < struct node * >que;
que.push(p);
while (!que.empty()) {
tmp = que.front();
que.pop();
for (int i = 0; i < 26; i++) {
son = tmp - >next[i];
if (son != NULL) {
if (tmp == root) {
son - >fail = root;
} else {
p = tmp - >fail;
while (p) {
if (p - >next[i]) {
son - >fail = p - >next[i];
break;
}
p = p - >fail;
}
if (!p) son - >fail = root;
}
que.push(son);
}
}
}
}
void query() {
int len = strlen(str);
node * p,
*tmp;
p = root;
int cnt = 0;
for (int i = 0; i < len; i++) {
int pos = str[i] - ‘A‘;
while (!p - >next[pos] && p != root) p = p - >fail;
p = p - >next[pos];
if (!p) p = root;
tmp = p;
while (tmp != root) {
if (tmp - >coun >= 0) {
cnt += tmp - >coun;
tmp - >coun = -1;
} else break;
tmp = tmp - >fail;
}
}
ans += cnt;
}
void solve() {
ans = 0;
root = new node;
root - >nodee();
root - >fail = NULL;
int n;
scanf("%d", &n);
getchar();
for (int i = 0; i < n; i++) {
gets(str);
updata();
}
getfail();
gets(str);
int len = strlen(str);
int nn = 0;
char c;
int now = 0;
int cnt = 0;
while (1) {
if (now >= len) break;
if (str[now] == ‘ [‘) {
now++;
while (str[now] >= ‘0‘ && str[now] <= ‘9‘) {
nn = nn * 10 + (str[now] - ‘0‘);
now++;
}
c = str[now];
for (int i = 0; i < nn; i++) tmp[cnt++] = c;
nn = 0;
now++;
now++;
} else {
// if (str[now]==‘]‘) {
// now++; continue;
// }
tmp[cnt++] = str[now];
now++;
}
// cout<<str[now]<<endl;
}
tmp[cnt] = ‘\0‘;
for (int i = 0; i <= cnt; i++) str[i] = tmp[i];
// cout<<str<<endl;
query();
reverse(str, str + strlen(str));
// cout<<str<<endl;
query();
cout << ans << endl;
}
int main() {
int t = 1;
// freopen("in.txt", "r", stdin);
scanf("%d", &t);
while (t--) solve();
return 0;
}
来源: http://www.bubuko.com/infodetail-2252866.html