题目概述

本题要求维护一个动态字符串，支持两种操作：

1. 在字符串末尾添加一个字符
2. 查询某个子串中最长的至少出现两次的子串长度

特殊要求：所有操作参数都受上一次查询结果影响，需要在线解密。

算法思路

核心观察

对于任意字符串，最长的至少出现两次的子串长度等于该字符串所有后缀的最长公共前缀（LCP）的最大值。

数据结构设计

本解法采用了三种高级数据结构的组合：

1. 后缀自动机 (Suffix Automaton)

• 作用：高效维护字符串的所有子串信息
• 特点：
  • 空间复杂度 O(n)
  • 支持在线添加字符
  • 每个状态代表一组结束位置相同的子串

2. 动态树 (Link-Cut Tree)

• 作用：维护后缀自动机的fail树（parent树）
• 功能：
  • 支持树的动态链接和切割
  • 在fail树上进行路径操作
  • 维护每个状态的endpos集合信息

3. 可持久化线段树

• 作用：记录历史版本信息，支持区间查询
• 应用：
  • 存储每个位置的答案信息
  • 支持对任意历史版本的查询

关键操作详解

状态设计与含义

在字符串处理中，我们维护以下关键状态：

• SAM状态：每个状态代表一组长度连续的子串，具有相同的结束位置集合
• LCT状态：维护SAM的parent树结构，支持动态操作
• 线段树状态：记录每个位置对应的最长重复子串信息

状态转移过程

字符添加操作

void extend(int ch) {
    int p = last_node, u = ++total_node;
    node[u].len = node[p].len + 1;
    
    // 状态转移：寻找第一个包含字符ch转移的状态
    for (; p && !node[p].go[ch]; p = node[p].fail)
        node[p].go[ch] = u;
    
    if (!p) {
        // 情况1：直接连接到根节点
        node[u].fail = root;
        LCT::add_leaf(u, root);
    } else {
        int q = node[p].go[ch];
        if (node[p].len + 1 == node[q].len) {
            // 情况2：直接连接到现有状态
            node[u].fail = q;
            LCT::add_leaf(u, q);
        } else {
            // 情况3：需要分裂状态
            int v = ++total_node;
            node[v] = node[q];
            node[v].len = node[p].len + 1;
            node[u].fail = node[q].fail = v;
            LCT::new_fath(q, v);
            LCT::add_leaf(u, v);
        }
    }
    last_node = u;
}

查询操作状态处理

int query(int l, int r) {
    // 状态1：查询从l到末尾的最大长度
    int x = segment_query(root[r], 1, n, l, n, 0);
    // 状态2：查询结束位置在l之前的最长子串
    int y = segment_query(root[r], 1, n, 1, l, 1);
    // 状态合并：取两种情况的较大值
    return max(x, y + 1 - l);
}

算法正确性证明

基础代价分析

• 每个字符添加操作正确维护了后缀自动机的所有性质
• LCT正确维护了parent树的动态结构
• 线段树正确记录了历史版本信息

查询正确性

对于查询区间 [l, r]：

• 情况1：最长重复子串完全在区间 [l, r] 内，通过 x 获取
• 情况2：最长重复子串跨越位置 l，通过 y + 1 - l 计算
• 取两者的最大值即为正确答案

复杂度分析

• 时间复杂度：O(n log n)
  • 每次字符添加：O(log n)
  • 每次查询：O(log n)
• 空间复杂度：O(n)

代码实现细节

初始化过程

void init() {
    root = total_node = last_node = 1;
    for (int i = 1; i <= N; i++)
        extend(str[i] - 'a');
}

主循环处理

for (int i = 1, op, l, r; i <= Q; i++) {
    scanf("%d", &op);
    if (op == 1) {
        // 添加字符，需要解密
        scanf("%s", str + ++N);
        str[N] = (str[N] - 'a' + ans * Ty) % 26 + 'a';
        SAM::extend(str[N] - 'a');
    } else {
        // 查询操作，需要解密区间
        scanf("%d%d", &l, &r);
        l = (l - 1 + ans * Ty) % N + 1;
        r = (r - 1 + ans * Ty) % N + 1;
        printf("%d\n", ans = SEG::query(l, r));
    }
}

样例解析

样例输入

aabda 6
2 1 4
1 a
2 1 5
1 b
2 6 5
2 7 4

执行过程分析

1. 初始状态：字符串 "aabda"
2. 查询1：子串 "aabd" → 最长重复子串 "a" (长度1)
3. 添加1：添加字符 'a' → 字符串变为 "aabdaa"
4. 查询2：子串 "aabda" → 最长重复子串 "aa" (长度2)
5. 添加2：添加字符 'b' → 字符串变为 "aabdaab"
6. 查询3：子串 "aab" → 最长重复子串 "aab" (长度3)
7. 查询4：子串 "da" → 最长重复子串 "a" (长度2)

总结

本题通过巧妙组合后缀自动机、动态树和可持久化线段树，实现了高效的动态字符串查询。这种解法展示了如何利用高级数据结构解决复杂的字符串处理问题，特别是在需要支持动态修改和区间查询的场景下。

算法亮点：

1. 利用SAM维护所有子串信息
2. 使用LCT支持动态树操作
3. 通过可持久化线段树记录历史版本
4. 在线解密机制增加了题目的趣味性

该解法在时间复杂度和空间复杂度上都达到了最优，能够高效处理大规模数据。