IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
196 . 經典問題（Classic Problem）
TopCoder
Tags
Description
（不想看故事的可以跳到分隔線下）
在現在的世界裡，多元並蓄、自由開放是思想的潮流所在。所謂自由，也包含了關於宗教上的自由：從大宗的俗稱「世界三大宗教」的佛、伊斯蘭、基督教，到諸如維京、希臘、日本神道教等，都允許人們自由信教。
這就是一個發跡於德田館的宗教的起源故事。
宗教創立之初，眾神（又稱上帝）們撰寫了一部宗教經典，以一個全為小寫字母組成且長度為 $N$ 的字串 $S$ 所組成。同時，還向信徒們宣告了一個挑戰：
「我們在 $S$ 中藏了密碼，為 $Q$ 個數字。若 $S[l, r]$ 為由 $S$ 的第 $l$ 個字到第 $r$ 個字的子字串，則密碼的第 $i$ 個數字為 $S[l_i, r_i]$ 在 $S$ 中第一次出現的位置。找到完整密碼者，即可升天，躋身上帝之列。」
現在，你知道了 $S$、$Q$、和每一個 $l_i, r_i$ 的值，請你寫一程式讓你能夠變成上帝吧！
————分隔線————
定義 $S[l, r]$ 為由 $S$ 的第 $l$ 個字到第 $r$ 個字組成的子字串。舉例來說，若 $S = \texttt{abcde}$，則 $S[1, 3] = \texttt{abc}$。
給定一個全為小寫字母組成且長度為 $N$ 的字串 $S$，有 $Q$ 筆詢問：第 $i$ 筆會給定兩個數字 $l_i, r_i$，請找一個最小的 $k_i$，使得 $S[k_i, k_i + (r_i - l_i)] = S[l_i, r_i]$（即找出 $S[l_i, r_i]$ 在 $S$ 中第一次出現的位子的左界）。
Input Format
第一行有兩個數字 $N, Q$，代表字串 $S$ 的長度與詢問的數量。
第二行有一個字串 $S$。
接下來有 $Q$ 行，每一行有兩個數字 $l_i, r_i$。
- $1\leq N, Q \leq 10^ 5$
- $|S| = N$
- $S$ 僅由小寫字母所組成
- $1 \leq l_i \leq r_i \leq N$
Output Format
請輸出 $Q$ 行，每一行有一個數字 $k_i$ 代表第 $i$ 個詢問的答案。
Sample Input 1
ittmcsvmoa
6 7
5 8
4 4
10 10
6 7
1 9
2 3
4 5
6 8
9 9
Sample Output 1
5
4
10
6
1
2
4
6
9
Sample Input 2
aaabbb
1 1
1 2
1 3
1 4
1 5
1 6
2 2
2 3
2 4
2 5
2 6
3 3
3 4
3 5
3 6
4 4
4 5
4 6
5 5
5 6
6 6
Sample Output 2
1
1
1
1
1
1
1
2
2
2
1
3
3
3
4
4
4
4
4
4
Hints
Problem Source
IOICamp 2022 Day5 pK
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~8 | $N, Q \leq 10^ 2$ | 17 |
| 3 | 0~24 | $NQ \leq 10^ 6$ | 21 |
| 4 | 0~35 | 無額外限制 | 62 |