P5231 [JSOI2012]玄武密码（SAM 经典运用）

[JSOI2012]玄武密码

题目背景

在美丽的玄武湖畔，鸡鸣寺边，鸡笼山前，有一块富饶而秀美的土地，人们唤作进香河。相传一日，一缕紫气从天而至，只一瞬间便消失在了进香河中。老人们说，这是玄武神灵将天书藏匿在此。

很多年后，人们终于在进香河地区发现了带有玄武密码的文字。更加神奇的是，这份带有玄武密码的文字，与玄武湖南岸台城的结构有微妙的关联。于是，漫长的破译工作开始了。

题目描述

经过分析，我们可以用东南西北四个方向来描述台城城砖的摆放，不妨用一个长度为 $n$ 的序列 $s$ 来描述，序列中的元素分别是 E，S，W，N，代表了东南西北四向，我们称之为母串。而神秘的玄武密码是由四象的图案描述而成的 $m$ 段文字。这里的四象，分别是东之青龙，西之白虎，南之朱雀，北之玄武，对东南西北四向相对应。

现在，考古工作者遇到了一个难题。对于每一段文字 $t$，求出其最长的前缀 $p$，满足 $p$ 是 $s$ 的子串。

输入格式

第一行有两个整数，分别表示母串的长度 $n$ 和文字段的个数 $m$。

第二行有一个长度为 $n$ 的字符串，表示母串 $s$。

接下来 $m$ 行，每行一个字符串，表示一段带有玄武密码的文字 $t$。

输出格式

对于每段文字，输出一行一个整数，表示最长的 $p$ 的长度。

样例 #1

样例输入 #1

7 3
SNNSSNS
NNSS
NNN
WSEE

样例输出 #1

4
2
0

提示

数据规模与约定

• 对于 $20\%$ 的数据，保证 $n\le 100$，$m\le 50$。
• 对于 $40\%$ 的数据，保证 $n\le 2\times 10^4$，$m\le 2\times 10^3$。
• 对于 $70\%$ 的数据，保证 $n\le 10^6$，$m\le 2\times 10^4$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^7$，$1\le m\le 10^5$，$1\le |t|\le 100$，$s,t$ 中均只含字母 ESWN。

思路：

由于后缀自动机形成的有向无环图恰好能够保存所有不同的子串，即从源点出发，沿任意一些字符能够到达的状态节点形成的子串在原字符串中都存在，故对于有每一个匹配串，都可以直接沿着后缀自动机形成的有向无环图走一遍，当无路可走或走完所有匹配串字符时即找到最长的前缀长度

代码：

#include <bits/stdc++.h>

using namespace std;
//#define int long long
const int N = 1e7 + 10, M = N << 1;
int fa[M], ch[M][5], len[M];
int tot = 1, np = 1;
int n, m;
char s[N], ss[110];
int hah[26];

void extend(int c) {
    
    int p = np;
    np = ++tot;
    len[np] = len[p] + 1;

    while (p && !ch[p][c]) {
    
        ch[p][c] = np;
        p = fa[p];
    }
    if (!p) {
    
        fa[np] = 1;
    }
    else {
    
        int q = ch[p][c];
        if (len[q] == len[p] + 1) {
    
            fa[np] = q;
        }
        else {
    
            int nq = ++tot;
            len[nq] = len[p] + 1;
            fa[nq] = fa[q], fa[q] = fa[np] = nq;
            while (p && ch[p][c] == q) {
    
                ch[p][c] = nq;
                p = fa[p];
            }
            memcpy(ch[nq], ch[q], sizeof ch[q]);
        }
    }
}

signed main()
{
    
    hah['E' - 'A'] = 0, hah['S' - 'A'] = 1, hah['W' - 'A'] = 2, hah['N' - 'A'] = 3;
    scanf("%d%d", &n, &m);
    scanf("%s", s);
    for (int i = 0; s[i]; ++i) {
    
        extend(hah[s[i] - 'A']);
    }
    while (m--) {
    
        scanf("%s", ss);
        int nod = 1, cnt = 0;
        for (int i = 0; ss[i]; ++i) {
    
            if (!ch[nod][hah[ss[i] - 'A']]) {
    
                break;
            }
            nod = ch[nod][hah[ss[i] - 'A']];
            ++cnt;
        }
        printf("%d\n", cnt);
    }

    return 0;
}