「JSOI2012」玄武密码

「JSOI2012」玄武密码

传送门

题目是要求多个串在母串上的最长匹配长度。

考虑 ( ext{AC}) 自动机，我们建出 ( ext{Trie}) 图然后用母串来在上面跑。

每一个能匹配的位置，它 ( ext{fail}) 的位置也一定可以匹配，我们就跳 ( ext{fail}) 把经过的节点的值赋为 (1) ，表示这个位置可以匹配。

然后我们每一个模式串，找到ta在 ( ext{Trie}) 树上最深的可以匹配的节点来计算答案即可。

参考代码：

#include <cstring>
#include <cstdio>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template < class T > inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
    s = f ? -s : s;
}

const int _ = 1e7 + 5, __ = 1e5 + 5;

char a[_], s[_][102]; int n, m;
int tot, ch[4][_], fail[_], vis[_];

inline int cg(char c) { if (c == 'E') return 0; if (c == 'S') return 1; if (c == 'W') return 2; if (c == 'N') return 3; }

inline void insert(int x) {
    int u = 0, len = strlen(s[x] + 1);
    for (rg int i = 1; i <= len; ++i) {
	    int c = cg(s[x][i]);
	    if (!ch[c][u]) ch[c][u] = ++tot;
	    u = ch[c][u];
    }
}

inline void build() {
    static int hd, tl, Q[_];
    hd = tl = 0;
    for (rg int c = 0; c < 4; ++c) if (ch[c][0]) Q[++tl] = ch[c][0];
    while (hd < tl) {
	    int u = Q[++hd];
	    for (rg int c = 0; c < 4; ++c) {
    	    if (!ch[c][u]) ch[c][u] = ch[c][fail[u]];
	        else fail[ch[c][u]] = ch[c][fail[u]], Q[++tl] = ch[c][u];
	    }
    }
}

inline void query() {
    int u = 0, len = strlen(a + 1);
    for (rg int i = 1; i <= len; ++i) {
	    u = ch[cg(a[i])][u];
	    for (rg int v = u; v; v = fail[v]) if (!vis[v]) vis[v] = 1; else break ;
    }
}

inline int calc(int x) {
    int u = 0, len = strlen(s[x] + 1), res = 0;
    for (rg int i = 1; i <= len; ++i) {
	    u = ch[cg(s[x][i])][u]; if (vis[u]) res = i;
    }
    return res;
}

int main() {
#ifndef ONLINE_JUDGE
    file("cpp");
#endif
    read(n), read(m), scanf("%s", a + 1);
    for (rg int i = 1; i <= m; ++i) scanf("%s", s[i] + 1), insert(i);
    build();
    query();
    for (rg int i = 1; i <= m; ++i) printf("%d
", calc(i));
    return 0;
}