ABC141 E - Who Says a Pun?

atcoder.jp

【問題文】
文字列が与えられて、部分文字列として重ならずに 2 回以上現れるもののうち、最長のもの

【考え方】
Zアルゴリズムで解けるらしいけど、解説動画を見てDPで解いた。
過去に確認した値を用いて計算する。

n=int(input())
s=list(input())

dp=[[0]*n for _ in range(n)]
ans=0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        if s[i]==s[j]:
            if i==n-1:
                dp[i][j]=1
            else:
                dp[i][j]=min(i-j,dp[i+1][j+1]+1)
        else:
            dp[i][j]=0
        ans=max(ans,dp[i][j])
print(ans)