222 . 帥哥總召出任務
TopCoder
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$ 個字串 $s_1, s_2, \cdots, s_N$ ，對於一個字串 $p$ 來說，定義這個字串的美麗度的值為滿足條件的二元組 $(k, i)$ 的數量。
一個二元組 $(k, i)$ 滿足條件若且惟若字串 $s_i$ 的前 $k$ 個字元與字串 $p$ 的前 $k$ 個字元拼起來是回文字串，即 $s_{i_0} s_{i_1} s_{i_2} \cdots s_{i_{k - 2}} s_{i_{k - 1}} p_0 p_1 p_2 \cdots p_{k - 2} p_{k - 1}$ 是回文字串。
接著給出一個長度限制 $L$，請算出對於所有每個可能的 $x$ 滿足 $1 \le x \le L$ ，一個長度為 $x$ 的未知字串 $p$ 最大可能的美麗度是多少？
Input Format
測試資料第一行包含兩個正整數 $N, L$ ，代表對應到題目所說的一共有 $N$ 個字串與長度限制 $L$。
接下來一共有 $N$ 行，每行會有一個字串分別代表 $s_1, s_2, \cdots, s_N$。
- $1 \le N \le 10^ 5$
- $1 \le L \le 10^ 5$
- $\sum \lvert s_i \rvert \le 10^ 5$
- 所有字串都由小寫字母組成
Output Format
請一共輸出 $L$ 個數字，代表未知字串 $p$ 在長度為 $1, 2, 3, \cdots, L$ 的限制底下最大可能的美麗度。
Sample Input 1
aaaaa
Sample Output 1
Hints
Problem Source
IOICamp 2021 Day4 pF
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~32 | 無額外限制 | 100 |