玄武密码问题

解题思路

本题给了一个长度为 $n$ 的主串，然后给了若干个小串，对于每个小串，我们要求出他的最长的一个在主串中出现过的前缀的长度。

其实就是判断主串中是否存在某个子串是小串的前缀，因此可以用后缀自动机来维护主串的所有子串，后缀自动机从起点沿着普通边走就能得到所有的子串，本质上是一个存了所有子串的 $Trie$ 字典树，因此对于每个小串，从起点开始沿着小串的每个字符往下走，走到不能走为止，就是该小串在主串中出现过的最长前缀。

可以发现本题是后缀自动机的非常简单的应用。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10000010;

int n, m;
char str[N];
struct Node
{
    int len, fa; //当前状态中最长子串长度、Link 边指向的状态
    int ch[4]; //ch[i] 指向后面加上字符 i 变成的新状态
}node[N * 2]; //存储后缀自动机中的所有状态
int tot = 1, last = 1;

inline int get(char c) //给字符进行离散化
{
    if(c == 'E') return 0;
    if(c == 'S') return 1;
    if(c == 'W') return 2;
    return 3;
}

void extend(int c) //将字符 c 加入后缀自动机
{
    int p = last, np = last = ++tot;
    node[np].len = node[p].len + 1;
    for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if(!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if(node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", str);
    for(int i = 0; str[i]; i++) extend(get(str[i])); //将主串的每个字符依次加入后缀自动机

    while(m--)
    {
        scanf("%s", str);
        int p = 1, res = 0; //p 表示当前所在位置，res 表示最长前缀的长度
        for(int i = 0; str[i]; i++)
        {
            int c = get(str[i]);
            if(node[p].ch[c]) p = node[p].ch[c], res++; //如果能继续往下走，就继续走
            else break; //否则停止
        }
        printf("%d\n", res);
    }
    return 0;
}