d990. 最終章－痛ましいです - 高中生程式解題系統

內容

前文:

學測悲劇啊，哈哈，比賽沒得名，成績也中下，現在?
上次被慘殺的題目，不收了，殺自己(KMP)用，來吧 !
再次讓我...

正文:

有用過Word嗎?有用過記事本嗎?曾經使用過尋找嗎?
現在請你模仿尋找的功能，找尋存在的資料筆數。

輸入說明

每組測資第一行會有一個主字串，長度 L ≦ 10,0000

接下來會有一行，有一個正數 N， N ≦ 1,0000

接下來會有N行要查詢的字串，其長度 L ≦ 10,0000

字串組成由 a.b...z。

輸出說明

對每一個查詢輸出其個數

範例輸入 #1

aabaabaa
1 
aabaa

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <10M
公開測資點#1 (30%): 1.0s , <10M
公開測資點#2 (30%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <10M

提示：

aabaabaa

Ans. 2個

Test1:

sigma(L)=150,1827，sigma(Ans)=31,6204

Test2:

sigma(L)=150,6175，sigma(Ans)=307,4546

Test3:

sigma(L)=49,8679，sigma(Ans)=5375,6707

Test4:

sigma(L)=394,6851，sigma(Ans)=4,6556

標籤:

Suffix Array

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
26269	alexrobotvm0 ... (黃子軒)	d990	suffix array	520	2021-07-29 17:03