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:
def z_argorithm(s):
    s_len=len(s)
    a=[0]*s_len
    a[0]=s_len
    i=1
    j=0
    while i<s_len:
        while i+j<s_len and s[j]==s[i+j]:
            j+= 1
        a[i]=j
        k=1
        if j==0:
            i += 1
            continue
        while i+k<s_len and k+a[k]<j:
            a[i+k]=a[k]
            k+=1

        i +=k
        j -=k
    return a
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(n-1):
        a=z_argorithm(s[i:])
        for n,i in enumerate(a):
            if ans < min(n,i):
                ans = min(n,i)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(len(s)-1):
    for j in range(i, len(s)-1):
        if s[i:j] in s[j:]:
            maxx = max(maxx, len(s[i:j]))

print(maxx)

Submission status: Time Limit Exceeded

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

for i in range(len(s)):
    for j in range(len(s)):
        if s[i:j] in s[j:]:
            maxx = max(maxx, len(s[i:j]))

print(maxx)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
dp = [[0 for i in range(n+1)] for j in range(n+1)]
ans = 0
for i in range(n):
  for j in range(n):
    if i == j:
      break
    if s[i] == s[j]:
      t = dp[i][j]
      if j == i-t:
        dp[i+1][j+1]=1
      else:
        dp[i+1][j+1]=1+t
        ans = max(ans, 1+t)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())
ans = [0]
for i in range(N):
  lst = [j for j, x in enumerate(S)
          if x == S[i] and j > i]
  for s in lst:
    num = 1
    ss = s; ii = i
    while ss <N-1:
      if S[ii+1] == S[ss+1]:
        if ii +1 == s:
          ans.append(num)
          break
        num +=1
        ss += 1; ii += 1
      else:
        ans.append(num)
        break
    ans.append(num)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
l = [[0] * n for _ in range(n)]
ans = 0

for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if i >= j and s[i] == s[j]:
            l[i][j] += 1
            
            if i < n-1 and j < n-1 and l[i+1][j+1] > 0:
                l[i][j] += l[i+1][j+1]
                
        now = min(l[i][j], i - j)
        ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
l = [[0] * n for _ in range(n)]
ans = 0

for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] == s[j]:
            l[i][j] += 1
            
            if i < n-1 and j < n-1 and l[i+1][j+1] > 0:
                l[i][j] += l[i+1][j+1]
                
        now = min(l[i][j], i - j)
        ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#二分探索
N = int(input())
S = input()
l = 0
r = N

ans = 0
while r - l > 1:
    mid = (l + r) // 2
    for i in range(N - (2*mid) + 1 ):
        if S[i:i+mid] in S[i+mid:]:
            l = mid
            ans = mid
            break
    else:
        r = mid
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def main():
    n = int(input())
    s = input()
    dp = [[0 for i in range(n)] for j in range(n)]
    
    for i in range(n):
        for j in range(i,n):
            if s[i]!=s[j]:
                continue
            else:
                cnt = 0
                for k in range(min(n-j,j-i)):
                    if s[i+k] ==s[j+k]:
                        cnt += 1
                    else:
                        break
                dp[i][j] = cnt 
    mx = 0
    for i in range(n):
        mx = max(mx,max(dp[i]))
    print(mx)

if __name__ =='__main__':main()

Submission status: Time Limit Exceeded

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

dp = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(i,n):
        if s[i] !=s[j]:
            continue
        else:
            cnt = 0
            for k in range(min(n-j,j-i)):
                if s[i+k] ==s[j+k]:
                    cnt += 1
                else:
                    break
            dp[i][j] = cnt 
mx = 0
for i in range(n):
    mx = max(mx,max(dp[i]))

print(mx)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
S = input()

def z_arr(s):
    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.

            p = k - lt  # Pair index.
            right_part_len = rt - k + 1

            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
    return Z

ans = 0
for i in range(len(S)):
    x = z_arr(S[i:])
    for j,e in enumerate(x):
        remain_length = len(S[i:])-e
        if remain_length >= e:
            if e > ans:
                ans = e

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def receive_string():
    string_length = int(input())
    string = input()
    return string_length, string

