#5455. 「ROI 2012 Day 1」密码 题解

问题分析

我们有两个数字字符串：

• 第一个字符串 $s$（长度最多 $100,000$）
• 第二个字符串 $t$

第二个字符串是通过将第一个字符串中的某个连续数字段替换为这些数字的和得到的。

我们需要找到被替换段的起始和结束位置。

关键观察

1. 替换规则：被替换的连续数字段的和等于替换后的数字
2. 字符串变化：替换后字符串长度可能变短（数字和位数少于原数字段）
3. 位置关系：替换段前后的字符保持不变

算法思路

双指针/滑动窗口法

我们可以遍历所有可能的连续数字段，检查：

• 该数字段的和是否等于 $t$ 中对应的数字
• 替换后整个字符串是否与 $t$ 匹配

具体步骤：

1. 预处理：计算 $s$ 的数字前缀和数组，用于快速计算任意区间的数字和
2. 寻找匹配位置：
   • 在 $s$ 中寻找与 $t$ 开头匹配的前缀
   • 在 $s$ 中寻找与 $t$ 结尾匹配的后缀
3. 验证候选段：对于可能的替换段，验证数字和是否等于 $t$ 中对应部分

更简单的方法

由于数据规模较大，我们需要线性或接近线性的算法：

1. 从左到右扫描 $s$ 和 $t$，找到第一个不同的位置 $l$
2. 从右到左扫描 $s$ 和 $t$，找到第一个不同的位置 $r$
3. 被替换段就是 $s[l:r]$（Python 切片表示法）
4. 验证 $s[l:r]$ 的数字和是否等于 $t$ 中对应的部分

算法实现

步骤详解

1. 找到差异边界：

   • 设 $i$ 从 $0$ 开始，比较 $s[i]$ 和 $t[i]$，找到第一个不同的位置 $l$
   • 设 $j$ 从末尾开始，比较 $s[len(s)-1-j]$ 和 $t[len(t)-1-j]$，找到第一个不同的位置 $r$

2. 确定替换段：

   • 替换段在 $s$ 中的位置是 $[l, len(s)-1-r]$
   • 在 $t$ 中对应的数字是 $t[l:len(t)-r]$

3. 验证：计算 $s[l:len(s)-r]$ 的数字和，应该等于 $t[l:len(t)-r]$ 的数值

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度
• 空间复杂度：$O(n)$，存储字符串

代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    
    int n = s.length(), m = t.length();
    
    // 找到左边第一个不同的位置
    int l = 0;
    while (l < n && l < m && s[l] == t[l]) {
        l++;
    }
    
    // 找到右边第一个不同的位置
    int r = 0;
    while (r < n && r < m && s[n-1-r] == t[m-1-r]) {
        r++;
    }
    
    // 计算替换段的数字和
    long long segment_sum = 0;
    for (int i = l; i < n - r; i++) {
        segment_sum += s[i] - '0';
    }
    
    // 提取t中对应的数字
    long long replacement_num = 0;
    for (int i = l; i < m - r; i++) {
        replacement_num = replacement_num * 10 + (t[i] - '0');
    }
    
    // 输出结果（位置从1开始计数）
    cout << l + 1 << " " << n - r << endl;
    
    return 0;
}