50分求助:
/*
work by: TLE_Automation
Time: O(TLE)
knowledge:
*/
#include<bits/stdc++.h>
#define TLE std
#define int long long
#define Min(x, y) (x > y ? y : x);
#define Max(x, y) (x > y ? x : y);
#define orz cout << "szt lps fjh AK IOI";
using namespace TLE;
const int maxn = 3e6;
const int MAXN = 3e3;
const double down = 0.996;
const double limit = 1e-10;
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while (!isdigit(ch)) {if(ch == '-') {w = -1;}ch = getchar();}
while (isdigit(ch)) {s = (s << 1) + (s << 3) + (ch ^ 48);ch = getchar();}
return s * w;
}
inline void print(int x) {
if (x < 0 ) putchar('-'), x = -x;
if (x > 9 ) print(x / 10);
putchar(x % 10 + '0');
}
const int MAX = 26;
int cnt = 0;
struct node {
int fail, vis[MAX], end;
}AC[maxn];
void build(string s) {
int now = 0;
int len = s.length();
for(int i = 0; i < len; i++) {
if(!AC[now].vis[s[i] - 'a']) {
AC[now].vis[s[i] - 'a'] = ++cnt;
}
now = AC[now].vis[s[i] - 'a'];
}
AC[now].end ++;
return;
}
void Fail() {
queue <int> q;
for(int i = 0; i < 26; i++) {
if(AC[0].vis[i]) {AC[AC[0].vis[i]].fail = 0;q.push(AC[0].vis[i]);}
}
while(!q.empty()) {
int u = q.front();q.pop();
for(int i = 0; i < 26; i++) {
if(AC[u].vis[i]) {
AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
}else {
AC[u].vis[i] = AC[AC[u].fail].vis[i];
}
}
}return;
}
int AC_query(string s) {
int len = s.length();
int now = 0, res = 0;
for(int i = 0; i < len; i++) {
now = AC[i].vis[s[i] - 'a'];
for(int j = now; j != 0 && AC[j].end != -1; j = AC[j].fail) {
res += AC[j].end;
AC[j].end = -1;
}
}return res;
}
signed main() {
// freopen("P3808_2.in", "r", stdin);
// freopen("ans.out", "w", stdout);
int n = read();
string s;
for(int i = 1; i <= n; i++) {
cin >> s;
build(s);
}
AC[0].fail = 0;
Fail();
cin >> s;
cout << AC_query(s) << endl;
return 0;
}