#include<cstdio> #include<cstring> usingnamespace std; typedeflonglong LL; constint N = 1e7 + 10; structNode { int len, fa; int nxt[4]; } tr[N << 1]; char str[N]; int n, m, last = 1, cnt = 1; intinsert(int c) { int p = last, np = ++cnt; tr[np].len = tr[p].len + 1; for (; p && !tr[p].nxt[c]; p = tr[p].fa) tr[p].nxt[c] = np; last = cnt; if (!p) { tr[np].fa = 1; return np; } int q = tr[p].nxt[c]; if (tr[q].len == tr[p].len + 1) { tr[np].fa = q; return np; } int nq = ++cnt; tr[nq] = tr[q], tr[nq].len = tr[p].len + 1; tr[q].fa = tr[np].fa = nq; for (; p && tr[p].nxt[c] == q; p = tr[p].fa) tr[p].nxt[c] = nq; return np; } intnum(char c) { if (c == 'E') return0; if (c == 'S') return1; if (c == 'W') return2; return3; } intmain() { scanf("%d%d%s", &n, &m, str + 1); for (int i = 1; i <= n; i++) insert(num(str[i])); for (int p = 1; m; m--, p = 1) { scanf("%s", str + 1); n = strlen(str + 1); for (int i = 0; i <= n; i++) { int t = tr[p].nxt[num(str[i + 1])]; if (i == n || !t) { printf("%d\n", i); break; } p = t; } } return0; }