Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
# who says a pun?

# 今日の精進問題第三問目ｎ

n = int(input())
s = list(input())
# dp[L][K]=一番目は左からL番目、二番目は左からK番目からスタートするとした時の共通文字列の中で長さが最大のもの
dp = [[0 for i in range(n + 2)] for j in range(n + 2)]
# もしi>=jであるならば答えは当然ゼロ
# 0<i<jである時だけで考える
for j in range(n, 1, -1):
    # j=n,n-1,,,,,,,,2の値をとる
    for i in range(1, j):

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

if n % 2 == 0:
    len_max = int((n - 1) / 2)
else:
    len_max = int(n / 2)

for i in range(len_max, 0, -1):
    for j in range(0, n - i + 1):
        t = s[j:j + i + 1]
        if t in s[j + i + 1:]:
            print(len(t))
            exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in reversed(range(N)):
    for j in reversed(range(i+1, N)):
        if S[i] != S[j]:
            dp[i][j] = 0
        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+1, N):
        now = min([dp[i][j], j-i])
        ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in reversed(range(N)):
    for j in reversed(range(N)):
        if i >= j:
            continue
        if S[i] != S[j]:
            dp[i][j] = 0
        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(N):
        now = min([dp[i][j], j-i])
        ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    s = input()
    
    def lcs(x,y):
        lx,ly = len(x),len(y)
        dp = [[0 for _ in range(ly+1)] for _ in range(lx+1)]
        for i in range(lx):
            for j in range(ly):
                if x[i] == y[j]:
                    p = 1
                else:
                    p = 0
                dp[i+1][j+1] = max(dp[i][j]+p,dp[i][j+1],dp[i+1][j])
        return dp[-1][-1]
    
    print(max(lcs(s[:i],s[i:]) for i in range(N)))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

l = len(s)

dp = [[0] * (l + 1) for _ in range(l + 1)]
dp[0][0] = 1

