i510: 尋找子字串
Tags :
Accepted rate : 31人/42人 ( 74% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-27 22:05

Content

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

Input

多筆測資

每筆測資共兩行

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

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

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

Output

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

第一行輸出 "Yes"

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

如果 t 不是 s 的子字串

直接輸出 "No"

Sample Input #1
3 2
aab ab
3 1
aaa a
3 2
aab ac
Sample Output #1
Yes
pos: 1
Yes
pos: 0
No
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 3.0s , <10M
公開 測資點#1 (80%): 2.0s , <50M
Hint :

測資有誤請告知

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

Tags:
出處:
[管理者: s1082942@g.n...(sellie) ]


ID User Problem Subject Hit Post Date
31277 krameri120(科科) i510
38 2022-07-21 23:03
31276 krameri120(科科) i510
47 2022-07-21 22:57