你要实现文本编辑器的“查找下一个”和“查找上一个”。 正文是一行字符串 T，位置从最前面的字符算作 0 开始数。 光标指向正文中的一个位置，开始时在位置 0。 单词 w 出现在位置 s，是指 T 从位置 s 开始、与 w 等长的那些字符和 w 完全相同。 出现的位置彼此重叠时，也全部分别计算。 命令有三种。 N w：在 w 出现的位置中，找出大于光标的最小位置。 如果没有这样的位置，就在整个正文中找 w 出现的最小位置。 这时答案也可能就是光标所在的位置。 P w：在 w 出现的位置中，找出小于光标的最大位置。 如果没有这样的位置，就在整个正文中找 w 出现的最大位置。 这时答案同样可能就是光标所在的位置。 N 和 P 找到位置后，把光标移到那个位置，并在一行中输出这个位置。 如果这个位置是在整个正文中重新查找得到的，就在位置后面加一个空格和 *。 如果 w 在正文中一次也没有出现，输出 -1，光标保持不动。 G p：把光标移到位置 p。 不输出任何内容。
输入
第一行给出正文 T。 T 的长度为 1 ~ 5,000，只含英文小写字母和空格，开头和结尾都不是空格。 第二行给出命令数 q (1 ≤ q ≤ 1,000)。 接下来的 q 行每行一条命令，命令字母与 w 或 p 之间用一个空格隔开。 w 是 1 ~ 20 个英文小写字母，可能比正文还长。 p 是 0 以上、(T 的长度 − 1) 以下的整数。 至少有一条 N 或 P 命令
输出
每条 N、P 命令输出一行，按命令的顺序输出。 位置只写数字，不加逗号
样例 1 · stdin
banana bandana
8
N ana
N ana
P ban
P ban
G 12
P ana
N ana
N apple
stdout
1
3
0
7 *
11
1 *
-1
样例 2 · stdin
hello world
9
N world
N world
P world
P hello
G 10
N d
P d
N lo
P zz
stdout
6
6 *
6 *
0
10 *
10 *
3 *
-1
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
向前查找在各语言里几乎一样，但向后查找时第二个参数的含义因语言而异。 把光标记作 c。 向前查找是 Python T.find(w, c + 1)，JS、TS、Java T.indexOf(w, c + 1)，C# T.IndexOf(w, c + 1, StringComparison.Ordinal)，C++ T.find(w, c + 1)。 找不到时 Python、JS、TS、Java、C# 返回 -1，C++ 返回 string::npos。 C 的 strstr(T + c + 1, w) 返回的不是位置而是指针，找不到时是 NULL，所以用 p - T 求位置。 陷阱一：查找的起点是 c + 1。 从 c 开始找会再次找到刚才的位置，第一个例子的第二个 N ana 会得到 1 而不是 3。 从 c 加上单词长度的位置开始找，第一个 N ana 会跳过重叠的 1 而输出 3。 陷阱二：向后查找的第二个参数。 在 JS、TS、Java 的 T.lastIndexOf(w, c - 1) 和 C++ 的 T.rfind(w, c - 1) 中，它的意思是“起始位置不超过这个值的出现”。 Python T.rfind(w, 0, 终点) 的终点是查找范围的终点，整个单词必须落在它之前，所以要传 c - 1 + len(w)。 写成 T.rfind(w, 0, c) 的话，第一个例子中 G 12 之后的 P ana 会漏掉跨过光标的 11 而输出 3。 C# T.LastIndexOf(w, i, StringComparison.Ordinal) 的 i 是开始向后查找的那个字符的位置，单词的最后一个字符不能超过 i。 所以要传 c + w.Length - 2（超过正文末尾时传 T.Length - 1）；传 c - 1 的话在同一处会得到 3。 陷阱三：光标为 0 时的 c - 1。 JS、TS 的 lastIndexOf 会把负数改成 0，于是找到位置 0 的单词。 第一个例子的第二个 P ban 会输出 0 而不是 7 *。 C++ 的位置是无符号的 size_t，0 - 1 变成最大的值，于是在整个正文中查找，输出不带 * 的 7。 C# 传入 -1 会因 ArgumentOutOfRangeException 而停止。 Java 对负数返回 -1，所以不需要另外判断。 陷阱四：位置 0 也算找到。 用 k > 0 判断的话，第一个例子的第一个 P ban 找到的 0 会被当成没找到，输出 7 *。 是否没找到要用 k < 0（C++ 用 k == string::npos）来判断。 陷阱五：重新查找时要看整个正文。 如果只在光标之前重新查找，像第二个例子的第二个 N world 那样单词只出现在光标位置时，会输出 -1 而不是 6 *。 C 没有向后查找的函数，所以把位置一个个往下移，用 strncmp 比较。 Craykon 的 查找位置 不接受起始位置。 向前查找时先用 正文.截取(c + 1).查找位置(w) 截开再找，然后加上 c + 1。 向后查找时在 正文.反转() 中从前面查找 w.反转()，再用 n - r - 单词长度 把找到的位置 r 换算回来。
Pythonmain.py · 37 行
import sysdef main(): lines = sys.stdin.read().split("\n") text = lines[0] q = int(lines[1]) cur = 0 out = [] for line in lines[2:2 + q]: kind, arg = line.split() if kind == "G": cur = int(arg) continue wrapped = False if kind == "N": # 커서 다음 칸부터 찾는다 k = text.find(arg, cur + 1) if k < 0: k = text.find(arg) wrapped = True else: # rfind의 끝 범위는 '시작 자리'가 아니라 '찾을 구간의 끝'이다. # 시작 자리가 cur - 1 이하이려면 구간은 cur - 1 + len(arg)에서 끝난다 k = text.rfind(arg, 0, cur - 1 + len(arg)) if k < 0: k = text.rfind(arg) wrapped = True if k < 0: out.append("-1") else: cur = k out.append(f"{k} *" if wrapped else str(k)) print("\n".join(out))main()
JavaScriptmain.js · 35 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const text = lines[0];const q = Number(lines[1]);let cur = 0;const out = [];for (let i = 2; i < 2 + q; i++) { const [kind, arg] = lines[i].split(" "); if (kind === "G") { cur = Number(arg); continue; } let wrapped = false; let k; if (kind === "N") { k = text.indexOf(arg, cur + 1); if (k < 0) { k = text.indexOf(arg); wrapped = true; } } else { // lastIndexOf(w, -1)은 -1을 0으로 고쳐 0번 자리를 찾아 버리니 cur가 0일 때는 부르지 않는다 k = cur > 0 ? text.lastIndexOf(arg, cur - 1) : -1; if (k < 0) { k = text.lastIndexOf(arg); wrapped = true; } } if (k < 0) { out.push("-1"); } else { cur = k; out.push(wrapped ? `${k} *` : String(k)); }}console.log(out.join("\n"));
TypeScriptmain.ts · 35 行
const lines: string[] = require("fs").readFileSync(0, "utf8").split("\n");const text: string = lines[0];const q: number = Number(lines[1]);let cur = 0;const out: string[] = [];for (let i = 2; i < 2 + q; i++) { const [kind, arg] = lines[i].split(" "); if (kind === "G") { cur = Number(arg); continue; } let wrapped = false; let k: number; if (kind === "N") { k = text.indexOf(arg, cur + 1); if (k < 0) { k = text.indexOf(arg); wrapped = true; } } else { // lastIndexOf(w, -1)은 -1을 0으로 고쳐 0번 자리를 찾아 버리니 cur가 0일 때는 부르지 않는다 k = cur > 0 ? text.lastIndexOf(arg, cur - 1) : -1; if (k < 0) { k = text.lastIndexOf(arg); wrapped = true; } } if (k < 0) { out.push("-1"); } else { cur = k; out.push(wrapped ? `${k} *` : String(k)); }}console.log(out.join("\n"));
JavaMain.java · 44 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String text = br.readLine(); int q = Integer.parseInt(br.readLine().trim()); int cur = 0; StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { String[] parts = br.readLine().split(" "); String arg = parts[1]; if (parts[0].equals("G")) { cur = Integer.parseInt(arg); continue; } boolean wrapped = false; int k; if (parts[0].equals("N")) { k = text.indexOf(arg, cur + 1); if (k < 0) { k = text.indexOf(arg); wrapped = true; } } else { // 둘째 값은 '시작 자리의 상한'이다. 음수를 주면 그냥 -1이 나온다 k = text.lastIndexOf(arg, cur - 1); if (k < 0) { k = text.lastIndexOf(arg); wrapped = true; } } if (k < 0) { out.append("-1\n"); } else { cur = k; out.append(k).append(wrapped ? " *\n" : "\n"); } } System.out.print(out); }}
C#Main.cs · 57 行
using System;using System.Text;class Program{ static void Main() { string text = Console.ReadLine(); int n = text.Length; int q = int.Parse(Console.ReadLine()); int cur = 0; var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] parts = Console.ReadLine().Split(' '); string arg = parts[1]; if (parts[0] == "G") { cur = int.Parse(arg); continue; } bool wrapped = false; int k; if (parts[0] == "N") { k = text.IndexOf(arg, cur + 1, StringComparison.Ordinal); if (k < 0) { k = text.IndexOf(arg, StringComparison.Ordinal); wrapped = true; } } else { // LastIndexOf의 둘째 값은 '거꾸로 찾기 시작하는 글자'다. // 찾은 낱말의 끝 글자가 그 자리를 넘지 못하므로, 시작 자리가 cur - 1 이하가 되게 하려면 // cur - 1에서 시작한 낱말의 끝 글자 자리인 cur + 길이 - 2를 준다 k = cur > 0 ? text.LastIndexOf(arg, Math.Min(n - 1, cur + arg.Length - 2), StringComparison.Ordinal) : -1; if (k < 0) { k = text.LastIndexOf(arg, StringComparison.Ordinal); wrapped = true; } } if (k < 0) { sb.Append("-1\n"); } else { cur = k; sb.Append(k).Append(wrapped ? " *\n" : "\n"); } } Console.Write(sb); }}
C++main.cpp · 46 行
#include <iostream>#include <string>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string text; getline(cin, text); int q; cin >> q; size_t cur = 0; for (int i = 0; i < q; i++) { char kind; string arg; cin >> kind >> arg; if (kind == 'G') { cur = stoul(arg); continue; } bool wrapped = false; size_t k; if (kind == 'N') { k = text.find(arg, cur + 1); if (k == string::npos) { k = text.find(arg); wrapped = true; } } else { // rfind의 둘째 값은 '시작 자리의 상한'이다. // cur가 0일 때 cur - 1은 size_t에서 가장 큰 값(npos)이 되어 전체를 찾아 버리니 따로 막는다 k = cur > 0 ? text.rfind(arg, cur - 1) : string::npos; if (k == string::npos) { k = text.rfind(arg); wrapped = true; } } if (k == string::npos) { cout << -1 << '\n'; } else { cur = k; cout << k << (wrapped ? " *\n" : "\n"); } } return 0;}
Cmain.c · 58 行
#include <stdio.h>#include <stdlib.h>#include <string.h>static char text[5005];/* 시작 자리가 hi 이하인 것 가운데 가장 뒤의 자리. 없으면 -1. C에는 거꾸로 찾는 strstr가 없어서 자리를 하나씩 내려가며 견준다 */static int find_last(int n, const char *w, int len, int hi) { if (hi > n - len) hi = n - len; for (int s = hi; s >= 0; s--) { if (strncmp(text + s, w, (size_t)len) == 0) return s; } return -1;}int main(void) { if (!fgets(text, sizeof text, stdin)) return 0; text[strcspn(text, "\n")] = '\0'; int n = (int)strlen(text); int q; if (scanf("%d", &q) != 1) return 0; int cur = 0; for (int i = 0; i < q; i++) { char kind; char arg[32]; if (scanf(" %c %30s", &kind, arg) != 2) return 0; if (kind == 'G') { cur = atoi(arg); continue; } int len = (int)strlen(arg); int wrapped = 0; int k; if (kind == 'N') { /* strstr는 자리가 아니라 포인터를 돌려준다. 없으면 NULL */ const char *p = strstr(text + cur + 1, arg); if (p == NULL) { p = strstr(text, arg); wrapped = 1; } k = p == NULL ? -1 : (int)(p - text); } else { k = find_last(n, arg, len, cur - 1); if (k < 0) { k = find_last(n, arg, len, n - 1); wrapped = 1; } } if (k < 0) { printf("-1\n"); } else { cur = k; printf(wrapped ? "%d *\n" : "%d\n", k); } } return 0;}
Craykonmain.cray · 74 行
본문 = 控制台.读行();n = 본문.长度;// 거꾸로 찾는 기능이 없어서, 뒤집은 본문에서 뒤집은 낱말을 앞에서부터 찾는다거꾸로 = 본문.反转();q = 控制台.读行().转数字();커서 = 0;循环 (i = 0; i < q; i++){ 칸 = 控制台.读行().分割(" "); 如果 (칸[0] == "G") { 커서 = 칸[1].转数字(); 继续; } 낱말 = 칸[1]; 길 = 낱말.长度; 넘김 = 假; k = -1; 如果 (칸[0] == "N") { // 자리찾기에는 시작 자리를 줄 수 없어서, 커서 다음부터 잘라 찾고 잘라 낸 만큼 더한다 k = 본문.截取(커서 + 1).查找位置(낱말); 如果 (k >= 0) { k += 커서 + 1; } 否则 { k = 본문.查找位置(낱말); 넘김 = 真; } } 否则 { 뒤낱말 = 낱말.反转(); // 본문의 s번 자리에서 시작한 낱말은 뒤집은 본문의 n - s - 길 자리에서 시작한다. // s가 커서 - 1 이하이면 그 자리는 n - 커서 + 1 - 길 이상이다 시작 = 数学.较大值(0, n - 커서 + 1 - 길); r = -1; 如果 (시작 <= n) { r = 거꾸로.截取(시작).查找位置(뒤낱말); } 如果 (r >= 0) { k = n - (r + 시작) - 길; } 否则 { r = 거꾸로.查找位置(뒤낱말); 넘김 = 真; 如果 (r >= 0) { k = n - r - 길; } } } 如果 (k < 0) { 控制台.输出("-1"); } 否则 { 커서 = k; 如果 (넘김) { 控制台.输出(k + " *"); } 否则 { 控制台.输出(k + ""); } }}