はじめに

今回からはコンテストの全ての問題を振り返るのではなく、学びがありそうな問題を一個ずつ取り上げようと思います。そうじゃないと書き終わらなそうなので...

E Who Says a Pun

この問題は一応コンテスト中に解けたのですが、色々な別解があり学びが多そうなので取り上げます。

問題概要

与えられた文字列Sについて、重ならずに二度以上現れる連続する部分文字列のうち、最長のものの長さを求めよ
制約: |S|<10**3

解説

解法1 DP?

まずは僕が実際にコンテストで書いた解法から説明していきます。
dp[i]をSの0~i文字目までのみからなる文字列における答えとします。それを更新することで最終的な答えをだすという方針です。
では、どのように更新していくかですが、もし、dp[i+1]>dp[i]であるなら、問題文の性質を満たす最長の部分列はS[i+1]を含むということがわかります。このことから、dp[i+1]<=dp[i]+1であることもわかります。よって今考えるべきことは、S[i+1]までの長さdp[i]+1の部分文字列が、Sの0~i-dp[i]-1にも含まれているかということです。この辺はよくわからなかったので、pythonの文字列検索に頼りました。色々ググったところ、文字列の検索はO(n)くらいっぽいので、全体としてはO(N**2）となり、十分高速だろうと思いました。結果はPypy3で約1200msでした

N = int(input())
S = input()
ans = 0
for i in range(N):
    if N-i<ans:
        break
    if S[i+1:].find(S[i-ans:i+1])>=0:
        ans += 1
print(ans)

解法2 DP

dp[i][j] = i, jから始まる、等しい部分文字列の最長の長さ
とおく。もし、S[i]=S[j]なら、dp[i][j] = dp[i+1][j+1]+1となり、そうでなければ0となる。全体の計算量はO(N**2)。エレガントですね。

N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
for i in reversed(range(N)):
    for j in reversed(range(N)):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(N):
    for j in range(i, N):
        ans = max(min(dp[i][j], j-i), ans)
print(ans)

最後のmaxを求める部分をmax( for i in range(N))みたいなので１行で書いたらTLEしました。理由は不明

解法3 Z-algorithm

Z-algorithm

名前がかっこいいですね。Z-algorithmとは各iについてSとS[i:]の最長共通接頭辞(LCP)を求めるアルゴリズムです。あらかじめわかっている結果をうまく利用することでO(n)で求めることができます。

def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP

参考

問題への応用

さて、上のようにして求めたLCPをこの問題に応用してみましょう。これは簡単で、各iについて上のSをS[i]に置き換えて実行すれば全てのS[i:], S[:j]の組の最長接頭辞が求められます。Z-algorithmはO(n)なので全体としてはO(n**2)となります。

ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

解法４　ローリングハッシュ

いわゆるロリハとかいうやつです。

ローリングハッシュ

ハッシュとは文字列などに対し、元データを要約した数値のことです。アルファベット小文字の長さNの文字列の組み合わせは、26**Nあり、それを2**64ほどの数値に落とし込むので、ハッシュの衝突ということも起こるらしいです。
ハッシュは、普通にやれば、文字列の長さに比例した時間がかかります。ローリングハッシュは、ある文字列の連続した部分文字列に関して、一気にハッシュをとりたいときに、以前計算したものを使いまわすことで、高速に求められるようにするアルゴリズムです。ローリングハッシュでは以下のような関数で文字列を変換します。
$f(S) = S[0]*b^{(n-1)}+S[1]*b^{(n-2)}+\cdots+S[n-1]*b^0 \bmod m$
bとmは任意で、S[i]は文字列のi文字目を適当に数値に変換したものです。このようにハッシュ関数を設定すると、f(S[p:q])を用いて、$f([p:q+1]) = f([p:q])+S[q]*b^{(n-q)}\mod m$
$f([p+1:q]) = (f([p:q])-S[p]*b^{(n-p)})*b+S[q]*b^{(n-q)}\bmod m$
などのように計算でき、iから始まる連続した部分列のハッシュや長さmの部分文字列のハッシュなどがO(n)で計算できます。上の式は結構適当なので間違ってたらごめんなさい。

mod#大きい素数
base#適当な数
rolling_hash = [0]*(n+1)#S[:i]のハッシュ
power#power[i] = base^iの配列
for i, s in enumerate(S):
    rolling_hash[i+1] = rolling_hash[i]+s*power[n-i]%mod

この問題への応用

この問題では、もし、条件を満たす長さn+1の部分文字列が存在するなら、条件を満たすような長さnの部分文字列が存在するという、単調性が存在します。よって、二分探索が使えます。ローリングハッシュによって、長さmの部分文字列のハッシュは効率的に求められるので、条件判定はO(n)程度で行えるため、全体ではO(nlogn)くらいとなり、十分高速です。

import numpy as np
N = int(input())
S = list(map(ord, list(input())))
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    if N-m<m:
        return False
    res = 0
    for i in range(m):
        res+=S[i]*power[m-i-1]
        res%=mod
    dic = {res:0}
    for i in range(N-m):
        res = ((res-S[i]*power[m-1])*base
                             +S[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

余談ですがpypyだと辞書はクソみたいに遅くてTLEします(Pythonでは55ms)
追記:defaultdictだとpypyで220msになりました

実はこんな面倒なことをしなくても、そのまま辞書にぶち込めばO(n**2logn)ですが、定数倍が早く余裕で間に合います。

N = int(input())
S = input()
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    dic = {}
    for i in range(N-m+1):
        s = S[i:i+m]
        if s in dic.keys():
            if dic[s]+m<=i:
                return True
        else:
            dic[s] = i
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

おまけ　suffix array

suffix arrayとかいうのを使っても解けるらしいですが、理解不能でした。

まとめ

今回は文字列に関するアルゴリズムとしてZ-algorithm, ローリングハッシュを取り上げましたが、それ以前に、単調性→二分探索に気づけるのが大事ですね。