题目描述

实现一个简单的文本编辑器，支持剪切和粘贴操作。

给定一个初始字符串 $S$ 和 $N$ 次操作。每次操作包含两步：

1. 剪切 (Cut):

   • 给定剪切的起始位置 l 和结束位置 r (位置从 1 开始编号)。
   • 将当前字符串中从位置 l 到 r 的子串（包含两端）复制到剪贴板中。
   • 从当前字符串中删除这个子串。
   • 例如：字符串 abcdefg，l=3, r=5。剪切后，剪贴板内容为 cde，字符串变为 abfg。

2. 粘贴 (Paste):

   • 给定用于定位插入位置的前缀字符串 pre 和后缀字符串 suf。
   • 在当前字符串中查找第一个出现 pre 后面紧跟着 suf 的位置。插入点就在 pre 和 suf 之间。
   • 将剪贴板的内容插入到找到的位置。
   • 清空剪贴板。
   • 查找规则:
     • 区分大小写。
     • 如果存在多个匹配 pre...suf 的位置，选择最靠前（下标最小）的那一个。
     • 如果找不到任何匹配 pre...suf 的位置，则将插入位置设置为当前字符串的末尾。
   • 例如：字符串 abfg，剪贴板 cde，pre="bf", suf="g"。找到 bf 和 g 之间的位置（即 g 的前面），插入 cde，字符串变为 abfcdeg。

完成所有 $N$ 次操作后，输出最终得到的字符串。

约束

• 初始字符串 $S$ 长度 $\le 200$。
• $1 \le N \le 100$。
• 剪切位置 l, r 保证合法 ($1 \le l \le r \le \text{当前字符串长度}$)。
• pre, suf 长度 $\le 5$，非空，不含空格。
• 字符串只包含可见 ASCII 字符，不含回车、空格。

样例

输入:
AcrosstheGreatWall,wecanreacheverycornerintheworld
5
10 18 ery cor
32 40 , we
1 6 tW all
14 18 rnerr eache
1 1 e r

输出:
he,allcornetrrwecaneacheveryGreatWintheworldAcross

算法 (模拟)

$O(N \times |S| \times L_{max})$ 其中 $|S|$ 是字符串长度, $L_{max}$ 是pre/suf最大长度 (近似 $O(N \times |S|)$)

思路分析

这个问题要求我们精确地模拟文本编辑器的剪切和粘贴操作。我们需要维护当前字符串的状态以及剪贴板的内容，并按照给定的顺序执行 N 次操作。

1. 维护状态:

   • 使用一个 std::string s 来存储当前编辑器中的文本内容。
   • 使用另一个 std::string clipboard 来存储剪贴板的内容。

2. 循环处理操作:

   • 循环 $N$ 次，每次处理一个剪切粘贴操作。
   • 在每次循环开始时，读取该次操作的参数：剪切起始位置 l、结束位置 r、插入前缀 pre、插入后缀 suf。

3. 坐标转换:

   • 题目给定的位置 l 和 r 是从 1 开始的。C++ 的 std::string 操作通常使用从 0 开始的下标。因此，在进行字符串操作前，需要将 l 和 r 减 1，转换为 0-based 索引。l--；r--；。

4. 执行剪切:

   • 提取子串: 使用 s.substr(l, length) 提取要剪切的子串。注意，第二个参数是子串的长度，而不是结束下标。长度为 r - l + 1。将提取的子串存入 clipboard。
     clipboard = s.substr(l, r - l + 1);
   • 删除子串: 使用 s.erase(l, length) 从原字符串 s 中删除对应的子串。
     s.erase(l, r - l + 1);

5. 执行粘贴:

   • 查找插入位置:
     a. 初始化插入位置 pos = -1（表示未找到）。
     b. 遍历当前字符串 s 的所有可能的起始下标 j，检查从 j 开始的子串是否匹配 pre。循环的上界需要注意，确保 pre 不会越界，即 j <= s.size() - pre.size()。
     c. 如果找到一个匹配 pre 的位置 j (s.substr(j, pre.size()) == pre)，计算 pre 后面紧接着的位置 k = j + pre.size()。
     d. 检查从位置 k 开始的子串是否匹配 suf。同样需要检查边界 k + suf.size() <= s.size()。
     e. 如果 suf 也匹配 (s.substr(k, suf.size()) == suf)，那么我们找到了一个合法的插入位置。根据题意，插入点在 pre 和 suf 之间，即位置 k。将 pos 设为 k，并 break 循环，因为我们只需要找到第一个（最靠前）的匹配位置。
   • 处理未找到的情况: 如果循环结束后 pos 仍然是 -1，说明没有找到匹配 pre...suf 的位置。按照规则，此时应将插入位置设为字符串末尾：pos = s.size();。
   • 插入: 使用 s.insert(pos, clipboard) 将剪贴板的内容插入到计算出的位置 pos。
   • 清空剪贴板: 粘贴操作完成后，需要清空剪贴板：clipboard.clear();。

