AC自动机经典题。
建好AC机后我们只需求出每个点是不是母串的子串即可。
和统计是一样的道理，如果点x是母串的子串那么fail[x]也是。
然后对于每个串只需暴力网上跳到根判断即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 10000010;
const int M = 100010;
const int Sigma = 4;
namespace StandardIO{
template <typename T> void read(T &x) {
int f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
}
template <typename T> void write(T x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void print(T x) {
if (x < 0) putchar('-'), x = -x;
write(x);
putchar('
');
}
}using namespace StandardIO;
int n, m;
char s[N], t[110];
namespace ACAM{
int trie[N][4], fail[N], fa[N], in[N], tot = 1;
int End[M], Len[M];
bool mark[N];
inline int f(char c) {
switch (c) {
case 'E':
return 0;
case 'S':
return 1;
case 'W':
return 2;
case 'N':
return 3;
default:
puts("Wrong");
return -1;
}
}
inline void insert(int id) {
int T = strlen(t + 1), p = 1;
for (int i = 1; i <= T; i++) {
int k = f(t[i]);
if (!trie[p][k]) trie[p][k] = ++tot, fa[trie[p][k]] = p;
p = trie[p][k];
}
End[id] = p;
Len[id] = T;
}
inline void get_fail() {
queue<int> q;
while (!q.empty()) q.pop();
for (int i = 0; i < Sigma; i++)
trie[0][i] = 1;
fail[1] = 0;
q.push(1);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < Sigma; i++) {
if (trie[x][i])
fail[trie[x][i]] = trie[fail[x]][i], q.push(trie[x][i]);
else
trie[x][i] = trie[fail[x]][i];
}
}
}
inline void work() {
int p = 1;
for (int i = 1; i <= n; i++) {
int k = f(s[i]);
p = trie[p][k];
mark[p] = true;
}
queue<int> q;
while (!q.empty()) q.pop();
for (int i = 1; i <= tot; i++) in[fail[i]]++;
for (int i = 1; i <= tot; i++) if (in[i] == 0) q.push(i);
while (!q.empty()) {
int x = q.front();
q.pop();
mark[fail[x]] |= mark[x];
in[fail[x]]--;
if (in[fail[x]] == 0) q.push(fail[x]);
}
}
}using namespace ACAM;
int main() {
read(n); read(m);
scanf("%s", s + 1);
for (int i = 1; i <= m; ++i) {
scanf("%s", t + 1);
insert(i);
}
get_fail();
work();
for (int i = 1; i <= m; ++i) {
int p = End[i];
while (p) {
if (mark[p]) {
break;
}
Len[i]--;
p = fa[p];
}
print(Len[i]);
}
return 0;
}