문서 편집기의 '다음 찾기'와 '이전 찾기'를 만든다.
본문은 한 줄짜리 문자열 T이고, 자리는 맨 앞 글자를 0으로 센다.
커서는 본문의 한 자리를 가리키며 처음에는 0번 자리에 있다.
낱말 w가 s번 자리에서 나온다는 것은 T의 s번 자리부터 w의 길이만큼의 글자가 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()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 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가 3이 아니라 1이 돼요. 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이 7 *가 아니라 0이 돼요. 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처럼 낱말이 커서 자리에만 있을 때 6 * 대신 -1을 내요. C에는 거꾸로 찾는 함수가 없어서 자리를 하나씩 내려가며 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 + ""); } }}