a655. 字串比對 - 旦旦解題農場

內容

$裸題$

給予兩個字串$a, b$，求$a$的連續子序列中有幾個和$b$完全相同的。

($a, b$ 皆由小寫字母組成)

輸入說明

第一行輸入一數$T$，代表接下來有$T$筆測資。

每一筆測資有三行

第一行有兩數$N, M$，代表$a, b$的大小。

接下來兩行為$a, b$字串

輸出說明

對每一筆測資輸出$a$的連續子序列中有幾個適合$b$完全相同的

範例輸入

3
6 3
abccba
abc
6 2
ababcb
ba
5 2
aaaaa
aa

範例輸出

1
1
4

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , >50M
公開測資點#16 (5%): 1.0s , >50M
公開測資點#17 (5%): 1.0s , >50M
公開測資點#18 (5%): 1.0s , >50M
公開測資點#19 (5%): 1.0s , >50M

提示：

$25\%$測資，$M\leq N \leq 10^4$

$50\%$測資，$M\leq N \leq 10^5$

$100\%$測資，$M\leq N \leq 10^6 T \leq 10$

$記得加上ios::sync\_with\_stdio(0), cin.tie(0)$

$2021/11/4 測資補強$

標籤:

KMP 字符串哈希演算法

出處:

[管理者：

william1010121 (郭勝威)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」