You are building "find next" and "find previous" for a text editor.
The text is a one-line string T, and positions are counted from 0 at the first character.
The cursor points at one position of the text and starts at position 0.
A word w occurs at position s when the characters of T starting at position s, as many as the length of w, are exactly w.
Occurrences that overlap each other all count separately.
There are three commands.
N w: among the positions where w occurs, find the smallest one that is greater than the cursor.
If there is none, find the smallest position in the whole text where w occurs. In that case the answer may be the cursor position itself.
P w: among the positions where w occurs, find the largest one that is less than the cursor.
If there is none, find the largest position in the whole text where w occurs. Again the answer may be the cursor position itself.
When N or P finds a position, move the cursor there and print the position on one line.
If the position came from searching the whole text again, add one space and * after it.
If w does not occur in the text at all, print -1 and leave the cursor where it is.
G p: move the cursor to position p. Print nothing.
Input
The first line has the text T. T has length 1 to 5,000, uses only lowercase English letters and spaces, and does not start or end with a space. The second line has the number of commands q (1 ≤ q ≤ 1,000). Each of the next q lines has one command: the command letter, one space, then w or p. w is 1 to 20 lowercase English letters and may be longer than the text. p is an integer from 0 to (length of T − 1). There is at least one N or P command
Output
One line per N or P command, in command order. Positions are plain digits without commas
Example 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
Example 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
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Searching forward is nearly the same everywhere, but for searching backward the second argument means different things in different languages. Call the cursor c. Forward: 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). When nothing is found, Python/JS/TS/Java/C# return -1 and C++ returns string::npos. C strstr(T + c + 1, w) returns a pointer instead of a position, or NULL, so the position is p - T. Trap one: the search starts at c + 1. Starting at c finds the same occurrence again, so the second N ana of the first example gives 1 instead of 3. Starting at c plus the word length makes the first N ana skip the overlapping 1 and give 3. Trap two: the second argument of the backward search. In JS/TS/Java T.lastIndexOf(w, c - 1) and C++ T.rfind(w, c - 1) it means "occurrences that start at or before this position". In Python T.rfind(w, 0, end) the end is the end of the searched range, so the whole word must fit before it; pass c - 1 + len(w). With T.rfind(w, 0, c), the P ana after G 12 in the first example misses 11, which reaches over the cursor, and gives 3. In C# T.LastIndexOf(w, i, StringComparison.Ordinal) i is the character where the backward search starts, so the last character of the word cannot be past i. Pass c + w.Length - 2 (or T.Length - 1 if that is past the end); passing c - 1 gives 3 at the same place. Trap three: c - 1 when the cursor is 0. JS/TS lastIndexOf turns a negative value into 0 and finds a word at position 0, so the second P ban of the first example gives 0 instead of 7 *. In C++ positions are unsigned size_t, so 0 - 1 becomes the largest value, the whole text is searched, and it prints 7 without the *. C# stops with ArgumentOutOfRangeException when given -1. Java returns -1 for a negative value, so no extra check is needed. Trap four: position 0 is a hit. Testing k > 0 treats the 0 found by the first P ban of the first example as a miss and prints 7 *. Test a miss with k < 0 (in C++, k == string::npos). Trap five: the second search looks at the whole text. Searching only the part before the cursor prints -1 instead of 6 * when the word occurs only at the cursor, as in the second N world of the second example. C has no backward search function, so walk the positions downward and compare with strncmp. Craykon IndexOf takes no start position. Forward, cut first with text.Substring(c + 1).IndexOf(w) and add c + 1. Backward, search w.Reverse() from the front of text.Reverse() and turn the found position r back with n - r - wordLength.
Pythonmain.py · 37 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
본문 = Console.ReadLine();n = 본문.Length;// 거꾸로 찾는 기능이 없어서, 뒤집은 본문에서 뒤집은 낱말을 앞에서부터 찾는다거꾸로 = 본문.Reverse();q = Console.ReadLine().ToNumber();커서 = 0;for (i = 0; i < q; i++){ 칸 = Console.ReadLine().Split(" "); if (칸[0] == "G") { 커서 = 칸[1].ToNumber(); continue; } 낱말 = 칸[1]; 길 = 낱말.Length; 넘김 = false; k = -1; if (칸[0] == "N") { // 자리찾기에는 시작 자리를 줄 수 없어서, 커서 다음부터 잘라 찾고 잘라 낸 만큼 더한다 k = 본문.Substring(커서 + 1).IndexOf(낱말); if (k >= 0) { k += 커서 + 1; } else { k = 본문.IndexOf(낱말); 넘김 = true; } } else { 뒤낱말 = 낱말.Reverse(); // 본문의 s번 자리에서 시작한 낱말은 뒤집은 본문의 n - s - 길 자리에서 시작한다. // s가 커서 - 1 이하이면 그 자리는 n - 커서 + 1 - 길 이상이다 시작 = Mathf.Max(0, n - 커서 + 1 - 길); r = -1; if (시작 <= n) { r = 거꾸로.Substring(시작).IndexOf(뒤낱말); } if (r >= 0) { k = n - (r + 시작) - 길; } else { r = 거꾸로.IndexOf(뒤낱말); 넘김 = true; if (r >= 0) { k = n - r - 길; } } } if (k < 0) { Console.WriteLine("-1"); } else { 커서 = k; if (넘김) { Console.WriteLine(k + " *"); } else { Console.WriteLine(k + ""); } }}