TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

今天帥哥總召要出任務,以下是他詢問大家對字串的看法:

小 A 說:在我看來學會 AC 自動機就夠了,名字有 AC 到處都 AC!

小 S 說:真的嗎?聽說 Suffix array 可以解決 70% 的字串題欸?不需要會其他的吧?不然字串也太難了,哪那麼雖?

小 O 說:不會啊,字串很簡單啊。 KMP 就是在討論前綴跟前綴的後綴的關係、 Z value 就是在討論前綴跟後綴的前綴的關係、Manacher's algorithm 就是在討論子字串的子字串跟回文的關係!

小 W 說:有道理,所以題目裡出現兩次前綴和一次後綴就用 KMP ,出現回文就用 Manacher's algorithm!

小 M 說:在我看來大家都忽略了一個最強的算法,不管甚麼題目用 Trie 直接 Trie Trie 看就會過了!

小 T 說:也不用那麼麻煩,看到題目直接迴圈掃過去就可以了,反正輸入的字串長度都是有限大,通通都是常數!

小 C 說:現在的題目怎麼都那麼難懂,要是直接告訴我要怎麼做就好了!

帥哥總召要回答的任務如下:

現在一共有 N 個字串 s1,s2,,sN ,對於一個字串 p 來說,定義這個字串的美麗度的值為滿足條件的二元組 (k,i) 的數量。

一個二元組 (k,i) 滿足條件若且惟若字串 si 的前 k 個字元與字串 p 的前 k 個字元拼起來是回文字串,即 si0si1si2sik2sik1p0p1p2pk2pk1 是回文字串。

接著給出一個長度限制 L,請算出對於所有每個可能的 x 滿足 1xL ,一個長度為 x 的未知字串 p 最大可能的美麗度是多少?

Input Format

測試資料第一行包含兩個正整數 N,L ,代表對應到題目所說的一共有 N 個字串與長度限制 L

接下來一共有 N 行,每行會有一個字串分別代表 s1,s2,,sN

  • 1N105
  • 1L105
  • |si|105
  • 所有字串都由小寫字母組成

Output Format

請一共輸出 L 個數字,代表未知字串 p 在長度為 1,2,3,,L 的限制底下最大可能的美麗度。

Sample Input 1

1 6
aaaaa

Sample Output 1

1 2 3 4 5 5

Hints

Problem Source

IOICamp 2021 Day4 pF

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~32 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2