a338. 基因解碼 - Zero1 Online Judge System

Content

小明正在幫一位遺傳學教授做實習生。教授手上有 N 個長度為 6 的基本基因組, 這些基本基因組可以看成一個只含 A, C, G, 及 U 這四個字母的字串。教授手上還有另一長度為 K 的基因鏈, 這個基因鏈亦可以看成一個只含有 A, C, G, 及 U 這四個字母的長長字串。現在教授要小明幫他找出那 N 個基本基因組每一個在基因鏈內出現的次數。於是小明決定編寫一個程式來解決這個問題。

Input

輸入資料的第一行含有兩個整數 N 及 K, 它們分別代表基本基因組的個數及基因鏈的長度。隨後的 N 行中, 每行有一個長度為 6 的字串, 這些字串只含英文字母 A, C, G, U, 每個字串代表一個基本基因組。最後一行上有一個長度為 K 的長字串, 這個字串亦只含有英文字母 A, C, G, U。它代表著長度為 K 的基因鏈。

這 N 個基本基因組是沒有任何重複的。1 ≤ N ≤ 4,000 及 1 ≤ K ≤ 4,000,000

Output

輸出應共有 N 行, 每行應有一個非負整數, 它們順序表示著對應輸入中的基本基因組在基因鏈中出現的次數。

Sample Input #1

3 20
ACCGUU
CACUAA
ACACAC
ACCGUUACACACACACUAAG

Sample Output #1

1
1
3

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (9%): 1.0s , <1K
公開測資點#1 (9%): 1.0s , <1K
公開測資點#2 (9%): 1.0s , <1K
公開測資點#3 (9%): 1.0s , <1K
公開測資點#4 (9%): 1.0s , <1M
公開測資點#5 (9%): 1.0s , <1M
公開測資點#6 (9%): 1.0s , <1M
公開測資點#7 (9%): 1.0s , <1M
公開測資點#8 (9%): 1.0s , <1M
公開測資點#9 (9%): 1.0s , <10M
公開測資點#10 (10%): 1.0s , <10M

Hint ：

上例中, ACCGUU 和 CACUAA 都出現了 1 次, 而 ACACAC 則出現了 3 次。你可以見到, 這裏只要求基本基因組出現的次數, 它們每次出現是可能有重叠的地方。如第二和第三個基本基因出現的地方就有部份是互相重叠的。而第三個基因組自己出現的地方就有重叠之處。

Tags:

出處:

[管理者：

ricky (電腦黃)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」