GCJ 2019 Round 1A - Alien Rhyme
codingcompetitions.withgoogle.com
問題文
ある地球外探査で、あなたは宇宙人の詩の形跡を見つけました！
言語学者のチームは、その宇宙人の言語の各単語は1つの位置（文字）にアクセントがあると判断しました。
ある単語の、アクセントがある文字とそれ以降の部分をaccent-suffixと呼びます。
2つの単語のaccent-suffixが等しい場合、それらの単語は韻を踏むと言います。
例えば、PROLとTARPOLの場合、2つの単語のアクセントがOにある場合とLにある場合は韻を踏んでいますが、それ以外では韻を踏んでいません。
あなたは宇宙人の詩の一部であるかもしれないN個の単語のリストを得ました。
残念ながら、あなたはそれぞれの単語のアクセントの位置がわかりません。
あなたはこれらの単語のうち0個以上を捨て、残りの単語にアクセントを割り当て、それらの単語全てをペアにした時に、「ペアどうしは韻を踏んでいるが他の単語とは韻を踏んでいない」ようにできると思っています。
このようにペアを作ることができる最大の単語数を求めてください。
入力
1行目にはテストケースの数 T が与えられ、それ以降の行に T 個のテストケースが与えられます。
各テストケースは N + 1 行からなります。
最初の1行に単語の数 N が与えられます。
残りのN行に単語 W_i が与えられます。
W_i は英大文字からなり、単語は各テストケースの中で互いに異なります。
同じ単語が異なるテストケースでは異なるアクセントを持つ可能性があることに注意してください。
出力
各テストケースについて、x を1から始まるテストケースの番号、 y をテストケースの答えとして、
Case #x: y と改行を出力してください。
制約
1 ≤ T ≤ 100
実行制限時間 : 20秒
メモリ制限 : 1GB
1 ≤ |W_i| ≤ 50
W_i は英大文字からなる
i ≠ j ならば W_i ≠ W_j
小課題
小課題1 (10点)
2 ≤ N ≤ 6
小課題2 (27点)
2 ≤ N ≤ 1000
考察
文字列の後ろ i 文字を高速に比較したい
→ suffix tree : 文字列に何が足されたかで木にする
ローリングハッシュ : 文字列を P 進数と見て大きな数で割った余りを比較する
1度使ったaccent-suffixはもう1度使えない
アクセントを後ろにずらせば使えるようになる
→ できるだけaccent-suffixは長い方がいい
後ろ i 文字が一致するペアを長い方から貪欲に取ればいい
ACコード :
