问题分析

我们需要找到一个最长的字符串序列 $S_1, S_2, \ldots, S_K$，满足：

1. $S_1$ 是 $T$ 的子串
2. 对于 $i \geq 2$，$S_i$ 是 $S_{i-1}$ 的双子串（在 $S_{i-1}$ 中至少出现两次）

关键观察

双子串的性质：如果字符串 $B$ 是 $A$ 的双子串，那么 $B$ 在 $A$ 中至少出现两次。这意味着：

• $B$ 必须是 $A$ 的某个真子串
• $B$ 在 $A$ 中的出现位置可以重叠

算法思路

1. 使用后缀自动机 (Suffix Automaton)

后缀自动机能够高效处理字符串的所有子串信息，特别适合本题：

• 构建 $T$ 的后缀自动机，每个状态对应一组 endpos 集合相同的子串
• 通过 fail 树（后缀链接树）建立状态间的层次关系

2. 维护 endpos 集合

使用可持久化线段树合并来维护每个状态的 endpos 集合：

• 每个状态对应的所有子串在 $T$ 中的结束位置集合相同
• 通过线段树合并，可以快速查询某个子串在给定区间内的出现次数

3. 动态规划求解

在 fail 树上进行 DFS，维护一个栈来记录当前路径上的状态：

• $f[u]$ 表示以状态 $u$ 对应的某个子串作为序列最后一个元素时的最大长度
• 对于每个状态 $u$，在栈中二分查找最深的满足条件的状态 $v$：
  • 状态 $v$ 对应的字符串是状态 $u$ 对应的字符串的双子串
  • 通过查询 endpos 集合来验证

核心算法步骤

步骤 1：构建后缀自动机

void extend(int ch) {
    int u = ++cntnode, p = lst;
    len[u] = len[lst] + 1;
    lst = u;
    pos[u] = ++idx;
    
    for (; !to[p][ch]; p = fail[p])
        to[p][ch] = u;
    
    if (to[p][ch] == u) {
        fail[u] = 0;
        return;
    }
    
    int v = to[p][ch];
    if (len[v] == len[p] + 1) {
        fail[u] = v;
        return;
    }
    
    int vv = ++cntnode;
    len[vv] = len[p] + 1;
    fail[vv] = fail[v], fail[v] = fail[u] = vv;
    for (int i = 0; i < 26; i++)
        to[vv][i] = to[v][i];
    for (; to[p][ch] == v; p = fail[p])
        to[p][ch] = vv;
}

步骤 2：构建 fail 树并维护 endpos

void dfs1(int u) {
    if (sam.pos[u]) {
        endpos[u] = sam.pos[u];
        root[u] = miku.newnode();
        miku.modify(root[u], 1, n, sam.pos[u], 1);
    }
    for (auto v : e[u])
        dfs1(v), root[u] = miku.merge(root[u], root[v], 1, n);
    if (!endpos[u])
        for (auto v : e[u]) {
            endpos[u] = endpos[v];
            break;
        }
}

步骤 3：在 fail 树上动态规划

void dfs2(int u, int fa) {
    stk[++top] = u;
    
    if (top == 1)
        f[u] = 0;
    else {
        f[u] = f[fa];
        int l = 1, r = top - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(stk[mid], u))  // 检查 stk[mid] 是否是 u 的双子串
                l = mid;
            else
                r = mid - 1;
        }
        f[u] = max(f[u], f[stk[l]] + 1);
    }
    
    for (auto v : e[u])
        dfs2(v, u);
    
    top--;
}

步骤 4：检查双子串条件

bool check(int u, int v) {
    if (u == 0) return true;
    // 检查状态 u 对应的字符串在状态 v 对应的字符串中是否出现至少两次
    return miku.query(root[u], 1, n, 
                     endpos[v] - sam.len[v] + sam.len[u], 
                     endpos[v] - 1) > 0;
}

复杂度分析

• 后缀自动机构建：$O(n)$
• 线段树合并：$O(n \log n)$
• 树上动态规划：$O(n \log n)$（每个状态在栈中二分）
• 总复杂度：$O(n \log n)$

算法正确性

1. 完备性：后缀自动机包含了 $T$ 的所有子串信息，不会漏解
2. 最优性：动态规划保证了找到最长的满足条件的序列
3. 双子串验证：通过 endpos 集合查询准确判断一个字符串是否是另一个字符串的双子串

代码总结

本题通过结合后缀自动机、可持久化线段树和树上动态规划，高效解决了寻找最长双子串序列的问题。算法充分利用了字符串的结构性质，将复杂的子串关系转化为树上的层次关系，实现了 $O(n \log n)$ 的优异复杂度。

该解法能够处理 $n \leq 2 \times 10^5$ 的大数据规模，适用于所有 Subtask。