6. 输出结果:

   • 完成所有 $N$ 次操作后，输出最终的字符串 s。

代码细节

• 使用了 C++ 的 std::string 类及其成员函数 substr, erase, insert, clear, size。
• 注意 substr 和 erase 的第二个参数是长度。
• 在查找 pre 和 suf 的循环和判断中，使用了 (int) 类型转换来比较 size() 返回的 size_t (无符号类型) 和 int 类型的索引 j，避免潜在的警告或无符号整数下溢问题，尤其是在检查 j <= s.size() - pre.size() 时。
• 使用了 long long (别名 i64)，虽然在本题中不是必需的，但这是一个好的编程习惯。

时间复杂度

• 循环 $N$ 次。
• 剪切: substr 和 erase 操作的复杂度与字符串长度 $|S|$ 和剪切长度有关，最坏情况下可认为是 $O(|S|)$。
• 粘贴 (查找位置): 循环最多 $|S|$ 次。内部的 substr 和字符串比较操作与 pre 和 suf 的长度（设为 $L_{max} \le 5$）有关。此步骤复杂度约为 $O(|S| \times L_{max})$。
• 粘贴 (插入): insert 操作的复杂度与字符串长度 $|S|$ 和剪贴板内容长度有关，最坏情况下可认为是 $O(|S|)$。
• 由于 $L_{max}$ 很小，可以近似认为每次操作的复杂度是 $O(|S|)$。
• 字符串 $S$ 的长度会变化，但其最大长度通常不会急剧增长（除非剪切板内容远大于删除内容且频繁插入）。考虑到初始长度和操作次数，可以认为 $|S|$ 不会变得过大。
• 总时间复杂度约为 $O(N \times |S|)$。对于给定的数据范围 ($N=100$, 初始 $|S|=200$)，这是完全可行的。

空间复杂度

• 存储字符串 s 和 clipboard 需要空间。复杂度为 $O(|S|)$，其中 $|S|$ 是操作过程中字符串的最大长度。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库
using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (本题未使用)

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    string s; // 当前编辑器中的字符串
    cin >> s; // 读入初始字符串

    int n; // 操作次数
    cin >> n;

    string clipboard; // 剪贴板内容
    // 循环执行 n 次操作
    for (int i = 0; i < n; i++) {
        int l, r;          // 剪切的起始和结束位置 (1-based)
        string pre, suf; // 粘贴定位用的前缀和后缀
        cin >> l >> r >> pre >> suf; // 读入操作参数
        l--; r--; // 将位置转换为 0-based 索引

        // --- 剪切操作 ---
        // 提取从 l 开始，长度为 r - l + 1 的子串到剪贴板
        clipboard = s.substr(l, r - l + 1);
        // 从字符串 s 中删除该子串
        s.erase(l, r - l + 1);

        // --- 粘贴操作 ---
        int pos = -1; // 初始化插入位置为 -1 (表示未找到)
        // 遍历字符串 s，查找第一个 pre...suf 模式
        // 注意循环条件 j <= (int)s.size() - (int)pre.size() 避免越界
        for (int j = 0; j <= (int)s.size() - (int)pre.size(); j++) {
            // 检查从 j 开始的子串是否匹配 pre
            if (s.substr(j, pre.size()) == pre) {
                // 如果 pre 匹配，计算 suf 应该开始的位置 k
                int k = j + pre.size();
                // 检查 k 之后是否有足够空间容纳 suf，并且是否匹配 suf
                if (k + suf.size() <= s.size() && s.substr(k, suf.size()) == suf) {
                    pos = k; // 找到匹配，记录插入位置 k (pre之后，suf之前)
                    break;   // 找到第一个匹配就停止查找
                }
            }
        }
        // 如果没有找到匹配的 pre...suf
        if (pos == -1) {
            pos = s.size(); // 将插入位置设置为字符串末尾
        }
        // 在位置 pos 处插入剪贴板的内容
        s.insert(pos, clipboard);
        // 清空剪贴板
        clipboard.clear(); 
    }

    // 输出 N 次操作后最终的字符串
    cout << s << "\n";
    return 0; // 程序正常结束
}