ans = 0
for i, ei in enumerate(s, 1):
    for j, ej in enumerate(s[i:], i+1):
        if ei == ej:
            dp[i][j] = min(dp[i-1][j-1] + 1, j - i)
            ans = max(ans, dp[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#141_E
n = int(input())
s = input()

ans = 0
for l in range(1, n // 2 + 1):
    for i in range(0, n - 2 * l + 1):
        for j in range(i + l, n - l + 1):
            if s[i: i + l] == s[j: j + l]:
                ans = max(ans, l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

N = int(input())
S = input()
MAX = 0

for i in range(N-1):
    A = z_algo(S[i:])
    for j in range(len(A)):
        if MAX < A[j] and A[j] <= j:
            MAX = A[j]

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def main():
    n=int(input())
    s=RollingHash(input())
    for i in range(1,n):
        d={}
        for j in range(0,n-i+1):
            k=s.get(j,j+i)
            if k in d:
                if d[k]+i<=j:
                    break
            else:
                d[k]=j
        else:
            print(i-1)
            break
main()

Submission status: Time Limit Exceeded

Solution code:
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        self.f=f=[1]*(n+1)
        self.h=h=[0]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=f[i]*b%M
            h[i+1]=(h[i]*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
n=int(input())
s=RollingHash(input())
for i in range(1,n):
    d={}
    for j in range(0,n-i+1):
        k=s.get(j,j+i)
        if k in d:
            if d[k]+i<=j:
                break
        else:
            d[k]=j
    else:
        print(i-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

n = int(input())
s = str(input())

dq_s = deque([])
for x in s:
    dq_s.append(x)

dq_s_shift = copy.deepcopy(dq_s)

ans = 0

for i in range(n):
    dq_s_shift.appendleft('_')
    count = 0
    # print(s)
    # print(s_shift)

    for j in range(n):
        if dq_s[j] == dq_s_shift[j]:
            count += 1
        else:
            count = 0
        if count >= ans and count <= i+1:
            ans = count
    # print('-'*30)
    # print(ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(input())
s_shift = s
ans = 0

for i in range(n):
    s_shift = '_' + s_shift
    count = 0
    # print(s)
    # print(s_shift)

    for j in range(n):
        if s[j] == s_shift[j]:
            count += 1
        else:
            count = 0
        if count >= ans and count <= i+1:
            ans = count
    # print('-'*30)
    # print(ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
s = input().rstrip()

strings = [[] for _ in range(n // 2 + 1)]

for i in range(n):
    string = [s[i]]
    strings[1].append(s[i])
    for j in range(i + 1, n):
        string.append(s[j])
        if j - i + 1 < 1 + n // 2:
            strings[j - i + 1].append("".join(string))

ans = 0

for i in range(n // 2, 0, -1):
    check = strings[i]
    for j in range(len(check)):
        check_set = set(check[j + i:])
        if check[j] in check_set:
            print(i)
            sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
s = input().rstrip()

strings = [[] for _ in range(n // 2 + 1)]

for i in range(n):
    string = [s[i]]
    strings[1].append(s[i])
    for j in range(i + 1, n):
        string.append(s[j])
        if j - i + 1 < 1 + n // 2:
            strings[j - i + 1].append("".join(string))

ans = 0

for i in range(n // 2, 0, -1):
    check = strings[i]
    for j in range(len(check)):
        if check[j] in check[j + i:]:
            print(i)
            sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
BASE = 9973
MOD = 2 ** 61 - 1


class RollingHash:
    # 文字列Sのローリングハッシュを構築
    # 計算量: O(N)
    def __init__(self, S):
        # acc[i]はS[0:i]のハッシュ値となる
        self.acc = [0]
        a = 0
        # 累積和を計算するイメージ
        for i, c in enumerate(S):
            h = ord(c) - ord("a") + 1
            offset = pow(BASE, i, MOD)
            a = (a + (h * offset)) % MOD
            self.acc.append(a)

    # S[i:j]のハッシュ値を返す
    # 計算量: O(1)
    def hash(self, i, j):
        # 累積和を用いて部分区間の和を計算するイメージ
        # 注意: 基数によるオフセットをキャンセルする必要がある
        offset = pow(BASE, i, MOD)
        # 素数MODを法とする剰余類における除算は逆元を乗算することで計算できる
        # 素数MODを法とする剰余類におけるxの逆元はx^(MOD - 2)に等しい
        offset_inv = pow(offset, MOD - 2, MOD)
        return ((self.acc[j] - self.acc[i]) * offset_inv) % MOD


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

# Sのローリングハッシュを計算しておく
rolling = RollingHash(S)

# 長さmのダジャレがSに含まれるならば、長さm-1のダジャレも含まれる
# つまり、長さmのダジャレがSに含まれるならば真となる述語をP(m)とすると、以下を満たす整数cが存在する:
#   - 0以上c以下の整数mについてP(m)は真
#   - cより大きい整数mについてP(m)は偽
# ※ Pは単調関数ということ
# このcを二分探索で発見すれば高速化できる！

# P(ok)は真
ok = 0
# P(ng)は偽
ng = N
while ng - ok > 1:
    # 区間[ok, ng)の中央値をmとする
    m = (ok + ng) // 2

    # 長さmのダジャレが存在するか判定する
    # 長さmのformerのハッシュ値のキャッシュ
    former_cache = set()
    p = False
    # latterに着目してループを回す
    for i in range(m, N):
        # ダジャレ長を決め打ちしているのでjを直接計算できる
        j = i + m
        # S[i:j]がSをはみ出したらループ終了
        if j > N:
            break
        # formerのハッシュ値をキャッシュする
        former_cache.add(rolling.hash(i - m, i))
        # キャッシャに同一のハッシュ値が存在する場合（ハッシュ値が衝突した場合）、ダジャレになっていると判定できる
        if rolling.hash(i, j) in former_cache:
            p = True
        # ハッシュ値の計算、キャッシュ存在判定は共にO(1)で処理できる！
    # 区間[ok, ng) を更新
    if p:
        ok = m
    else:
        ng = m
# whileループを抜けると区間[ok, ng)は[c, c + 1) になっている
ans = ok

print(ans)

Submission status: Time Limit Exceeded

Solution code:
BASE = 9973
MOD = 2 ** 61 - 1


class RollingHash:
    # 文字列Sのローリングハッシュを構築
    # 計算量: O(N)
    def __init__(self, S):
        # acc[i]はS[0:i]のハッシュ値となる
        self.acc = [0]
        a = 0
        # 累積和を計算するイメージ
        for i, c in enumerate(S):
            h = ord(c) - ord("a") + 1
            a += h * pow(BASE, i, MOD)
            self.acc.append(a)

    # S[i:j]のハッシュ値を返す
    # 計算量: O(1)
    def hash(self, i, j):
        # 累積和を用いて部分区間の和を計算するイメージ
        # 注意: 基数によるオフセットをキャンセルする必要がある
        offset = pow(BASE, i, MOD)
        # 素数MODを法とする剰余類における除算は逆元を乗算することで計算できる
        # 素数MODを法とする剰余類におけるxの逆元はx^(MOD - 2)に等しい
        offset_inv = pow(offset, MOD - 2, MOD)
        return ((self.acc[j] - self.acc[i]) * offset_inv) % MOD


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

# Sのローリングハッシュを計算しておく
rolling = RollingHash(S)

# 長さmのダジャレがSに含まれるならば、長さm-1のダジャレも含まれる
# つまり、長さmのダジャレがSに含まれるならば真となる述語をP(m)とすると、以下を満たす整数cが存在する:
#   - 0以上c以下の整数mについてP(m)は真
#   - cより大きい整数mについてP(m)は偽
# ※ Pは単調関数ということ
# このcを二分探索で発見すれば高速化できる！

# P(ok)は真
ok = 0
# P(ng)は偽
ng = N
while ng - ok > 1:
    # 区間[ok, ng)の中央値をmとする
    m = (ok + ng) // 2

    # 長さmのダジャレが存在するか判定する
    # 長さmのformerのハッシュ値のキャッシュ
    former_cache = set()
    p = False
    # latterに着目してループを回す
    for i in range(m, N):
        # ダジャレ長を決め打ちしているのでjを直接計算できる
        j = i + m
        # S[i:j]がSをはみ出したらループ終了
        if j > N:
            break
        # formerのハッシュ値をキャッシュする
        former_cache.add(rolling.hash(i - m, i))
        # キャッシャに同一のハッシュ値が存在する場合（ハッシュ値が衝突した場合）、ダジャレになっていると判定できる
        if rolling.hash(i, j) in former_cache:
            p = True
        # ハッシュ値の計算、キャッシュ存在判定は共にO(1)で処理できる！
    # 区間[ok, ng) を更新
    if p:
        ok = m
    else:
        ng = m
# whileループを抜けると区間[ok, ng)は[c, c + 1) になっている
ans = ok

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ls = len(s)

ans = 0
for i in range(1, n):
    #print(s[:i], s[i:], i, ls-i)
    a, b = s[:i], s[i:]
    la, lb = i, ls - i
    dp = [[0] * (la+1) for _ in range(lb+1)]
    for j in range(la):
        for k in range(lb):
            if a[j] == b[k]:
                dp[k+1][j+1] = dp[k][j] + 1
    #print(dp[lb][la])
    ans = max(ans, dp[lb][la])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

def lcs(s, t):
    ls, lt = len(s), len(t)
    dp = [[0] * (lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            #prev = dp[i+1][j+1]
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
    return dp[ls][lt]


ans = 0
for i in range(1, len(s)):
    l = lcs(s[:i], s[i:])
    ans = max(ans, l)
    #print(l, s[:i], s[i:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline   
sys.setrecursionlimit(100000000)
from functools import lru_cache
INF = 1000000000
MOD = 10**9+7

def main():
    n=int(input())
    s=input()

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

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
class RollingHash:
    # Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
    def __init__(self, seq, base=10 ** 9 + 7, mod=2 ** 89 - 1):
        """
        :param str|typing.Sequence[int] seq:
        :param int base:
        :param int mod:
        """
        if isinstance(seq, str):
            self._seq = seq = list(map(ord, seq))
        else:
            self._seq = seq
        self._base = base
        self._mod = mod

        hashes = [0] * (len(seq) + 1)
        power = [1] * (len(seq) + 1)
        for i, c in enumerate(seq):
            hashes[i + 1] = (hashes[i] * base + c) % mod
            power[i + 1] = power[i] * base % mod
        self._hashes = hashes
        self._power = power

    def get(self, L, r):
        """
        [L, r) のハッシュ値を取得します
        :param int L:
        :param int r:
        """
        if L >= r:
            return 0
        return (self._hashes[r] - self._hashes[L] * self._power[r - L]) % self._mod

    def lcp(self, p, q, allow_overlap=False):
        """
        seq[p:] と seq[q:] の Longest Common Prefix
        O(logN)
        :param int p:
        :param int q:
        :param bool allow_overlap:
        """
        lim = min(len(self._seq) - p, len(self._seq) - q)
        if not allow_overlap:
            lim = min(lim, abs(p - q))

        ok = 0
        ng = lim + 1
        while abs(ng - ok) > 1:
            sz = (ok + ng) // 2
            if self.get(p, p + sz) == self.get(q, q + sz):
                ok = sz
            else:
                ng = sz
        return ok


N = int(sys.stdin.buffer.readline())
S = sys.stdin.buffer.readline().decode().rstrip()
rh = RollingHash(S)

ans = 0
for i, j in itertools.combinations(range(N), 2):
    ans = max(ans, rh.lcp(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0
    for i in range(1, n):
        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

def main():
    n = int(input())
    s = input().rstrip()
    ans = 0
    for i in range(n):
        lcp = Z_algo(s[i:])
        for j, l in enumerate(lcp):
            x = min(l, j)
            ans = max(ans, x)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input().rstrip()
    sets_l = [set() for _ in range(n)]
    sets_r = [set() for _ in range(n)]
    sets_l[0].add(s[0])
    for i in range(1, len(s)):
        #sets_l[i] = sets_l[i] | sets_l[i-1]
        for j in range(i+1):
            sets_l[i].add(s[j:i+1])
    sets_r[n-1].add(s[n-1:])
    for i in reversed(range(len(s)-1)):
        sets_r[i] = sets_r[i] | sets_r[i+1]
        for j in reversed(range(i, len(s))):
            sets_r[i].add(s[i:j+1])
    ans = 0
    for i in range(i, len(s)-1):
        for v in sets_l[i]:
            if v in sets_r[i+1]:
                if ans < len(v):
                    ans = len(v)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input().rstrip()
    sets_l = [set() for _ in range(n)]
    sets_r = [set() for _ in range(n)]
    sets_l[0].add(s[0])
    for i in range(1, len(s)):
        sets_l[i] = sets_l[i] | sets_l[i-1]
        for j in range(i+1):
            sets_l[i].add(s[j:i+1])
    sets_r[n-1].add(s[n-1:])
    for i in reversed(range(len(s)-1)):
        sets_r[i] = sets_r[i] | sets_r[i+1]
        for j in reversed(range(i, len(s))):
            sets_r[i].add(s[i:j+1])
    ans = 0
    for i in range(i, len(s)-1):
        for v in sets_l[i]:
            if v in sets_r[i+1]:
                if ans < len(v):
                    ans = len(v)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict(int)
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
				break
		else:
			dc[x] = i+j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict
from itertools import accumulate
n = int(input())
s = input()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(n//2,0,-1):
	dc = defaultdict(int)
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
				break
		else:
			dc[x] = i+j
	else:
		continue
	break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict
from itertools import accumulate
n = int(input())
s = input()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict(int)
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
				break
		else:
			dc[x] = i+j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict
from itertools import accumulate
n = int(input())
s = input()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict((int))
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
				break
		else:
			dc[x] = i+j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict
from itertools import accumulate
n = int(input())
s = input()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict((int))
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
		else:
			dc[x] = i+j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    s = input()
    dp = np.zeros((N+1,N+1),dtype=int)
    for i in range(N):
        for j in range(i+1,N):
            if s[i] == s[j]:
                dp[i+1][j+1] = min(dp[i][j]+1,j-i)

    print(dp.max())

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    s = input()
    dp = np.zeros((N+1,N+1),dtype=int)
    for i in range(N):
        for j in range(1,N):
            if s[i] == s[j]:
                dp[i+1][j+1] = min(dp[i][j]+1,j-i)
    
    print(np.max(dp))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
for i in range(n-1):
  for j in range(i+1,n):
    for k in range(min(n-j,j-i)):
      if s[i+k] != s[j+k]:
        k -= 1
        break
    ans = max(ans,k+1)     
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import hashlib

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


objects = []
l = [[] for i in range(n//2+1)]


for i in range(n):
    objects.append(hashlib.md5())


for size in range(1, n//2+1):
    for i in range(n - size + 1):
        h = objects[i]
        h.update(s[i].encode())
        l[size].append(h.hexdigest())


def output():
    left, right = 0, n//2+1
    while left < right-1:
        mid = (left+right)//2
        if check(l[mid]):
            left = mid
        else:
            right = mid
    return left


def check(li):
        hashes = set()
        for h in li:
            if h in hashes:
                return True
            hashes.add(h)
        return False


print(output())

Submission status: Time Limit Exceeded

Solution code:
import hashlib

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


objects = []
l = [[] for i in range(n//2+1)]


for i in range(n):
    objects.append(hashlib.md5())


for size in range(1, n//2+1):
    for i in range(n - size + 1):
        h = objects[i]
        h.update(s[i].encode())
        l[size].append(h.hexdigest())


def output():
    for size, li in zip(reversed(range(n//2+1)), reversed(l)):
        hashes = set()
        for h in li:
            if h in hashes:
                return size
            hashes.add(h)

    return 0

print(output())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

def compare(x0, x1):
    old_x1 = x1
    while x1 < n and s[x0] == s[x1] and x0 < old_x1:
        x0 += 1
        x1 += 1
    return x1-old_x1


m = 0
for i0 in range(n):
    for i1 in range(i0+1, n):
        m = max(compare(i0, i1), m)

print(m)

Submission status: Time Limit Exceeded

Solution code:
# 長さNの文字列Sについて、i=2,3,...,N でのSのi文字目以降から成る文字列とSの最長共通接頭辞の長さ 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
  
N = int(input())
S = input()

ans = 0
for i in range(N):
  SS = S[i:]
  lcp = z_algo(SS)
  for j in range(len(lcp)):
    l = min(lcp[j], j)
    ans = max(ans, l)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 長さNの文字列Sについて、i=2,3,...,N でのSのi文字目以降から成る文字列とSの最長共通接頭辞の長さ O(N) 
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
  
N = int(input())
S = input()

ans = 0
for i in range(N):
  SS = S[i:]
  lcp = z_algo(SS)
  for j in range(len(lcp)):
    l = min(lcp[j], j)
    ans = max(ans, l)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

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

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    # https://tjkendev.github.io/procon-library/python/string/z-algorithm.html
    def z_algo(S):
        N = len(S)
        A = [0] * N
        i = 1; j = 0
        A[0] = l = len(S)
        while i < l:
            while i + j < l and S[j] == S[i + j]:
                j += 1
            if not j:
                i += 1
                continue
            A[i] = j
            k = 1
            while l - i > k < j - A[k]:
                A[i + k] = A[k]
                k += 1
            i += k; j -= k
        return A
    N = I()
    S = SI()
    ans = 0
    for i in range(N):
        Z = z_algo(S[i:])
        for k,n in enumerate(Z[1:]):
            cur = min(k+1,n)
            ans = max(ans,cur)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
def condition(num):
    if num==0:
        return True
    else:
        flag=0
        data=[]
        for i in range(0,N-num+1):
            data.append(S[i:i+num])
        for i in range(0,len(data)-1):
            for j in range(i+num,N-num+1):
                if data[i]==data[j]:
                    flag=1
        return flag==1

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def z_algorithm(S):
    n = len(S)
    A = [0] * n
    A[0] = n
    L = 0
    R = 0
    # 過去にS[R]まで調べたとする
    for i in range(1, n):
        if R <= i:
            L = R = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
        elif A[i - L] < R - i:
            A[i] = A[i - L]
        else:
            L = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
    return A


def main():
    N = int(input())
    S = input()
    answer = 0
    for i in range(1, N - 1):
        a = np.array(z_algorithm(S[i:]), np.int64)
        arange = np.arange(N - i)
        cnt = np.minimum(arange, a)
        cnt = cnt[1:].max()
        if cnt > answer:
            answer = cnt

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


def main():
    N = int(input())
    S = input()
    l = len(S)
    answer = 0
    for i in range(1, N - 1):
        a = z_algorithm(S[i:])
        for j in range(1, l - i):
            cnt = min(j, a[j])
            if cnt > answer:
                answer = cnt

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
ans=0
partlist=[[] for i in range(0,N+1)]
for j in range(0,N-1):
    if S[j]==S[j+1]:
        ans=1
for i in range(2,N):
    x=S[0]
    for j in range(1,i):
        x+=S[j]
    partlist[i].append([x,0])
    for j in range(0,N-i):
        x=x[1:i]+S[j+i]
        partlist[i].append([x,j+1])
    partlist[i].sort()
    for j in range(0,len(partlist[i])-1):
        if partlist[i][j][0]==partlist[i][j+1][0] and partlist[i][j][1]+i-1<partlist[i][j+1][1]:
            if i>ans:
                ans=i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
s=input()
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    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
ans=0
for i in range(n):
    lcp=Z_algo(s[i:])
    for j in range(len(lcp)):
        tmp=min(j,lcp[j])
        ans=max(ans,tmp)
print(ans)