TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

64.3% (9/14)

Description

佩佩和喬治很喜歡玩模仿對方的遊戲,但是今天他們想要改變遊戲規則,改成如果誰先模仿對方講話就算輸了。遊戲的方法與步驟是:
1. 佩佩和喬治先猜拳決定誰當出題者,誰當猜題者。
2. 出題者先寫下⼀個由 ‘A’ 和 ‘B’ 所組成且⾧度為 M 的字串 X,並且不可以讓猜題者看到。
3. 猜題者寫下⼀個由 ‘A’ 和 ‘B’ 所組成且⾧度為 N 的字串 Y,並且不可以讓出題者看到;當然,N 的數⽬⼀定⽐ M 來得⼤。
4. 如果猜題者的字串 Y 中存在⼀個⼦字串剛好等於出題者的字串 X ,則猜題者就算輸了,要接受處罰跑操場。
5. 猜題者可以根據出題者的字串 X,從猜題者的字串Y 中刪除部分的字元,直到字串 Y 中不再含有⼀個⼦字串剛好等於字串 X。
6. 猜題者被處罰跑操場的圈數,恰好等於在步驟5 中刪除的字元數。
例如,倘若出題者的字串是 ‘ABA’ ,而猜題者的字串是 ‘ABABAA’ ,由於後者存在一個子字串等於前者,因此判定猜題者輸了;同時,由於猜題者只要移除第三個字元,將字串改成 ‘ABBAA’ 即可完全避免有子字串等於 ‘ABA’ ,因此猜題者只需要被處罰跑一圈操場即可。你的任務便是協助猜題者,找出最佳的策略減少被處罰跑操場的圈數。註:若猜題者的字串 Y 中不存在任何一個子字串等於字串 X ,則處罰跑操場的圈數為 0。

Input Format

第一行為一個出題者所提供的字串,第二行為一個猜題者所提供的字串。

Output Format

請輸出該組測資中猜題者根據最佳策略所需要被處罰跑操場的圈數。

Sample Input

ABA
ABABAA

Sample Output

1

Hints

本題共有五組測試資料,每組20 分:
第一組測試資料中,M = 2 且2 < N ≤ 10。
第二組測試資料中,2 ≤ M ≤ 5,2 < N ≤ 20,且M < N。
第三組測試資料中,2 ≤ M ≤ 10,2 < N ≤ 100,且M < N。
第四組測試資料中,2 ≤ M ≤ 10,2 < N ≤ 1000,且M < N。
第五組測試資料中,2 ≤ M ≤ 100,2 < N ≤ 1000,且M < N。

Problem Source

臺北市104 學年度高級中學資訊學科能力競賽

Subtasks

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536