テキストエディタの「次を検索」と「前を検索」を作る。 本文は1行の文字列 T で、位置は先頭の文字を 0 として数える。 カーソルは本文の1つの位置を指し、はじめは位置 0 にある。 単語 w が位置 s に現れるとは、T の位置 s から w の長さぶんの文字が w とちょうど同じであることをいう。 現れる位置どうしが重なっていても、すべて別々に数える。 命令は3種類ある。 N w: w が現れる位置のうち、カーソルより大きいものの中で最も小さい位置を探す。 そのような位置がなければ、本文全体で w が現れる最も小さい位置を探す。 このときはカーソルの位置そのものが答えになることもある。 P w: w が現れる位置のうち、カーソルより小さいものの中で最も大きい位置を探す。 そのような位置がなければ、本文全体で w が現れる最も大きい位置を探す。 このときもカーソルの位置そのものが答えになることがある。 N と P で位置が見つかったら、カーソルをその位置へ移し、その位置を1行に出力する。 本文全体を探し直して得た位置なら、位置のあとに空白1つと * を付ける。 w が本文に一度も現れなければ -1 を出力し、カーソルは動かさない。 G p: カーソルを位置 p へ移す。 何も出力しない。
入力
1行目に本文 T が与えられる。 T の長さは 1 ~ 5,000 で、英小文字と空白だけからなり、先頭と末尾は空白ではない。 2行目に命令の数 q (1 ≤ q ≤ 1,000) が与えられる。 続く q 行に命令が1行に1つずつ、命令の文字と w または p を空白1つで区切って与えられる。 w は英小文字 1 ~ 20 文字で、本文より長いこともある。 p は 0 以上 (T の長さ − 1) 以下の整数である。 N または P の命令が少なくとも1つある
出力
N, P の命令ごとに1行ずつ、命令の順に出力する。 位置はカンマなしの数字だけで書く
例 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 言語の解答
前向きの検索はどの言語もほぼ同じですが、後ろ向きの検索は2番目の値の意味が言語ごとに違います。 カーソルを 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 で位置を求めます。 罠その1: 検索の開始位置は c + 1 です。 c から探すと今見つけた位置をもう一度見つけ、1つ目の例の2回目の N ana が 3 ではなく 1 になります。 c に単語の長さを足した位置から探すと、最初の N ana が重なっている 1 を飛ばして 3 を出します。 罠その2: 後ろ向き検索の2番目の値です。 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) と書くと、1つ目の例の 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 になります。 罠その3: カーソルが 0 のときの c - 1 です。 JS・TS の lastIndexOf は負の値を 0 に直すので、位置 0 の単語を見つけてしまいます。 1つ目の例の2回目の P ban が 7 * ではなく 0 になります。 C++ は位置が符号なしの size_t なので 0 - 1 が最大の値になり、本文全体を探して * なしの 7 を出します。 C# は -1 を渡すと ArgumentOutOfRangeException で止まります。 Java は負の値に -1 を返すので、特別な確認は要りません。 罠その4: 位置 0 も見つかったことになります。 k > 0 で確かめると、1つ目の例の最初の P ban で見つけた 0 を見つからなかったと扱い、7 * を出します。 見つからなかったかどうかは k < 0（C++ は k == string::npos）で確かめます。 罠その5: 探し直すときは本文全体を見ます。 カーソルより前だけを探し直すと、2つ目の例の2回目の N world のように単語がカーソルの位置にしかないとき、6 * ではなく -1 を出します。 C には逆向きに探す関数がないので、位置を1つずつ下げながら strncmp で比べます。 クレイコンの 位置検索 は開始位置を受け取りません。 前向きは 本文.切り出す(c + 1).位置検索(w) で切ってから探し、c + 1 を足します。 後ろ向きは 本文.逆に() の中で w.逆に() を前から探し、見つけた位置 r を n - 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 + ""); } }}