题目内容

塔子哥玩腻了记事本，打算自己写一个文本编辑器。该编辑器有以下功能：

插入：insert str。表示将字符串 $str$ 插入到当前游标所处位置，同时游标移动到 $str$ 的右边。
删除：delete len。表示将游标左边长度为 $len$ 的字符串删除。要求该功能命令合法，即 $len\ge 0$ ，如果 $len\lt0$ 或者 $len$ 大于字符串长度，则认为输入非法，不进行操作。
移动：move cnt。将游标移动 $cnt$ 次，如果为负数，向左移动，为正数，向右移动。如果 $cnt$ 超过字符串左右边界，那么认为非法，不进行移动。
复制：copy。将游标左边字符串复制并插入到游标的右边。游标位置不变。

现在塔子哥已经写好了该文本编辑器，而你正在使用它，那么输入一系列命令后，会得到什么结果呢？

输入描述

每行仅输入一个功能对应的操作。如果为 $end$ ，代表操作结束。

初始时，字符串为空。游标位置为 $0$ 。

$1 \le str.length \le 40$

$1 \le len \le 40$

$-40 \le cnt \le 40$

调用insert，delete，move和copy的总次数不超过200次。

输出描述

最终的文本结果，注意，结果应当包含游标，用"|"表示。

样例

输入

insert test
insert pass
move 10
delete 4
insert fail
move -4
copy
end

输出

test|testfail

题面描述

塔子哥开发了一个文本编辑器，支持插入、删除、移动游标和复制文本等基本功能。用户通过输入相应的命令来操作文本，直到输入“end”表示结束。每个命令影响游标位置和文本内容，最终输出的结果中需要用“|”标识游标的位置。例如，输入一系列操作后，若文本为“testtestfail”，游标在“test”和“testfail”之间，则输出为“test|testfail”。

思路：模拟

定义两个双端队列分别表示游标左边和右边的文本。

插入：我们将字符串中的每个字符添加到左边的双端队列的末尾。
删除：我们从左边的双端队列的末尾删除指定数量的字符。
移动：我们将指定数量的字符从一个双端队列的末尾移动到另一个双端队列的开头。如果移动的数量为负数，我们从左边的双端队列移动字符到右边的双端队列；如果移动的数量为正数，我们从右边的双端队列移动字符到左边的双端队列。
复制：我们将左边的双端队列的所有字符复制到右边的双端队列的开头。

最后，我们将左边的双端队列和右边的双端队列中的所有字符连接起来，然后输出。

题解

塔子哥开发了一个文本编辑器，使用两个双端队列来分别表示游标左侧和右侧的文本内容。这种结构使得插入、删除、移动游标和复制文本等操作都可以高效进行。具体操作如下：

插入操作（insert）：将输入字符串的每个字符添加到游标左侧的双端队列末尾。这意味着新插入的文本位于游标的左侧。
删除操作（delete）：从游标左侧的双端队列末尾删除指定数量的字符。若请求删除的字符数量超过当前可删除的字符数，则只删除可删除的字符。
移动操作（move）：根据指定的数量，将字符从一个双端队列的末尾移动到另一个双端队列的开头。如果移动的数量为负数，则从游标左侧的双端队列移动字符到右侧；如果为正数，则相反。此操作需要检查是否会超出队列的边界。
复制操作（copy）：将游标左侧的所有字符复制到游标右侧的双端队列的开头。
输出结果（print）：将游标左侧和右侧的内容连接起来，中间用“|”表示游标的位置。

最后，用户通过输入一系列操作命令（如insert、delete、move、copy），直到输入“end”命令表示结束，程序将输出最终的文本结果。

时间复杂度

$O(n)$

代码

C++

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

// 定义两个双端队列，分别表示游标左边和右边的文本
deque<char> front, back;

// 插入操作，将输入字符串的字符添加到左侧双端队列末尾
void insert() {
    string str;
    cin >> str; // 读取输入的字符串
    for(char t: str) {
        front.push_back(t); // 将每个字符添加到左侧队列
    }
}

// 删除操作，从左侧双端队列末尾删除指定数量的字符
void del() {
    int len;
    cin >> len; // 读取要删除的字符数量
    while(len > 0 && len <= front.size()) { // 确保删除操作合法
        front.pop_back(); // 从左侧队列末尾删除字符
        len--; // 减少删除计数
    }
}

// 移动操作，将字符从一个双端队列的末尾移动到另一个双端队列的开头
void move() {
    int cnt;
    cin >> cnt; // 读取要移动的字符数量
    // 处理负数移动：从左侧移动到右侧
    while(cnt < 0 && -cnt <= front.size()) {
        cnt++; // 计数递增
        back.push_front(front.back()); // 从左侧队列末尾移动到右侧队列开头
        front.pop_back(); // 移除左侧队列末尾字符
    }
    // 处理正数移动：从右侧移动到左侧
    while(cnt > 0 && cnt <= back.size()) {
        cnt--; // 计数递减
        front.push_back(back.front()); // 从右侧队列开头移动到左侧队列末尾
        back.pop_front(); // 移除右侧队列开头字符
    }
}

// 复制操作，将左侧队列的所有字符复制到右侧队列的开头
void copy() {
    auto tmp = front; // 备份左侧队列
    while(tmp.size()) {
        back.push_front(tmp.back()); // 从备份队列末尾移动到右侧队列开头
        tmp.pop_back(); // 移除备份队列末尾字符
    }
}