def find_max_duplication(string_length, string):
    start_length = string_length // 2
    if string_length > 26**2:
        s = 3
        max_string = 2
    elif string_length > 26:
        s = 2
        max_string = 1
    else:
        s = 1
        max_string = 0
    for current_length_head, current_length_tail in zip(range(s, start_length+1), range(start_length, s-1, -1)):
        flag = 1
        for start in range(string_length - current_length_head):
            if string[start:current_length_tail+start] in string[start+current_length_tail:]:
                max_string = current_length_tail
                flag = 1
                break
            if string[start:current_length_head+start] in string[start+current_length_head:]:
                max_string = current_length_head
                flag = 0
            if current_length_head > len(string[start+current_length_head:]):
                break
        if flag != 0:
            break

    print(max_string)
    return 0
if __name__ == '__main__':
    string_length, string = receive_string()
    ret = find_max_duplication(string_length, string)

Submission status: Time Limit Exceeded

Solution code:
def receive_string():
    string_length = int(input())
    string = input()
    return string_length, string

def find_max_duplication(string_length, string):
    start_length = string_length // 2
    if string_length > 26:
        s = 2
        max_string = 1
    else:
        s = 1
        max_string = 0
    for current_length_head, current_length_tail in zip(range(s, start_length+1), range(start_length, s-1, -1)):
        flag = 1
        for start in range(string_length - current_length_head):
            if string[start:current_length_tail+start] in string[start+current_length_tail:]:
                max_string = current_length_tail
                flag = 1
                break
            if string[start:current_length_head+start] in string[start+current_length_head:]:
                max_string = current_length_head
                flag = 0
            if current_length_head > len(string[start+current_length_head:]):
                break
        if flag != 0:
            break

    print(max_string)
    return 0

if __name__ == '__main__':
    string_length, string = receive_string()
    ret = find_max_duplication(string_length, string)

Submission status: Time Limit Exceeded

Solution code:
def receive_string():
    string_length = int(input())
    string = input()
    return string_length, string

def find_max_duplication(string_length, string):
    start_length = string_length // 2
    if string_length > 26:
        s = 2
        max_string = 1
    else:
        s = 1
        max_string = 0
    for current_length in range(s, start_length+1):
        flag = 1
        # print('current_length : ', current_length)
        for start in range(string_length - current_length):
            # print('start : ', start)
            # print(string[start:current_length+start] , string[start+current_length:])
            if string[start:current_length+start] in string[start+current_length:]:
                max_string = current_length
                # print(max_string)
                flag = 0
            if current_length > len(string[start+current_length:]):
                break
        if flag != 0:
            break

    print(max_string)
    return 0

if __name__ == '__main__':
    string_length, string = receive_string()
    ret = find_max_duplication(string_length, string)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def receive_string():
    string_length = int(input())
    string = input()
    return string_length, string

def find_max_duplication(string_length, string):
    start_length = string_length // 2
    mod = string_length % 2
    for current_length in range(start_length, 0, -1):
        for start in range(string_length - current_length):
            if string[start:current_length+start] in string[start+current_length:]:
                print(current_length)
                return 0
            if current_length > len(string[start+current_length:]):
                break
    print(0)
    return 0

if __name__ == '__main__':
    string_length, string = receive_string()
    ret = find_max_duplication(string_length, string)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

