ABC141 E - Who Says a Pun?

問題原文

atcoder.jp

問題要旨

長さ の文字列 が与えられる。
の連続する部分文字列であって、２回以上出現しているもの（ただしそれらの区間は重なりあってはいけない）ものの、最大の長さを求めよ。

• 

解法１：Z-algorithmで殴る

Z-algorithm を使って、 の最長共通接頭辞列をそれぞれ求めて、判定する。
区間が重なっているものをカウントしないように注意。

実装

N = int(input())
S = input()

ans = 0
for i in range(N):
    X = S[i:]
    Z = z_algorithm(X)

    for j, z in enumerate(Z):
        if j >= z:
            ans = max(ans, z)

print(ans)

解法２：二分探索

答えには明らかに単調性がある（abcd が条件を満たすとき、明らかに abc も条件を満たす）ので、二分探索が使える。
判定においては、「ある連続する部分文字列を候補に詰めた後、次の連続する部分文字列が候補の中にあるかチェック」 という感じでやれば、高速かついい感じに区間の重複も考慮しながら判定できる。

実装

N = int(input())
S = input()
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    check = set()
    for i in range(N - x + 1):
        check.add(S[i: i + x])
        if S[i + x: i + 2 * x] in check:
            ok = x
            break
    else:
        ng = x

print(ok)

感想

にぶたん解の判定部の実装はいろんな場面で使えそう。
あと Z-algorithm つよいですね。