HW 4:How's Problem

Description

English version (translated by Seth Austin Harding)

皓皓是個喜歡讀書的天才小兒童,天底下的所有問題都難不倒他,因此有一個廣為人知的稱號 — 「一眼秒題皓大爺」。
今天喜歡看書的他在看一本名為「DSA」的書,其中有一題讓他看了兩秒還想不出答案,因此他便很高興的拿著這一題和他的好朋友 — 裴裴討論,可惜的是兩個臭皮匠勝不過一個諸葛亮(因為要三個才夠(X)),對這一題依然沒有半點頭緒,請問你能寫個程式來幫助皓皓解決這個難題嗎?

這道題目如下:
給你一個初始的字串S,及一個正整數Q
接下來有Q個問題,每種問題有三種形式,分別如下:
1. 「1 c」 其中c是一個字元,代表要加一個字元c在字串S的前方。
2. 「2 c」 其中c是一個字元,代表加一個字元c在字串S的後方。
3. 「3 Ti」 其中Ti是一個字串,如果是這種形式的問題,要輸出字串TiS中出現幾次。

舉例來說,如果一開始S = "cd", Q = 5,並且依序的5個問題如下:
1 'b' → 此時S = "bcd"
1 'a' → 此時S = "abcd"
2 'e' → 此時S = "abcde"
3 "cd" → 此時S = "abcde""cd"S中出現一次,因此要輸出1
3 "aa" → 此時S = "abcde""aa"S中出現零次,因此要輸出0

Input / Output Format

請由stdin讀入、stdout輸出。

輸入的第一行有一個字串S,如題目所述。
輸入的第二行有一個正整數Q,代表有Q個問題。
接下來的Q行,每行形式為「1 c」、「2 c」、「3 Ti」三種中的一種,其中c為字元、Ti為一字串。

Sample Input 1 Sample Output 1
cd
5
1 b
1 a
2 e
3 cd
3 aa
1
0
Sample Input 2 Sample Output 2
ababa
1
3 aba
2
Sample Input 3 Sample Output 3
d
8
1 a
2 e
1 b
3 ba
2 n
3 bad
2 d
3 badend
1
1
1
Sample Input 4 Sample Output 4
bccbcabbcc
10
1 a
1 c
1 a
1 a
3 b
3 a
2 a
3 ab
2 b
2 b
4
4
2
Sample Input 5 Sample Output 5
點此下載 點此下載
Subtasks

對於所有的Subtask皆滿足:
所有字元皆為英文小寫字母
1 ≤ 字串S的初始長度 ≤ 105
1 ≤ Q ≤ 105
0 ≤ 所有字串Ti的長度總和 ≤ 105

Subtask 1 (5 pt):
1 ≤ 字串S的初始長度 ≤ 105
Q = 1
所有問題皆為第三種問題

Subtask 2 (5 pt):
1 ≤ 字串S的初始長度 ≤ 1000
1 ≤ Q ≤ 1000
0 ≤ 所有字串Ti的長度總和 ≤ 104

Subtask 3 (30 pt):
1 ≤ 字串S的初始長度 ≤ 105
1 ≤ Q ≤ 105
所有字串Ti的長度 ≥ 104
0 ≤ 所有字串Ti的長度總和 ≤ 105

Subtask 4 (30 pt):
1 ≤ 字串S的初始長度 ≤ 105
1 ≤ Q ≤ 105
1 ≤ 所有字串Ti的長度 ≤ 10
0 ≤ 所有字串Ti的長度總和 ≤ 105

Subtask 5 (30 pt):
原題設條件
1 ≤ 字串S的初始長度 ≤ 105
0 ≤ 所有字串Ti的長度總和 ≤ 105

Suggestions & Hints
1. 關鍵字:rolling hash(可參考此連結第二頁,或說明投影片)、binary search tree(map)、hash table(unordered_map)、square root decomposition(平方分割、分塊法)

2. 可以仔細想想看subtask3及subtask4分別有什麼特殊性?

上傳連結