11855 Buzzwords
コンテストに参加してたりなんだり.全然できないけど,問題だけでも読むようにはしてる.
問題
ある文字列が与えられて,その文字列の部分文字列の現れる頻度を数える.出力は文字の長さが1,2,3,4...である部分文字列で頻度が最大のものの長さをそれぞれ表示(ただし,頻度が2回以上のやつだけ).
たとえば,"ABCBCC"なら,長さ1の"C"が3回,長さ2の"BC"が2回なので,出力は3,2.
考え方
最初はTrie木で頻度を数えてみたけど,実装の問題か,木を作るのに時間がかかりすぎてTLE.
すべての部分文字列についてhashを計算してhash tableに入れながら数えた.hash tableの用意しておくサイズの決め方がいまいちわからなくて適当に早そうなサイズにした.map使ったらなんか遅かった.
反省
1位の人のコードが異常に早いけど,もっと早いやりかたあるようだから調べよう.