// 输出操作，打印最终的文本结果
void print() {
    string s;
    for(char t: front) s += t; // 将左侧队列的字符连接到字符串s
    s += "|"; // 添加游标标识
    for(char t: back) s += t; // 将右侧队列的字符连接到字符串s
    cout << s << endl; // 输出结果
}

int main() {
    string op;
    while(cin >> op) { // 循环读取操作命令
        switch(op[0]) { // 根据命令类型调用相应的函数
            case 'i': // 插入
                insert();
                break;
            case 'd': // 删除
                del();
                break;
            case 'm': // 移动
                move();
                break;
            case 'c': // 复制
                copy();
                break;
            case 'e': // 输出并结束
                print();
                return 0; // 程序结束
        }
    }
}

python代码

# 初始化两个列表，s_left表示游标左侧的文本，s_right表示游标右侧的文本
s_left = []
s_right = []

# 持续读取用户输入的操作
while True:
    info = input().strip()  # 读取输入并去掉两端的空白字符
    
    if ' ' in info:  # 检查输入是否包含空格，表示是带参数的操作
        op, obj = info.split()  # 分割操作类型和参数
        
        if op == 'insert':  # 如果操作是插入
            s_left.extend(list(obj))  # 将字符串的每个字符添加到游标左侧的列表中
            
        elif op == 'delete' and 0 <= int(obj) <= len(s_left):  # 如果操作是删除，且删除长度合法
            # 从游标左侧删除指定数量的字符
            s_left[len(s_left) - int(obj):len(s_left)] = []  # 切片删除指定范围的字符
            
        elif op == 'move':  # 如果操作是移动
            if -len(s_left) <= int(obj) < 0:  # 检查是否为负数移动，且移动量合法
                # 从游标左侧移动字符到游标右侧
                tmp = s_left[len(s_left) + int(obj):len(s_left)]  # 获取要移动的字符
                s_left[len(s_left) + int(obj):len(s_left)] = []  # 从左侧删除这些字符
                s_right = tmp + s_right  # 将这些字符添加到右侧
                
            elif 0 < int(obj) <= len(s_right):  # 检查是否为正数移动，且移动量合法
                # 从游标右侧移动字符到游标左侧
                tmp = s_right[0:int(obj)]  # 获取要移动的字符
                s_right[0:int(obj)] = []  # 从右侧删除这些字符
                s_left += tmp  # 将这些字符添加到左侧
                
    else:
        op = info  # 处理没有参数的操作
        if op == 'end':  # 如果操作是结束
            break  # 退出循环
            
        elif op == 'copy':  # 如果操作是复制
            s_right = s_left + s_right  # 将游标左侧的文本复制到游标右侧
    
# 输出结果，将左侧和右侧的文本连接并在中间插入游标标识符“|”
print(''.join(s_left + ['|'] + s_right))

Java代码

import java.io.BufferedReader; // 引入BufferedReader类，用于高效读取输入
import java.io.IOException; // 引入IOException类，用于处理输入输出异常
import java.io.InputStreamReader; // 引入InputStreamReader类，将字节流转换为字符流
import java.util.Locale; // 引入Locale类，虽然在此代码中未使用
import java.util.StringTokenizer; // 引入StringTokenizer类，虽然在此代码中未使用

public class Main {
    public static void main(String[] args) throws IOException { // 主函数，抛出IOException
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 创建BufferedReader对象用于读取输入
        StringBuilder sb = new StringBuilder(); // 创建StringBuilder对象用于构建字符串
        String s = ""; // 定义字符串s以存储每行输入
        int pos = 0; // 初始化游标位置为0

        // 读取第一行输入
        s = br.readLine(); 
        if (s.length() == 0) // 如果输入为空，则继续读取下一行
            s = br.readLine();

        // 循环处理输入操作，直到遇到"end"
        while (!s.equals("end")) {
            String[] operations = s.trim().split(" "); // 按空格分割输入操作和参数
            if (operations[0].equals("insert")) { // 如果操作是插入
                sb.insert(pos, operations[1]); // 在游标位置插入指定字符串
                pos += operations[1].length(); // 更新游标位置
            } else if (operations[0].equals("delete")) { // 如果操作是删除
                int len = Integer.valueOf(operations[1]); // 将要删除的长度转换为整数
                // 检查删除长度是否合法
                if (len >= 0 && len <= pos) {
                    sb.delete(pos - len, pos); // 从游标左侧删除指定长度的字符
                    pos = pos - len; // 更新游标位置
                }
            } else if (operations[0].equals("move")) { // 如果操作是移动
                int cnt = Integer.valueOf(operations[1]); // 将移动的数量转换为整数
                if (cnt > 0 && pos + cnt <= sb.length()) { // 正向移动
                    pos = pos + cnt; // 更新游标位置
                } else if (cnt < 0 && pos + cnt >= 0) { // 反向移动
                    pos = pos + cnt; // 更新游标位置
                }
            } else if (operations[0].equals("copy")) { // 如果操作是复制
                sb.insert(pos, sb.substring(0, pos)); // 将游标左侧的字符串复制并插入到游标位置
            }
            // 读取下一行输入
            s = br.readLine(); 
            if (s.length() == 0) // 如果输入为空，则继续读取下一行
                s = br.readLine();
        }
        // 输出最终结果，将左侧和右侧的文本连接并在中间插入游标标识符“|”
        System.out.println(sb.substring(0, pos) + "|" + sb.substring(pos, sb.length()));
    }
}

#P1553. 2023.08.23-秋招-第二题-文本编辑器

2023.08.23-秋招-第二题-文本编辑器

题目内容

输入描述

输出描述

样例

题面描述

思路：模拟

题解

时间复杂度

代码

Status

Development

Support