はじめに
今回からはコンテストの全ての問題を振り返るのではなく、学びがありそうな問題を一個ずつ取り上げようと思います。そうじゃないと書き終わらなそうなので...
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, ローリングハッシュを取り上げましたが、それ以前に、単調性→二分探索に気づけるのが大事ですね。