2/14 PKU

Algorithm PKU

3261 Milk Patterns

N個の整数からなる数列がある。数列にK回以上現れる連続したパターンのうち最長のものの長さを求めよ。

suffix array と lcp を求めると、lcp中において「K-1個の連続した部分の最小値」の最大値が答えになる。

1743 Musical Theme

ある音楽のメロディが与えられる。メロディの中で「テーマ」を次のように定める。

  • 長さが5以上
  • メロディ中に2回以上現れ、重なっていない(但し、転調されてても可)

最長の「テーマ」の長さを求めよ。

メロディの隣りあう項の差を取ると(階差と呼ぶことにする)、長さD以上のテーマが存在するならば、階差において先頭がD以上離れている長さD-1の共通部分が存在する。
suffix array と lcp を求めた後、二分探索をする