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:
import sys
sys.setrecursionlimit(10**9)


class RollingHash:

    def __init__(self,string):
        base1 = 1007
        mod1 = 10**9+7

        base2 = 2009
        mod2 = 10**9+9

        self.string = string
        n = len(string)
        hash1 = [0]*(n+1)
        power1 = [1]*(n+1)

        hash2 = [0]*(n+1)
        power2 = [1]*(n+1)
        for i,e in enumerate(string):
            hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
            power1[i+1] = (power1[i]*base1)%mod1
            hash2[i+1] = (hash2[i]*base2 + ord(e))%mod2
            power2[i+1] = (power2[i]*base2)%mod2

        self.hash1 = hash1
        self.power1 = power1
        self.hash2 = hash2
        self.power2 = power2
        self.base1 = base1
        self.mod1 = mod1
        self.base2 = base2
        self.mod2 = mod2

    def calc(self,i,j):
        ans = ((self.hash1[j]-self.hash1[i]*self.power1[j-i]%self.mod1)%self.mod1)*(10**10)
        ans += (self.hash2[j]-self.hash2[i]*self.power2[j-i]%self.mod2)%self.mod2
        return ans

def main():
    N = int(input())
    S = input()

    rh = RollingHash(S)

    seen = set()
    dic = {}

    def add(x,i,j):
        if x in seen:
            dic[x].append(j)
        else:
            dic[x] = [j]
            seen.add(x)


    def is_ok(hash,i,j):
        if not hash in seen: return False
        # print(hash)
        for nx_j in dic[hash]:
            if nx_j < i:
                return True


    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            hash = rh.calc(i,j)
            if is_ok(hash,i,j):
                ans = max(ans, j-i+1)

            add(hash,i,j)

    print(ans)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    S = input()


    dict = {}
    seen = set()

    def count(val,x,y):
        if val in seen:
            dict[val].append((x,y))
        else:
            dict[val] = [(x,y)]
            seen.add(val)

    for i in range(N):
        for j in range(N-i):
            count(S[i:i+j+1],i,i+j)

    # print(dict,seen)
    ans = 0
    for s in seen:
        poss = dict[s]
        if not len(poss) > 1: continue

        poss.sort()
        pre_pos = poss.pop()
        while len(poss) > 0:
            pos = poss.pop()
            if pos[1] < pre_pos[0]:
                # print("s",s,pos[1]-pos[0]+1)
                ans = max(ans,pos[1]-pos[0]+1)

            pre_pos = pos


    print(ans)






if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

