BalticOI 2019 Day2 T2. Necklace 题解

算法思路

本题使用字符串匹配技术来寻找最长的公共子串，考虑项链可以旋转和翻转的特性。

核心思想

1. 问题转化：将项链的旋转和翻转特性转化为字符串的正向和反向匹配问题
2. KMP优化：利用KMP算法的前缀函数来高效计算最长公共子串
3. 双向处理：分别处理原字符串和反转后的字符串，覆盖所有可能的项链配置

关键观察

• 项链可以翻转 → 需要同时考虑原串和反转串
• 项链可以旋转 → 子串可以是原字符串的任意连续段（考虑首尾相连）
• 从两端移除珠子 → 子串在原字符串中的位置可以任意

算法详解

1. 字符串预处理

s = " " + s;  // 下标从1开始
s1 = " " + s1;

2. 主要求解函数 solve()

函数通过构造特殊字符串并应用KMP算法来寻找最长公共子串：

字符串构造

// 反向部分 + 分隔符 + 原串反向
ForD(j, i, 1) s2 += s1[j];
s2 += "%";
ForD(j, n, 1) s2 += s[j];

// 正向部分 + 分隔符 + 原串正向  
For(j, i + 1, m) s3 += s1[j];
s3 += "%";
For(j, 1, n) s3 += s[j];

KMP前缀函数计算

For(j, 2, p) {
    int k = pf[j - 1];
    while (true) {
        if (s2[k + 1] == s2[j]) {
            pf[j] = k + 1;
            break;
        }
        if (k == 0) break;
        k = pf[k];
    }
}

匹配位置计算

For(j, 2, n) {
    int x = pf[n - j + i + 2];  // 反向匹配长度
    int y = pf1[m - i + j];     // 正向匹配长度
    
    if (x + y > ans) {
        ans = x + y;
        y1 = i - x + 1;  // Jane的起始位置
        x1 = j - y;      // Jill的起始位置
    }
}

3. 处理边界情况

// 单字符特殊情况
if (m == 1) {
    For(j, 1, n)
        if (s[j] == s1[1])
            return {1, {j, 1}};
}

4. 处理反转情况

// 反转原字符串重新计算
reverse(all(s));
s.pop_back();
s = " " + s;
auto xxx = solve();
xxx.ss.ff = tmp - xxx.ss.ff + 1;  // 调整反转后的位置

复杂度分析

• 时间复杂度：$O(n \times m)$
  • 外层循环遍历所有可能的分割点
  • 内层使用KMP进行线性时间匹配
• 空间复杂度：$O(n + m)$
  • 存储字符串和前缀函数数组

样例解析

对于样例：

输入:
zxyabcd
yxbadctz

输出:
4
3 2

算法执行过程：

1. 发现 abcd (Jill从位置3开始) 和 badc (Jane从位置2开始) 可以匹配
2. badc 翻转后为 cdab，旋转后与 abcd 等价
3. 找到长度为4的最长公共项链

代码亮点

1. 巧妙的字符串构造：通过拼接和分隔符处理旋转匹配
2. KMP高效匹配：利用前缀函数避免重复比较
3. 全面覆盖：处理正向、反向所有可能情况
4. 边界处理：妥善处理单字符等特殊情况

总结

本题通过将项链的几何特性转化为字符串匹配问题，结合KMP算法的高效性，成功解决了在允许旋转和翻转条件下的最长公共子串查找问题。算法在$O(nm)$时间内解决了$N \leq 3000$的数据规模，满足了题目要求。