N=int(input())
S=input()
L=0
for i in range(N//2,N): #N-i文字を切り出す。残りがi文字となり自由度に相当。長い文字列から順に試して見つかったら即終了。重複しない文字列を見るため、文字列の長さは元の半分以下である必要がある。
    for j in range(i-1):  #手前の(j+1)文字目から(N-i)文字に着目し、後ろにk文字ずらした時に一致するか確認。i=j+kを満たす
        for k in range(N-i+j,N):
            if k>=N-i+j and S[j:(N-i+j)]==S[(k):(N-i+k)]:
                L=N-i
                break
        else:
            continue
        break
    else:
        continue
    break
print(L)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

N=int(input())
S=input()
L=0
for i in range(N//2,N):
    for j in range(i-1):
        for k in range(N-i+j,N):
            if k>=N-i+j and S[j:(N-i+j)]==S[(k):(N-i+k)]:
                L=N-i
                break
        else:
            continue
        break
    else:
        continue
    break
print(L)

Submission status: Time Limit Exceeded

Solution code:
import hashlib

def make_table(N, S):
    mod = 2 ** 61 - 1
    table = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for head in range(N):
        for tail in range(head+1, N+1):
            if head < tail:
                encoded = S[head:tail].encode()
                table[head][tail] = int(hashlib.md5(encoded).hexdigest(), 16) // mod
    return table

def solve(N, S):
    table = make_table(N, S)
    longest = 0
    for i in range(1, N//2+1):
        for j in range(0, N-i):
            for k in range(j+i, N):
                if k+i > N:
                    continue
                # compare S[j:j+i] and S[k:k+i]
                if table[j][j+i] == table[k][k+i]:
                    longest = max(longest, i)
    return longest

def main():
    N = int(input().strip())
    S = input().strip()
    result = solve(N, S)
    print(result)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def maxLengthBeginningFrom(i, string):
    ans = 0
    substring = string[i:]
    zArray = efficientZ(substring)
    for j in range(len(zArray)):
        ans = max(ans, min(j, zArray[j]))
    return ans

def efficientZ(string):
    """
    引数: string
    戻り値: 数値からなる配列。0番目の値は0．空文字列に対しては[]を返す。
    >>> efficientZ("ababa")
    [0,0,3,0,1]
    >>> efficientZ("aaaaa")
    [0,4,3,2,1]
    """
    length = len(string)
    Z = [0 for _ in range(length)]
    left = 0
    right = 0
    for i in range(1, length):
        if i >= right: 
            j = 0
            while i + j < length:
                if (string[j] == string[i + j]):
                    j += 1
                else:
                    break
            Z[i] = j
            left = i
            right = i + j
        else:
            correspondingValue = Z[i - left]
            if i + correspondingValue < right:
                Z[i] = correspondingValue
            else:
                j = right - i
                while i + j < length:
                    if string[i + j] == string[j]:
                        j += 1
                    else:
                        break
                Z[i] = j
                left = i
                right = i + j
    return Z 

N = int(input())
S = input()
ans = 0
for i in range(len(S)):
    ans = max(ans,maxLengthBeginningFrom(i, S))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  join = ''.join
  def getCharNGram(n,s):
      charGram = (join(s[i:i+n]) for i in range(len(s)-n+1))
      return charGram
  N = int(input())
  S = input()
  ans = 0
  from collections import Counter
  for i in range(1,N//2+1):
      l = getCharNGram(i,S)
      am = Counter(l)
      for j in am.values():
        if j>1:
          ans =max(i,ans)
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  def getCharNGram(n,s):
      charGram = [''.join(s[i:i+n]) for i in range(len(s)-n+1)]
      return charGram
  N = int(input())
  S = input()
  ans = 0
  from collections import Counter
  for i in range(1,N//2+1):
      l = getCharNGram(i,S)
      am = Counter(l)
      for j in am.values():
        if j>1:
          ans =max(i,ans)
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def si(): return input().rstrip()
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class RollingHash():
    """ロリハ。容易に衝突するので注意。"""
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:  # rollinghash by 2 mod
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)

        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
        if opt == 2:  # rollinghash by 2 mod
            for i, e in enumerate(s):
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2

        if self.opt == 2:
            return (res1, res2)
        else:
            return res1
# END CUT HERE
if not __debug__:
    import io
    import random
    class MyStdin(io.TextIOWrapper):
        @classmethod
        def readline(cls):
            N = 1000000
            yield "{}\n".format(N)
            yield "{}\n".format(''.join([chr(random.randint(0, 25) + ord("a")) for i in range(N // 5)] * 5))
    input = MyStdin.readline().__next__

def ABC131E():
    N = ii()
    S = si()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d.keys():
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    if not __debug__:
        import cProfile
        cProfile.run('ABC131E()', sort=1)
    else:
        ABC131E()

Submission status: Time Limit Exceeded

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def si(): return input().rstrip()
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class RollingHash():
    """ロリハ。容易に衝突するので注意。"""
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:  # rollinghash by 2 mod
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)

        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
        if opt == 2:  # rollinghash by 2 mod
            for i, e in enumerate(s):
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2

        if self.opt == 2:
            return (res1, res2)
        else:
            return res1
# END CUT HERE
if not __debug__:
    import io
    import random
    class MyStdin(io.TextIOWrapper):
        @classmethod
        def readline(cls):
            N = 200000
            yield "{}\n".format(N)
            yield "{}\n".format(''.join([chr(random.randint(0, 25) + ord("a")) for i in range(N)]))

def ABC131E():
    N = int(input().rstrip())
    S = input().rstrip()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d.keys():
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    if not __debug__:
        input = MyStdin.readline().__next__
        import cProfile
        cProfile.run('ABC131E()', sort=1)
    else:
        input = sys.stdin.readline
        ABC131E()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = list(input())

def C(k):
    for i in range(0, n - 2 * k + 1):
        for j in range(i + k, n - k + 1):
            if S[i : i + k] == S[j : j + k]:
                return True
            
    return False

lb = 0
ub = n

while ub - lb > 1:
    mid = (lb + ub) // 2
    
    if C(mid):
        lb = mid
    else:
        ub = mid
        
if C(ub):
    print(ub)
else:
    print(lb)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    s = input().strip()

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(N, S):    
    Z = [0] * N     # 重複ありの最大長    
    left = 0
    right = 0
    max_length = 0
    
    for i in range(1, len(S)):
        k = 0        
        if i < right and Z[i-left] <= right - i:
            Z[i] = Z[i-left]
            continue
        elif i < right:
            k = right - i
        
        while i + k < N:         
            if S[i+k] == S[k]:
                k += 1
            else:
                break

        Z[i] = k
        left = i
        right = i + k
        #重複しない場合の最大長　は　i
        max_length = max(max_length, min(Z[i], i))
        
    return max_length
    
N = int(input())
S = input()

ans = 0
for i in range(N):
    s = S[i:]
    n = N - i
    if ans >= len(s) // 2:
        break
    ans = max(ans, z_algorithm(n, s))
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
ans=0
n=int(input())
s=input()
class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1

rh=RollingHash(s)
for i in range(n-2):
    for le in range(1,n//2+1):
        for j in range(i+le,n-le+1):
            if rh.get(i,i+le)==rh.get(j,j+le):
                ans=max(ans,le)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
ans = 0
for i in range(1,n):
    tmpans = 0
    streak = 0
    for j in range(n-i):
        if s[j] == s[j+i]:
            streak += 1
        else:
            tmpans = max(tmpans,min(i,streak))
            streak = 0
    tmpans = max(tmpans,min(i,streak))
    ans = max(tmpans,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
ansl = []
for i in range(1,n):
    ans = 0
    count = 0
    for j in range(n-i):
        #print(s[j],s[j+i])
        if s[j] == s[j+i]:
            count += 1
        else:
            if count > 0:
                if count > ans:
                    ans = min(count,i)
                count = 0
    if count > ans:
        ans = min(count,i)
    ansl.append(ans)
if len(ansl) > 0:
    print(max(ansl))

Submission status: Time Limit Exceeded

Solution code:
n=input()
s=input()
best=0
for i in range(len(s)):
	for j in range(i):
		act=0
		while(s[i+act]==s[j+act]):
			act+=1
			if((j+act>=i)|(i+act>=len(s))):
				break
		if(act>best):
			best=act
		j+=1
	i+=1
print(best)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
ansl = []
for i in range(1,n-1):
    l = []
    count = 0
    for j in range(n-i):
        #print(s[j],s[j+i])
        if s[j] == s[j+i]:
            count += 1
        else:
            if count > 0:
                if count > i:
                    l.append(i)
                else:
                    l.append(count)
                count = 0
    l.append(min(count,i))
    ansl.append(max(l))
if len(ansl) > 0:
    print(max(ansl))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
TF = False
for i in range((N//2),-1,-1): #iが長さ
    if TF == True:
        break
    for j in range(N-2*i):    #jは開始位置
        if TF == True:
            break
        tmp = S[j:j+i+1]
        for k in range(j+i+1,N-i):    #kは判断する方の開始位置
            if S[k:k+i+1] == tmp:
                #print("i=",i,"j=",j,"k=",k, tmp)
                ans = i+1
                TF = True
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
TF = False
for i in range(0,(N//2)+1): #iが長さ
    TF = False
    for j in range(N-2*i):    #jは開始位置
        if TF == True:
            break
        tmp = S[j:j+i+1]
        for k in range(j+i+1,N-i):    #kは判断する方の開始位置
            if S[k:k+i+1] == tmp:
                #print("i=",i,"j=",j,"k=",k, tmp)
                ans = i+1
                TF = True
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Z(s):
    ls = len(s)
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and s[j] == s[i+j]:
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    for i in range(ls):
        lcp[i] = min(lcp[i],i)
    return max(lcp)

n = int(input())
s = input()
print(max(Z(s[i:]) for i in range(n)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)
# END CUT HERE

def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d.keys():
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

import sys

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

T = len(S)

for t in reversed(range(T+1)):
    i = 0
    while 0 < len(S[i:i+t-1]) and len(S[i:i+t-1]) <= len(S[i+t-1:]):
        if S[i:i+t-1] in S[i+t-1:]:
            print(len(S[i:i+t-1]))
            sys.exit()
        i += 1
print('0')