【深基6.例6】文字处理软件

解题思路

用 string 的追加、substr、insert、find 对应四类操作。修改操作输出新文档，查询操作输出首位置或 -1。

正确性说明

标准字符串操作分别实现题意定义的追加、保留区间、位置前插入和首次匹配查找；顺序执行使每次都基于最新文档。

易错点

下标从 0 开始；substr 第二参数是长度而非终点；npos 不能直接当普通下标输出。

复杂度

设最大文档长 L、操作串长 P，单次查找最坏 O(LP)，修改 O(L+P)，空间 O(L+P)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    string s;
    cin >> q >> s;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            string t;
            cin >> t;
            s += t;
            cout << s << "\n";
        } else if (op == 2) {
            int a, b;
            cin >> a >> b;
            s = s.substr(a, b);
            cout << s << "\n";
        } else if (op == 3) {
            int a;
            string t;
            cin >> a >> t;
            s.insert(a, t);
            cout << s << "\n";
        } else {
            string t;
            cin >> t;
            size_t p = s.find(t);
            if (p == string::npos)
                cout << -1 << "\n";
            else
                cout << p << "\n";
        }
    }
    return 0;
}