ABC 141 E - Who says a pun? - ゆきくらげのブログ

初学者につき注意。

問題

長さNの文字列Sが与えられ、
Sの連続する部分文字列として重ならずに2回以上現れるもののうち、最長のものを求めよ

例)strangeorange→5
range、という5文字の文字列が2回出てくる

制約

2≦N≦5×10^3
|S| = N
Sは英小文

考察

最初はdpでやりました(TLEでした)
dp[i][j]を、i文字目までの文字列とj文字目までの文字列が同じになる最長の長さ。
と定義します。
そうすると

もしS[i]==S[j]ならdp[i][j]=min(dp[i-1][j-1],j-i)

(文字列が被っていてはダメなのでj-iとmin関数にかける)

それ以外なら(S[i]!=S[j]なら)dp[i][j]=0

こうしてdp上の値の最大値を返せばいい。
のですが、これは $O(N^{2})$ の計算時間がかかってしまい、kotlinを使うとTLEになってしまいました。
一応自分のコード↓
https://atcoder.jp/contests/abc141/submissions/7570248
そこで解説にあったローリングハッシュ法を使うことに(ググりました)

ローリングハッシュとは？

こちらのブログが非常にわかりやすかったです。著者の方、ありがとうございます。
perogram.hateblo.jp
ロリハのことはまた別の記事にまとめるとします。

さて、この問題の解法ですが、実際の解をbとおきます。そして適当に仮定解aを作ります。
文字列長aであるSの部分文字列のハッシュをロリハを使って次々にTreeSetに投げていきます
そこで重複する要素があったならa<=b、なかったらa>bです。
これを使って二分探索で答えを探ります。

実装

実際は文字列がかぶってはいけないので、TreeSetではなくTreeMapを使って(ハッシュ,インデックス)のペアを追加していくようにしました。

import java.util.*
class RollingHash(val N:Int,val S:String){
  val base = 101L
  val mod = 100000000003L
  val powBase = Array(N){1L}
  init{
    for(i in 1 until N){
      powBase[i] = powBase[i-1]*base%mod
    }
  }
  fun check(len:Int):Boolean{  //文字列長がlenの二回以上出てくる部分文字列があるか
    val T = TreeMap<Long,Int>()
    var hash = 0L
    for(i in 0 until len){
      hash = (hash + S[i].toLong()*powBase[len-i-1])%mod
    }
    T.put(hash,-1)
    for(i in 0 until N-len){
      hash = (hash - S[i].toLong()*powBase[len-1])*base+S[i+len].toLong()
      hash = hash%mod
      hash = if(hash>=0)hash else hash+mod
      if(T.containsKey(hash)){
        if(i-T[hash]!!>=len){
          return true
        }
      }
      else
      {
        T.put(hash,i)
      }
    }
    return false
 }
  fun maxlen():Int{ //二分探索
    var left = 0
    var right = N/2.toInt()+1
    while(right-left>1){
      val len = (right+left)/2.toInt()
      if(check(len))left = len else right = len
    }
    return left
  }
}
fun main(args:Array<String>){
  val rh = RollingHash(readLine()!!.toInt(),readLine()!!)
  println(rh.maxlen())
}

感想

ムズイ