시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 1024 MB | 191 | 32 | 25 | 22.727% |
You are given a string $s$ and several queries.
Each query consists of a string $t$ and an integer $k$. For each query, determine the $k$th position in $s$ where a substring matching $t$ starts. If $t$ occurs fewer than $k$ times in $s$, print −1.
The first line of input contains a single string $s$ ($1 \le |s| \le 2 \cdot 10^5$), which is the queriable string. It will consist only of lower-case letters.
The next line of input contains a single integer $q$ ($1 \le q \le 2 \cdot 10^5$), which is the number of queries that follow.
Each of the next $q$ lines contains a string $t$ ($1 \le |t|$) and an integer $k$ ($1 \le k \le |s|$). This represents a query for the $k$th occurrence of $t$ in $s$. The string $t$ will consist only of lower-case letters. The sum of all $|t|$’s will be $\le 2 \cdot 10^5$.
Output a single integer, which is the position of the start of the $k$th occurrence of $t$ in $s$, or −1 if $t$ occurs fewer than $k$ times in $s$. The first character in $s$ is at position 1.
abacabadabacaba 4 a 7 e 3 bac 2 abada 1
13 -1 10 5