AcWing 1283. 玄武密码 题解

题目分析

本题讲述了与玄武密码相关的背景故事，实际问题是给定一个长度为(N)的母串（由E、S、W、N表示东南西北方向）和(M)段文字，需要求出每段文字的前缀在母串上的最大匹配长度。

解题思路

本题通过构建后缀自动机（SAM）来解决匹配问题。先根据母串构建后缀自动机，然后对于每段文字，在后缀自动机上进行匹配，从而得到最大匹配长度。
1. 构建后缀自动机：利用extend函数根据母串逐个字符扩展后缀自动机。
2. 字符映射：通过get函数将字符E、S、W、N映射为(0)、(1)、(2)、(3)，方便在后缀自动机中进行状态转移。
3. 匹配过程：对于每段文字，从后缀自动机的初始状态开始，根据文字中的字符进行状态转移，能成功转移则匹配长度加(1)，直到无法转移为止，此时得到的匹配长度即为该段文字前缀与母串的最大匹配长度。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 10000010;

int n, m;
int tot = 1, last = 1;
char str[N];
struct Node
{
    int len, fa;
    int ch[4];
}node[N * 2];

• 引入必要的头文件，包括输入输出、字符串操作和算法相关的头文件。
• 定义常量(N)表示母串的最大长度。
• 变量(n)表示母串的长度，(m)表示文字段的个数。
• tot表示后缀自动机状态的总数，初始为(1)；last表示上一个添加的状态，初始为(1)。
• str[N]用于存储母串和每段文字。

• 定义结构体Node，每个节点包含子串长度len、父节点编号fa以及字符转移数组ch[4]，用于表示从该状态通过E、S、W、N四个字符转移到的下一个状态。

• 字符映射函数

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

• 该函数用于将字符E、S、W、N映射为整数(0)、(1)、(2)、(3)，方便在后缀自动机中进行状态转移操作。

• 扩展后缀自动机函数

void extend(int 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;
        }
    }
}

• 该函数用于向后缀自动机中添加一个字符c（这里c是映射后的整数值）。
• 首先创建一个新状态np，其长度为上一个状态p的长度加(1)。
• 然后从last状态开始，沿着父指针向上遍历，若当前状态没有字符c的转移边，则添加一条指向新状态np的转移边。
• 如果遍历到了根状态（p == 0），则将新状态np的父节点设为根状态（编号为(1)）。

• 否则，找到通过字符c转移到的状态q。若q的长度等于p的长度加(1)，则将np的父节点设为q；否则，创建一个新状态nq，复制q的信息并调整其长度，将q和np的父节点都设为nq，并更新之前指向q的转移边，使其指向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;
        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;
}

• 读入母串长度n和文字段个数m，然后读入母串str。
• 根据母串构建后缀自动机，逐个字符调用extend函数进行扩展。
• 对于每段文字：
  • 读入文字str。
  • 初始化匹配的起始状态为根状态（编号为(1)），匹配长度res为(0)。
  • 遍历文字中的每个字符，将字符映射后检查当前状态p是否有对应的转移边。若有，则沿着转移边移动到下一个状态，并将匹配长度加(1)；若没有，则停止匹配。
  • 输出该段文字前缀与母串的最大匹配长度res。

时间复杂度分析

• 构建后缀自动机的过程中，每个字符的扩展操作时间复杂度为(O(1))，母串长度为(n)，所以构建后缀自动机的时间复杂度为(O(n))。
• 对于每段文字的匹配过程，每段文字长度不超过(100)，共有(m)段文字，所以匹配过程的时间复杂度为(O(100m))，总体时间复杂度为(O(n + 100m))。

空间复杂度分析

主要空间消耗在于存储后缀自动机的状态数组，空间复杂度为(O(n)) 。