i510. 尋找子字串 - 高中生程式解題系統

內容

給定兩字串 s , t ，問 t 是否是 s 的子字串，如果是的話輸出該子字串在 s 的起始位置(0-indexed)。如果有多個子字串都是 t ，輸出第一個符合的子字串的起始位置。

輸入說明

多筆測資

每筆測資共兩行

第一行會有兩個正整數 n , m ( 1<= n , m <=10⁵ 且 n>=m ) 代表 s 與 t 的長度，正整數之間以空格間隔

第二行有兩個字串 s , t ，字串之間以空格間隔

s , t 裡只包含小寫英文字母

輸出說明

如果 t 是 s 的子字串，輸出兩行

第一行輸出 "Yes"

第二行先輸出 "pos: "，再輸出第一個符合的子字串在s的起始位置(0-indexed)

如果 t 不是 s 的子字串

直接輸出 "No"

範例輸入 #1

3 2
aab ab
3 1
aaa a
3 2
aab ac

範例輸出 #1

Yes
pos: 1
Yes
pos: 0
No

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (20%): 3.0s , <10M
公開測資點#1 (80%): 2.0s , <50M

提示：

測資有誤請告知

希望可以卡掉O(n*m)的解法

標籤:

出處:

[管理者：

s1082942@g.n ... (sellie) ]