刷题笔记合集🔗

代码编辑器

问题描述

某公司为了更高效的编写代码，邀请你开发一款代码编辑器程序。

程序的输入为已有的代码文本和指令序列，程序需输出编辑后的最终文本。指针初始位置位于文本的开头。
支持的指令（ 为大于等于 的整数， 为无空格的字符串）：

• FORWARD 指针向前（右）移动 ，如果指针移动位置超过了文本末尾，则将指针移动到文本末尾
• BACKWARD 指针向后（左）移动 ，如果指针移动位置超过了文本开头，则将指针移动到文本开头
• SEARCH-FORWARD 从指针当前位置向前查找 并将指针移动到 的起始位置，如果未找到则保持不变
• SEARCH-BACKWARD 在文本中向后查找 并将指针移动到 的起始位置，如果未找到则保持不变
• INSERT 在指针当前位置前插入 ，并将指针移动到 的结尾
• REPLACE 在指针当前位置替换并插入字符（删除原有字符，并增加新的字符）
• DELETE 在指针位置删除 个字符

输入格式

第一行为命令列表的长度 。

第二行为文件中的原始文本。

接下来的 行，每行为一个指令。

输出格式

编辑后的最终结果。

样例输入

1
ello
INSERT h

2
hllo
FORWARD 1
INSERT e

样例输出

hello

hello

数据范围

• 文本最长长度不超过

题解

这道题目考察的是字符串处理和模拟操作，需要我们实现一个简单的代码编辑器。

解题思路很直接：维护一个字符串和一个当前指针位置，然后按照指令进行操作。关键是要正确理解和处理每种指令的逻辑。

首先，我们需要理解几个容易混淆的概念：

• "向前"指向右移动（文本后方）
• "向后"指向左移动（文本前方）
• SEARCH-FORWARD是从当前位置向右查找
• SEARCH-BACKWARD是从当前位置向左查找

处理每种指令的方法：

1. FORWARD X：将指针向右移动X位，但不超过文本长度
2. BACKWARD X：将指针向左移动X位，但不小于0
3. SEARCH-FORWARD：从当前位置向右查找目标词，找到则移动指针
4. SEARCH-BACKWARD：从当前位置向左查找目标词，找到则移动指针
5. INSERT：在当前位置插入词，并更新指针到插入内容之后
6. REPLACE：从当前位置开始替换文本
7. DELETE：从当前位置删除指定长度的文本

实现这些功能时，需要注意字符串操作的边界条件处理。比如在替换文本时，如果替换的内容超出了原文本长度，我们需要做适当调整。

时间复杂度分析：对于每条指令，最坏情况下需要O(n)的时间复杂度（比如在字符串中查找或替换），总共有K条指令，所以总时间复杂度为O(K×n)，其中n是文本长度。这对于题目给出的约束（文本长度不超过256K）是可接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
k = int(input())
s = input()
cmds = [input().split() for _ in range(k)]

# 当前指针位置
pos = 0

# 处理每条指令
for cmd in cmds:
    cmd_type = cmd[0]
    
    # 处理前进指令
    if cmd_type == "FORWARD":
        # 向右移动X位，但不超过文本长度
        dist = int(cmd[1])
        pos = min(pos + dist, len(s))
    
    # 处理后退指令
    elif cmd_type == "BACKWARD":
        # 向左移动X位，但不小于0
        dist = int(cmd[1])
        pos = max(pos - dist, 0)
    
    # 处理向前搜索
    elif cmd_type == "SEARCH-FORWARD":
        # 从当前位置向右查找目标词
        word = cmd[1]
        idx = s.find(word, pos)
        if idx != -1:
            pos = idx
    
    # 处理向后搜索
    elif cmd_type == "SEARCH-BACKWARD":
        # 从当前位置向左查找目标词
        word = cmd[1]
        # 找到位置0到pos之间最右边出现的word
        idx = s.rfind(word, 0, pos)
        if idx != -1:
            pos = idx
    
    # 处理插入操作
    elif cmd_type == "INSERT":
        # 在当前位置前插入word，并移动指针
        word = cmd[1]
        s = s[:pos] + word + s[pos:]
        pos += len(word)
    
    # 处理替换操作
    elif cmd_type == "REPLACE":
        # 替换当前位置的文本
        word = cmd[1]
        s = s[:pos] + word + s[pos+len(word):]
    
    # 处理删除操作
    elif cmd_type == "DELETE":
        # 删除当前位置的X个字符
        count = int(cmd[1])
        s = s[:pos] + s[pos+count:]

# 输出结果
print(s)

• Cpp

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

int main() {
    int k;
    string s, cmd, val;
    
    // 读取命令数量和初始文本
    cin >> k;
    cin.ignore(); // 忽略换行符
    getline(cin, s);
    
    int pos = 0; // 当前指针位置
    
    // 处理每条命令
    for (int i = 0; i < k; i++) {
        cin >> cmd;
        
        // 前进命令
        if (cmd == "FORWARD") {
            int x;
            cin >> x;
            //