def LCS(s,t):
    ret = ''
    ls,lt = len(s), len(t)
    
    # dp[i][j] : s_i, t_iでのLCS
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            if s[i]==t[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    
    if dp[ls][lt]==0:
        return ret
    i,j = ls, lt
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            ret += s[i-1]
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
    return ret[::-1]

n = int(input())
S = input()
ans = 0
for i in range(1, n//2 + 2):
    s = S[:i]
    t = S[i:]
    ans = max(ans, len(LCS(s,t)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def LCS(s,t):
    ret = ''
    ls,lt = len(s), len(t)
    
    # dp[i][j] : s_i, t_iでのLCS
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            if s[i]==t[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    
    if dp[ls][lt]==0:
        return ret
    i,j = ls, lt
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            ret += s[i-1]
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
    return ret[::-1]

n = int(input())
S = input()
ans = 0
for i in range(1, n):
    s = S[:i]
    t = S[i:]
    ans = max(ans, len(LCS(s,t)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r): #S[l:r]indexでいうl文字目からr-1文字目
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
      
N =int(input())
S = str(input())

base1 = 1007
mod1 = 10**9+7

RH = RollingHash(S,base1,mod1)

#print(a,b)
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    low = 0
    high = min(j-i,N-j)+1
    while abs(low-high)>1:
      mid = (low+high)//2
      if RH.get(i,i+mid) != RH.get(j,j+mid):
        high = mid
      else:
        low = mid
    ans = max(ans,low)
    #print(i,j,low)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc141/tasks/abc141_e
# https://www.slideshare.net/hcpc_hokudai/ss-121539419
# これのほうがいいかな？ https://sen-comp.hatenablog.com/entry/2020/01/16/174230

# 結局これが一番わかりやすい https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05

# zアルゴリズムをやるらしい


def z_algorithm(S: str):
    '''SとS[i]の最長共通接頭辞長 Z[i] の配列を返す O(len(S))'''
    Z = [-1] * len(S)  # -1で初期化 (-1が出てきたらおかしい！)
    Z[0] = len(S)
    i = 1  # 現在求めたいZ[i]の位置
    j = 0  # S[i:i+j]の文字列は先頭と一致している
    while i < len(S):
        while (i + j < len(S) and S[j] == S[i + j]):
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue
        k = 1
        while (k < j and k + Z[k] < j):  # ならば再利用可能
            # ∵kからZ[k]後がjより小さいということは同一文字列の終了がjを突き抜けないことが保証されている
            # →Z[k]のほうが必ず早く終了するので値はZ[i+k]の値はZ[k]になる
            Z[i + k] = Z[k]
            k += 1
        i += k  # 次のiはまだ埋まっていないところまで移動
        j -= k  # jも無駄な探索を避けるために移動分だけの幅減少に留める
        # jの働き後半がはみ出すときは確定させないで次の探索で確定できるようにするというだけ
    return Z


N = int(input())
S = input()
# まずzアルゴリズムを任意の開始地点に用いる
# ほしいデータ構造
# S[i:]とS[j:]の最長共通接頭辞長行列 M[i][j]
# これのうち重複していないなかでの最大値が答え。
# つまりmax{M[i][j] | i+M[i][j]<=j}

# i,jはあくまで相対位置なのでMを実際に構成しなくてもiを一つずつずらしてjを調べるということでおk
ans = 0
for i in range(N):  # 開始位置
    Z = z_algorithm(S[i:])
    for j in range(N - i):
        if Z[j] <= j:
            ans = max(ans, Z[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algo(s):
    """https://www.youtube.com/watch?v=f6ct5PQHqM0
    """
    n = len(s)
    ret = [0] * n

    ref_frm, ref_tail = -1, -1  # 一番末尾まで探索したケースの起点と終点
    for frm in range(n):
        cont = max(0, min(ret[frm - ref_frm], ref_tail - frm)) if ~ref_frm else 0

        while (frm + cont < n) and (s[cont] == s[frm + cont]): cont += 1
        ret[frm] = cont
        if ref_tail < frm + cont:
            ref_tail = frm + cont
            ref_frm = frm
    return ret


def main():
    N = int(input())
    S = input()

    ret = 0
    t = ''
    for c in reversed(S):
        # zalgoは[0,i]の比較で
        # 先頭が固定されているので
        # 末尾から文字を増やしていくことで
        # 先頭をSの各文字にしている
        t = c + t
        lcp = z_algo(t)
        for diff, len_ in enumerate(lcp):
            ret = max(ret, min(diff, len_))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def Z(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = c = 0
    # c : 最も末尾側まで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

a = 0
n, s = open(0)
for i in range(int(n)):
    for j, l in enumerate(Z(s[i:])):
        a = max(a, min(l, j))
print(a)

Submission status: Time Limit Exceeded

Solution code:
def z_algo(s: str) -> list:
    """LCP(0,i)のlist"""
    N = len(s)
    ret = [-1] * N
    ret[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and s[j] == s[i + j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret


def main():
    N = int(input())
    S = input()

    ret = 0
    t = ''
    for c in reversed(S):
        t = c + t
        lcp = z_algo(t)
        for diff, len_ in enumerate(lcp):
            ret = max(ret, min(diff, len_))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1,N):
    c = 0
    cc = 0
    for j in range(N-i):
        if S[j] == S[i+j]:
            cc += 1
        else:
            c = max(cc,c)
            cc = 0
    c = max(cc,c)
    c = min(i,c)
    ans = max(ans,c)
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):
        s = S[i:j+1]
        if S[j+1:].find(s) != -1:
            ans = max(ans,len(s))
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
maxi = n // 2
for i in range(maxi, 0, -1):
    dic = {}
    for j in range(n-i+1):
        if s[j:j+i] in dic.keys():
            if dic[s[j:j+i]] < j:
                print(i)
                exit()
        dic[s[j:j+i]] = j+i-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N//2+1):
    C = {}
    x = S[:k]
    C[x]=[0]
    for i in range(1,N-k+1):
        x = x[1:]+S[i+k-1]
        if x not in C:
            C[x]=[]
        C[x].append(i)
    for a in C:
        if len(C[a])>1 and C[a][-1]-C[a][0]>=k:
            cmax = max(cmax,k)
            break
print(cmax)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N//2+1):
    C = {}
    for i in range(N-k+1):
        x = S[i:i+k]
        if x not in C:
            C[x]=[]
        C[x].append(i)
    for a in C:
        if len(C[a])>1 and C[a][-1]-C[a][0]>=k:
            cmax = max(cmax,k)
            break
print(cmax)

Submission status: Time Limit Exceeded

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

ans = 0
maxi = n // 2
for i in range(maxi, 0, -1):
    dic = {}
    for j in range(n-i+1):
        if s[j:j+i] in dic:
            if dic[s[j:j+i]] < j:
                print(i)
                exit()
        dic[s[j:j+i]] = j+i-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N//2+1):
    C = {}
    x = S[:k]
    C[x]=[0]
    for i in range(1,N-k+1):
        x = x[1:]+S[i+k-1]
        if x not in C:
            C[x]=[]
        C[x].append(i)
    flag = 0
    for a in C:
        if len(C[a])>1:
            for j in range(1,len(C[a])):
                if C[a][j]-C[a][j-1]>=k:
                    cmax = max(cmax,k)
                    flag = 1
                    break
            if flag==1:break
print(cmax)

Submission status: Time Limit Exceeded

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

lst = [set([]), set([s[0]])]
ans = 0
for end in range(2, n+1):
    new_set = set([])
    for start in range(end):
        if s[start:end] in lst[start]:
            ans = max(ans, len(s[start:end]))
        new_set.add(s[start:end])
    new_set = new_set | lst[-1]
    lst.append(new_set)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N//2+1):
    C = {}
    for i in range(N-k+1):
        if S[i:i+k] not in C:
            C[S[i:i+k]]=[]
        C[S[i:i+k]].append(i)
    flag = 0
    for a in C:
        if len(C[a])>1:
            for j in range(1,len(C[a])):
                if C[a][j]-C[a][j-1]>=k:
                    cmax = max(cmax,k)
                    flag = 1
                    break
            if flag==1:break
print(cmax)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for k in range(N-1):
    for l in range(k+1,N):
        if S[k] == S[l]:
            temp = 1
            i, j = k+1, l+1
            while i < l and j < N:
                if S[i] == S[j]:
                    temp += 1
                    i += 1
                    j += 1
                else:
                    break
            ans = max(ans,temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

c = collections.Counter()

ans = 0

for i in range(N):
    ss = ""
    for j in range(i, i + (N // 2)):
        if j > N - 1:
            break
        ss += S[j]
        c[ss] += 1
        if c[ss] == 2:
            ans = max(ans, len(ss))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

c = collections.Counter()

for i in range(N):
    ss = S[i]
    for j in range(i + 1, i + 1 + (N // 2)):
        c[ss] += 1
        if j > N - 1:
            break
        ss += S[j]

ans = 0

for k in c.keys():
    if c[k] >= 2:
        ans = max(ans, len(k))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
S = rs()

def get_max(i):
	ok, ng = i, len(S)
	while ng-ok > 1:
		c = (ok+ng)//2
		if S[i:c] in S[c:]:
			ok = c
		else:
			ng = c
	return ok-i

ans = 0
for i in range(N):
	l = get_max(i)
	ans = max(ans, l)
print(ans)

Submission status: Time Limit Exceeded

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

def lcs(s,t):
  a=len(s)
  b=len(t)
  dp=[[0]*(b+1) for i in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        dp[i+1][j+1]=dp[i][j]+1
      else:
        dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
  return dp[-1][-1]

ans=0
for i in range(1,N):
  s=S[:i]
  t=S[i:]
  a=lcs(s,t)
  ans=max(a,ans)
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(n)] for _ in range(n)]
all_patterns = dict()
max_val = 0
for i in range(n):
    for j in range(i,n):
        target = s[i:j+1]
        if target in all_patterns: 
            if len(target) > max_val:
                if i>all_patterns[target][1]:
                    max_val = len(target)
        else:
            all_patterns[target] = [i,j]

print(max_val)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(n)] for _ in range(n)]
all_patterns = dict()
max_val = 0
for i in range(n):
    for j in range(i,n):
        target = s[i:j+1]
        if target in all_patterns and len(target) > max_val and i>all_patterns[target][1]:
            max_val = len(target)
        else:
            all_patterns[target] = [i,j]

print(max_val)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def Zalgo(S):
    N = len(S)
    A = [0]*N

    froms = -1
    lasts = -1
    for i in range(1, N):
        same = 0
        if froms != -1:
            same = min(A[i-froms], lasts-i)
            same = max(0, same)
        while i+same<N and S[same] == S[i+same]:
            same += 1
        
        if i+same > lasts:
            lasts = i+same
            froms = i
        A[i] = same
    A[0] = N
    return A

N = int(input())
S = input().rstrip()

ans = 0
for i in range(N):
    A = Zalgo(S[i:])
    res = 0
    L = len(A)
    for j,a in enumerate(A):
        res = max(res, min(j, a))
    ans = max(res, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from heapq import heappush, heappop
N = int(input())
S = input()

l = []
for a, b in combinations(range(N+1), 2):
    heappush(l, (S[a:b], a, b-1))
ans = 0
ts, ta, tb = "", 0, 0
while len(l) > 0:
    s, a, b = heappop(l)
    if ts == s:
        if tb < a or b < ta:
            ans = max(ans, len(ts))
    else:
        ts, ta, tb = s, a, b

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ss = input().rstrip()

    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if Ss[i] == Ss[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = 0

    ans = 0
    for i in range(N):
        for j in range(N):
            L = j-i if j-i <= dp[i][j] else dp[i][j]
            if L > ans:
                ans = L

    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ss = input().rstrip()

    for L in reversed(range(1, N//2+1)):
        setCand = set()
        RHs = []
        for i in range(N-L+1):
            if i <= N-2*L or L <= i:
                RH = hash(Ss[i:i+L])
            if i <= N-2*L:
                RHs.append(RH)
            if L <= i:
                setCand.add(RHs[i-L])
                if RH in setCand:
                    print(L)
                    break
        else:
            continue
        break
    else:
        print(0)


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ss = input().rstrip()

    for L in reversed(range(1, N//2+1)):
        setCand = set()
        RHs = []
        for i in range(N-L+1):
            RH = hash(Ss[i:i+L])
            RHs.append(RH)
            if i-L >= 0:
                setCand.add(RHs[i-L])
            if RH in setCand:
                print(L)
                break
        else:
            continue
        break
    else:
        print(0)


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    BASE = 10**9 + 7
    MOD = 2**61 - 1  # メルセンヌ素数
    ordA = ord('a')

    N = int(input())
    Ss = input().rstrip()

    As = [ord(S)-ordA for S in Ss]

    def genRollingHash_AllRight(As, lenInit, BASE, MOD):
        hashA = 0
        for A in As[:lenInit]:
            hashA = (hashA*BASE + A) % MOD
        yield hashA

        powB_L = pow(BASE, lenInit, MOD)
        for Aadd, Asub in zip(As[lenInit:], As[:len(As)-lenInit]):
            hashA = (hashA*BASE + Aadd - Asub*powB_L) % MOD
            yield hashA

    for L in reversed(range(1, N//2+1)):
        setCand = set()
        RHs = []
        for i, RH in enumerate(genRollingHash_AllRight(As, L, BASE, MOD)):
            RHs.append(RH)
            if i-L >= 0:
                setCand.add(RHs[i-L])
            if RH in setCand:
                print(L)
                break
        else:
            continue
        break
    else:
        print(0)


solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
dp = [[0]*n for _ in range(n)]
for i in range(n-1, -1, -1):
  for j in range(n-1, -1, -1):
    if i == n-1:
      dp[i][j] = int(S[i] == S[j])
    elif j == n-1:
      dp[i][j] = dp[j][i]
    else:
      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):
    ans = max(ans, min(dp[i][j], j-i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
max = 0
len_str = 0
judge = False
if len(S) == len(set(S)):
  judge = True
else:
  for i in range(len(S)):
    for j in range(i+1, len(S)):
      if 1 < len(S[i:j]) and max < len(S[i:j]) and S.count(S[i:j]) > 1:
        max = len(S[i:j])
print(0 if judge else max)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input().strip())
    S = input().strip()
    low = 0
    high = (N >> 1) + 1
    while high - low > 1:
        mid = (high + low) >> 1
        is_match = False
        m = N-mid-mid+1
        for i in range(0, m):
            if S[i:i+mid] in S[i+mid:]:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


if __name__ == '__main__':
    outputs = solve()
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    low = 0
    high = (N >> 1) + 1
    while high - low > 1:
        mid = (high + low) >> 1
        is_match = False
        m = N-mid-mid+1
        for i in range(0, m):
            if S[i:i+mid] in S[i+mid:]:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict


# CPythonの文字列検索アルゴリズム (BM法) を利用
# http://effbot.org/zone/stringlib.htm


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    low = 0
    high = (N >> 1) + 1
    while high - low > 1:
        mid = (high + low) >> 1
        is_match = False
        m = N-mid-mid+1
        for i in range(0, m):
            if S[i:i+mid] in S[i+mid:]:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    m = 999999937
    b = random.randint(10000, m-1)
    rh = RollingHash(S, b=b, m=m)
    low = 0
    high = (N+1) // 2 + 1
    while high - low > 1:
        mid = (high + low) // 2
        is_match = False
        i = 0
        while not is_match and i+mid*2 <= N:
            for j in range(i+mid, N-mid+1):
                if rh.get(i, i+mid) == rh.get(j, j+mid):
                    is_match = True
                    break
            i += 1
        if is_match:
            low = mid
        else:
            high = mid
    return low


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        prefix = [0] * (n+1)
        power = [1] * (n+1)
        for i, c in enumerate(map(ord, S)):
            prefix[i+1] = prefix[i] * b + c
            prefix[i+1] %= m
            power[i+1] = power[i] * b
            power[i+1] %= m
        self.S = S
        self.prefix = prefix
        self.power = power
        self.b = b
        self.m = m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        h = self.prefix[r] - self.power[r-l] * self.prefix[l]
        return h % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        h = self.power[l2] * h1 + h2
        return h % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    m = 999999937
    b = random.randint(10000, m-1)
    rh = RollingHash(S, b=b, m=m)
    low = 0
    high = (N+1) // 2 + 1
    while high - low > 1:
        mid = (high + low) // 2
        is_match = False
        i = 0
        while not is_match and i+mid*2 <= N:
            for j in range(i+mid, N-mid+1):
                if rh.get(i, i+mid) == rh.get(j, j+mid):
                    is_match = True
                    break
            i += 1
        if is_match:
            low = mid
        else:
            high = mid
    return low


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ret = 0
for d in range(1, n - 1):
    l = 0
    for i in range(n - d):
        if s[i] == s[i + d]:
            l += 1
        else:
            l = 0
        ret = max(ret, min(l, d))
print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
d = dict()
words = []
length = 0
word = ''
for i in range(N):
    s = S[i]
    d[s] = d.get(s, 0) + 1
    if d[s] >= 2:
        length += 1
        word = word + s
        words.append(word)
    else:
        length = 0
        word = ''
new_words = []
for w in words:
    for i in range(len(w)):
        new_words.append(w[i:])

new_words.sort(key=lambda a: -len(a))

length = 0
for w in new_words:
    c = S.count(w)
    if c >= 2:
        length = len(w)
        break
print(length)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n//2, -1, -1):
    for j in range(n-1):
        aaa = s[j: j+i]
        for k in range(j+i, n):
            if k+i > n:
                break
            bbb = s[k: k+i]
            # print(aaa, bbb, i, (aaa == bbb))
            if aaa == bbb:
                ans = i
                break
        if ans > 0:
            break
    if ans > 0:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=10**9+7):
        rh = 0
        for s in S:
            rh *= b
            rh %= m
            c = self._c(s)
            rh += c
            rh %= m
        size = len(S)
        self.S = S
        self.rh = rh
        self.rh_head = rh
        self.b = b
        self.bn = pow(b, size, m)
        self.binv = pow(b, m-2, m)
        self.m = m
        self.offset = 0
        self.size = size

    def _c(self, s):
        return ord(s) - ord("a") + 1

    def rotate(self):
        """右方向に1字ずらす"""
        if self.size <= 0:
            raise ValueError("No data left.")
        self.rh *= self.b
        self.rh %= self.m
        self.rh -= self._c(self.S[self.offset]) * self.bn
        self.rh %= self.m
        self.rh += self._c(self.S[(self.offset + self.size) % len(self.S)])
        self.rh %= self.m
        self.offset += 1
        self.offset %= len(self.S)
        return self

    def contract(self):
        """右端を1字削る"""
        if self.size <= 0:
            raise ValueError("No data left.")
        self.rh = self.rh_head
        self.rh -= self._c(self.S[self.size-1])
        self.rh %= self.m
        self.rh *= self.binv
        self.rh %= self.m
        self.offset = 0
        self.size -= 1
        self.bn = pow(self.b, self.size, self.m)
        self.rh_head = self.rh
        return self

    def get_hash(self):
        if self.size <= 0:
            raise ValueError("No data left.")
        return self.rh
    
    def __len__(self):
        return self.size

    def __eq__(self, other):
        return self.size == other.size and self.rh == other.rh


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    m = 10**9+7
    b = random.randint(10000, m-1)
    rh = RollingHash(S)
    ans = 0
    for n in range(N, N//2, -1):
        rh.contract()
    for n in range(N//2, 0, -1):
        hdict = defaultdict(list)
        for i in range(0, N - n + 1):
            # list all S[i:i+n]
            h = rh.get_hash()
            hdict[h].append(i)
            rh.rotate()
        for h in hdict.keys():
            if hdict[h][-1] - hdict[h][0] > ans:
                ans = max(ans, n)
        rh.contract()
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))