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: Accepted

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            if se[kkk] <= i-n:
                    return True
        else:
            bs.insort(data,kkk)
            se[kkk] = i
    return False
def solver():
    n = onem()

    s = list(input())
    l = 0
    r = n//2
    for i in range(n):
        mid = -(-(l+r)//2)
        ans = search(s,mid)
        if l == mid:
            break
        if ans:
            l = mid
        else:
            r = mid-1
    print(l)



if __name__ == '__main__':
    solver()

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for i,s in enumerate(S):
    T = S[i:]
    d = [0]*(N-i)
    d[0] = -1
    k,j = 0,1
    while j< (N-i-1):
        matched = T[k] == T[j]
        if not matched and k>0:
            k = d[k]
        else:
            if matched:
                k += 1
            j += 1
            d[j] = k
    j,p = 1,0
    while j< (N-i) and p< (N-i):
        if (T[j] == T[p]) and (p*2 < j):
            j += 1
            p += 1
            ans = max(ans,p)
        elif p == 0:
            j += 1
        else:
            p = d[p]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
f=0
b=-1
for d in range(1,n):
  c=0
  for i in range(n-d):
    if s[i]==s[i+d] and c<d:
      if b==-1:b=i
      c+=1
      f=max(f,c)
    else:
      c=0
      b=-1
print(f)

Submission status: Accepted

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

ans = 0
index = 0
length = 1
while index < N-ans*2:
    while S[index:index+length] in S[index+length:]:
        length += 1
    if ans < length-1:
        ans = length-1
    index += 1
print(ans)

Submission status: Accepted

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

check_list = [ [ 0 for i in range(n) ] for i in range(n) ]


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

print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            if se[kkk] <= i-n:
                    return True
        else:
            bs.insort(data,kkk)
            se[kkk] = i
    return False
def solver():
    n = onem()

    s = list(input())
    l = 0
    r = n//2
    for i in range(n):
        mid = -(-(l+r)//2)
        ans = search(s,mid)
        if l == mid:
            break
        if ans:
            l = mid
        else:
            r = mid-1
    print(l)



if __name__ == '__main__':
    solver()

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
f=0
b=-1
for d in range(1,n):
    c=0
    for i in range(n-d):
        if s[i]==s[i+d] and c<d:
            if b==-1:
                b=i
            c+=1
            f=max(f,c)
        else:
            c=0
            b=-1
print(f)

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def is_match(string, pattern):
    if pattern in string:
        return True
    else:
        return False

def main():
    N = int(input())
    S = input()
    dp = [0] * N
    for i in range(1, N):
        length = dp[i - 1] + 1
        match_string = S[i - length + 1: i + 1]
        matched_string = S[:i+1-length]
        if is_match(matched_string, match_string):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
    print(dp[-1])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
debug = True

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    N = II()
    S = SI()

    #mark = [-1 for i in range(N)]
    ans = -1

    from collections import defaultdict
    posd = defaultdict(list)

    for i, c in enumerate(S):
        posd[c].append(i)

    for i in range(N):
        si = S[i]

        # headの文字の位置のリスト
        pos_list = posd[si]

        for pos in pos_list:
            if pos >= i:
                # 自分より前のところだけを探す
                continue

            # この場合は直前により長いシーケンスを見ているので見なくていい
            if pos > 0 and S[pos - 1] == S[i - 1]:
                continue

            # どこまであうかをやっていく
            for j in range(N):
                # 前回見たシーケンスは見ない
                # 自分のところまで来てたらやめる
                if pos+j == i:
                    break
                # 突き抜けたらやめる
                if i+j == N:
                    break

                you = pos + j
                me = i + j

                # 違ったらやめる
                if S[you] != S[me]:
                    break

                # 同じなら、マークする
                ans = max(ans, j)
                #mark[you] = max(mark[you], j)

    #dprint(mark)
    #print(max(mark)+1)
    print(ans + 1)

main()

Submission status: Accepted

Solution code:
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

from collections import defaultdict
N = int(input())
S = input()
ans = 0
for i in range(N):
    s = S[i:]
    z = Z(s)
    for j in range(len(z)):
        z[j] = min(j,z[j])
    ans = max(ans,max(z))

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
debug = True

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    N = II()
    S = SI()

    mark = [-1 for i in range(N)]

    from collections import defaultdict
    posd = defaultdict(list)

    for i, c in enumerate(S):
        posd[c].append(i)

    for i in range(N):
        si = S[i]

        # headの文字の位置のリスト
        pos_list = posd[si]

        for pos in pos_list:
            if pos >= i:
                # 自分より前のところだけを探す
                continue

            # この場合は直前により長いシーケンスを見ているので見なくていい
            if pos > 0 and S[pos - 1] == S[i - 1]:
                continue

            # どこまであうかをやっていく
            for j in range(N):
                # 前回見たシーケンスは見ない
                # 自分のところまで来てたらやめる
                if pos+j == i:
                    break
                # 突き抜けたらやめる
                if i+j == N:
                    break

                you = pos + j
                me = i + j

                # 違ったらやめる
                if S[you] != S[me]:
                    break

                # 同じなら、マークする
                mark[you] = max(mark[you], j)

    dprint(mark)
    print(max(mark)+1)



main()

Submission status: Accepted

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

ans = 0

while ans <= len(s)//2:
    prev_s = ''
    for i in range(ans+1, len(s)//2+1):
        if s[:i] in s[i:]:
            prev_s = s[:i]
        else:
            ans = max(ans, len(prev_s))
            break
    else:
        ans = max(ans, len(prev_s))
    s = s[1:]
    if len(s) == 1:
        break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = [ord(s) for s in input()]
# N = 5000
# S = "abcdefg" + "k"*4993

c = 0
for i in range(1, N):
    d = 0
    for s_j, t_j in zip(S, S[i:]):
        if s_j == t_j:
            d += 1
        else:
            c = max(c, min(d, i))
            d = 0
    c = max(c, min(d, i))

# print(S, t)
print(c)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    S = input()
    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    ans = 0

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1] == S[j-1] and dp[i-1][j-1] < (j-i):
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
            else:
                dp[i][j] == 0
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
s=list(input())
a=list(map(ord,s))
m=0
for i in range(1,n):
    cnt=0
    flg=0
    tmp=0
    for j in range(n-i):
        if a[j]==a[j+i] and flg==0:
            #print("!")
            flg=1
            tmp=j+i
            cnt+=1
        elif a[j]==a[j+i] and flg==1:
            #print("?")
            cnt+=1
            if tmp>j:
                m=max(m,cnt)
        else:
            #print("$")
            cnt=0
            flg=0
print(m)

Submission status: Accepted

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

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

ans = 0

for i in range(n):
    a = Z(s[i:])
    b = [a[j] if j - a[j] >= 0 else 0 for j in range(len(s[i:]))]
    ans = max(ans,max(b))

print(ans)


'''
    if len(a) > 1:
        ind = a.index(max(a[1:]))
        if a[ind-1] > 0:
            ans = max(ans,a[ind-1] // 2)
        elif a[ind] - ind - 1 < 0:
            continue
        else:
            ans = max(ans,a[ind])
'''

Submission status: Accepted

Solution code:
n = int(input())
s = input()
dp = [[0]*n for i in range(n)]
for i in range(n):
    dp[0][i] = 1 if s[0] == s[i] else 0
ans = 0
for i in range(1,n):
    for j in range(i,n):
        if s[i] == s[j]:
            if dp[i-1][j-1] > 0:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = 1
for i in range(n):
    for j in range(i + 1,n):
        if ans < dp[i][j] and i + dp[i][j] <= j:
            ans = dp[i][j]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
_max = 0
for i in range(n):
    for j in range(i+1, n):
        if _max >= j-i:
            continue
        part = s[i:j]
        if part in s[j:]:
            _max = j-i
        else:
            break
print(_max)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    S = input()
    dp = [[0]*(N+1) for _ in range(N+1)]
    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)
    print( max( [ max(dp[i]) for i in range(N+1)]))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[0] * (N+2) for _ in range(N+2)]
ans = 0
for i in range(1,N):
    for d in range(1,N+1-i):
        if S[i-1] == S[i-1+d]:
            dp[i][d] = min(d, dp[i-1][d]+1)
            ans = max(ans, dp[i][d])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
DP = [[0]*(N+1)for i in range(N+1)]
ans = 0
for i in range(N):
    for j in range(N):
        if S[i] == S[j] :
            DP[i+1][j+1] = DP[i][j]+1
            if j-DP[i+1][j+1]-i < 0:
                DP[i+1][j+1] = 0
print(max([max(i) for i in DP]))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [0]*N
j = 1

for i in range(N):
    while S[i:j] in S[j:N]:
        dp[i] = j-i
        j += 1
print(max(dp))

Submission status: Accepted

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

a = ""
ans = 0
for i in range(n):
  a += s[i]
  while(len(a) > 0):
    if a in s[i+1:]:
      ans = max(ans,len(a))
      break
    else:
      a = a[1:]
print(ans)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N = int(input())
S = input()

character_pos = [ set() for _ in range(26) ]
for i in range(N):
    character_pos[ord(S[i])-ord('a')].add(i)

ans = 0
continue_list = dict()
for i in range(N):
    s = S[i]
    new_continue_list = dict()
    for p in character_pos[ord(s)-ord('a')]:
        if p < i:
            new_continue_list[p] = 1
    for k, v in continue_list.items():
        if s == S[k+1]  and v + 1 <= i - k - 1:
            new_continue_list[k+1] = v+1
        elif v > ans:
            ans = v
    continue_list = new_continue_list

if len(continue_list.values()) > 0:
    ans = max(ans, max(continue_list.values()))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def max(a, b):
    return a if a > b else b
 
def is_match(string, pattern):
    # print(string, pattern)
    # pat_len = len(pattern)
    # skip = [pat_len for _ in range(256)]
    # for i in range(pat_len):
    #     skip[ord(pattern[i])] = pat_len - i - 1
    # i = pat_len - 1
    # while i < len(string):
    #     j = pat_len - 1
    #     while string[i] == pattern[j]:
    #         if j == 0:
    #             return True
    #         i -= 1
    #         j -= 1
    #     i = i + max(skip[ord(string[i])], pat_len-j)
    # return None
    if pattern in string:
        return True
    else:
        return False


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

    dp = [0] * N

    for i in range(1, N):
        length = dp[i - 1] + 1
        match_string = S[i - length + 1: i + 1]
        matched_string = S[:i+1-length]
        # print(match_string, matched_string)
        if is_match(matched_string, match_string):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
        # print(dp[i])
    
    # print(dp)
    print(dp[-1])



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True

ans=0
an=[]
n=I()
st=-1
s=list(input())
can=[]
for d in range(1,n):
    cnt=0
    for i in range(n-d):
        if s[i]==s[i+d] and st+cnt+1<=st+d:
            if st==-1:
                st=i
            #show('d,i,s[i],st,cnt,an',d,i,s[i],st,cnt,an)
            cnt+=1
            #an+=s[i]
            ans=max(ans,cnt)
        else:
            #show('d,i,s[i],st,cnt,an',d,i,s[i],st,cnt,an,'els')
            cnt=0
            #can+=[an]
            #an=[]
            st=-1
    cnt=0
print(ans)
#show(can)

Submission status: Accepted

Solution code:
n = int(input())
s = '^' + input().strip() + '$'

dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
longest = 0
for i in range(1, n + 2):
    for j in range(i + 1, n + 2):
        if s[i] == s[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            val = dp[i - 1][j - 1]
            if j - i < val:
                val = j - i
            if val > longest:
                longest = val

print(longest)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l,r=n//2+1,0
while l-r>1:
    t=(l+r)//2
    g=s[:t]
    q={}
    q[s[t:2*t]]=1
    d=s[t:2*t]
    for i in range(2*t,n):
        d=d[1:]+s[i]
        if d in q:
            q[d]+=1
        else:
            q[d]=1
    if g in q:
        r=t
    else:
        d=s[t:2*t]
        for i in range(t,n-t):
            q[d]-=1
            if q[d]==0:
                del q[d]
            d=d[1:]+s[i+t]
            g=g[1:]+s[i]
            if g in q:
                r=t
                break
        else:
            l=t
print(r)

Submission status: Accepted

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

# N = 5*10**3
# S = "".join(["t" for n in range(N)])

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

mx = 0

for i in range(N):
#   print(dp)
  for k in range(N):
    if i<k and S[i] == S[k]:
      dp[i+1][k+1] = 1
    c_before = dp[i][k]
    if k<N and i+c_before<k and S[k]==S[i]:
      dp[i+1][k+1] = c_before+1
      mx = max(mx,c_before+1)

# print(dp)
print(mx)

Submission status: Accepted

Solution code:

import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return sys.stdin.readline()[:-1]

def main():
    n = II()
    s = S()
    inf = n + 2
    m = [[0 for i in range(n)] for i in range(n)]
    first = [[inf for i in range(n)] for i in range(n)]
    # set 1st index value
    lcs = 0
    for i, c in enumerate(s):
        # print(c, s[0])
        if c == s[0]:
            m[i][0] = 1
            first[i][0] = i
            if i != 0:
                lcs = 1
    for i in range(1, n):
        for j in range(1, n):
            if i <= j:
                continue
            if s[i] == s[j]:
                if first[i-1][j-1] > j:
                    m[i][j] = m[i-1][j-1] + 1
                    lcs = max(m[i][j], lcs)
                    if first[i-1][j-1] == inf:
                        first[i][j] = i
                    else:
                        first[i][j] = first[i-1][j-1]
            else:
                m[i][j] = 0

    # print(m)
    print(lcs)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
S = input()
def match(n):
  D = defaultdict(list)
  for i in range(N + 1 - n):
    D[S[i:i + n]].append(i)
  for L in D.values():
    if len(L) > 1 and L[-1] - L[0] >= n:
      return True
  return False
def bs(upper, lower):
  if upper - lower == 1:
    return lower
  mid = (upper + lower) // 2
  if match(mid):
    return bs(upper, mid)
  else:
    return bs(mid, lower)
print(N // 2 if match(N // 2) else bs(N // 2, 0))

Submission status: Accepted

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

m = [[0] * n for _ in range(n)]
lcs = 0

# i = 0
for j in range(1, n):
    if s[j] == s[0]:
        m[0][j] = 1
        lcs = 1

# dp
for i in range(1, n-1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            m[i][j] = min(m[i-1][j-1] + 1, j - i)
            lcs = max(m[i][j], lcs)
        else:
            m[i][j] = 0

print(lcs)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

def check(L):
    strings = {}
    for i in range(N - L):
        s= S[i:i+L+1]
        if s in strings:
            start, end = strings[s]
            #print('exists', s, i, start, end)
            if i > end:
                #print('True')
                return True
        else:
            strings[s] = i, i + L
    
    #print('False')
    return False


N = int(raw_input())
S= raw_input()
lo = 0
hi = N/2 + 1
for i in range(13):
    mid= (lo +hi)//2
    has_two = check(mid)
    #print('checking ', mid)
    if has_two:
        lo = mid
    else:
        hi = mid
print(hi)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    S = input()
    next_end = 1
    max_length = 0
    for start in range(N-1):
        for end in range(next_end, N):
            text = S[start:end]
            if text in S[end:]:
                max_length = max(len(text), max_length)
                continue
            else:
                if start + 1 == end:
                    next_end = end + 1
                else:
                    next_end = end
            break
    
    print(max_length)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
P = 123456789012419
x = 31
ix = pow(x, P-2, P)
N = int(input())
A = [ord(s)-95 for s in input()]

def chk(k):
    D = {}
    s = 0
    for i in range(k):
        s = (s * x) % P
        s += A[i]
    X = [s]
    D[s] = k-1
    for i in range(k, N):
        s = ((s - pow(x, k-1, P) * A[i-k]) * x + A[i]) % P
        X.append(s)
        if s in D:
            if i - D[s] >= k:
                return 1
        else:
            D[s] = i
    return 0

l = 0
r = N//2 + 1
while r - l > 1:
    m = (l+r) // 2
    if chk(m):
        l = m
    else:
        r = m
print(l)

Submission status: Accepted

Solution code:
#
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n = int(input())
    s = input()
    if len(set(s)) == n:
        print(0)
        return

    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = -10**4

    for i in range(n):
        for j in range(i, n):
            if i == j:
                continue
            if s[i] == s[j]:
                if i > 0 and j > 0:
                    length = dp[i-1][j-1]
                    if j - length > i:
                        dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 1

    ans = 0
    for d in dp:
        ans = max(ans, max(d))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    
    ans = 0
    x = []
    for i in range(N):
        x.append(S[i])
        xj = ''.join(x)
        if(S[i+1:].count(xj)):
            ans = max(ans, len(xj))
        else:
            x.pop(0)

    print(ans)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod = 10 ** 9 + 7
hash = [0]
pow = [1]
for s in S :
    hash.append((hash[-1] * 26 + ord(s) - 97) % mod)
    pow.append(pow[-1] * 26 % mod)

M = 0
for i in range(N + 1) :
    for j in range(i + 1, N + 1) :
        for k in range(M + 1, N - j + 1) :
            if i + k > j :
                break
            if (hash[j+k] - hash[j] * (pow[k])) % mod == (hash[i+k] - hash[i] *  pow[k]) % mod :
                M += 1
            else :
                break
                
print(M)

Submission status: Accepted

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

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

for i in range(N):
    if i > 0 and S[0] == S[i]:
        dp[0][i] = 1

ans = 0
for i in range(0, N-1):
    for j in range(i, N-1):
        if S[i+1] == S[j+1]:
            tmp = dp[i][j] + 1
            tmp2 = min(tmp, j-i)
            dp[i+1][j+1] = tmp2
            if tmp2 > ans:
                ans = tmp2
print(ans)

Submission status: Accepted

Solution code:
MOD = 10000000000000061
def hsh(s):
    tot = 0
    pw = 1
    for c in s:
        tot = (tot*256 + ord(c))%MOD
        pw = (pw*256)%MOD
    return tot, pw

def ok(L, S):
    h, pw = hsh(S[:L])
    D = {}
    D[h] = 0
    for i in range(len(S) - L):
        j = i + 1
        h = ((h*256 - pw*ord(S[i])) + ord(S[i+L]))%MOD
        if h in D:
            if D[h] + L <= j: return True
        else:
            D[h] = j
    return False


raw_input()
S = raw_input()
lo = 0
hi = len(S)//2

while lo < hi:
    mid = (lo + hi + 1)//2
    ans = ok(mid, S)
    if ans:
        lo = mid
    else:
        hi = mid - 1
print(lo)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, s in enumerate(S):
  if i != 0 and S[i] == S[0]:
    dp[i][0] = 1
    dp[0][i] = 1

for i in range(1, N):
  for j in range(1, N):
    if i != j and S[i] == S[j]:
      if i + dp[i-1][j-1] == j or j + dp[i-1][j-1] == i:
        dp[i][j] = dp[i-1][j-1]
      else:
        dp[i][j] = dp[i-1][j-1] + 1
      ans = max(ans, dp[i][j])
print(ans)

Submission status: Accepted

Solution code:
def lrs(str):
    n = len(str)
    LCSRe = [[0 for x in range(n + 1)]
             for y in range(n + 1)]
    res = ""
    res_length = 0
    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (str[i - 1] == str[j - 1] and
                    LCSRe[i - 1][j - 1] < (j - i)):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

                if (LCSRe[i][j] > res_length):
                    res_length = LCSRe[i][j]
                    index = max(i, index)

            else:
                LCSRe[i][j] = 0


    if (res_length > 0):
        for i in range(index - res_length + 1,
                       index + 1):
            res = res + str[i - 1]

    return res


if __name__ == "__main__":
    a = int(input())
    s = input()

    print(len(lrs(s)))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
s_table = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(i, n):
        if i != j and s[i] == s[j]:
            s_table[i][j] = 1
            s_table[j][i] = 1

# print(s_table)
ans = 0
for i in range(n):
    cnt = 0
    start = i
    j = 0
    while i < n and j < n:
        # print(i, j, start)
        if s_table[i][j] == 1 and start != j:
            # print(1)
            cnt += 1
            ans = max(cnt, ans)
        else:
            cnt = 0
            start = i + 1
        i += 1
        j += 1
print(ans)

Submission status: Accepted

Solution code:
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

MOD = 10**9 + 7
P = 97
def solve(N, S):
    A = [0]
    rawA = []
    #powers = []
    ha = 0
    #pwr = 1
    for c in S:
        x = ord(c) - ord('a') + 2
        rawA.append(x)
        #ha += x * pwr
        #ha %= MOD
        #powers.append(pwr)
        ha += x
        A.append(ha)
        #pwr *= P
        #pwr %= MOD
    #powers.append(pwr)

    def gethash(i, j):
        ha = A[j] - A[i]
        #ha *= pow(powers[i-1], MOD-2, MOD)
        ha %= MOD
        #print 'gh', i,j, ';', ha
        return ha

    # A
    #print 'g1',gethash(2, 2+5)
    #print 'g2', gethash(8, 8+5)
    
    def doublematch(L):
        if L == 0: return True
        for i in xrange(N - L + 1):
            for j in xrange(i + L, N - L + 1):
                if gethash(i, i+L) == gethash(j, j+L) and rawA[i:i+L] == rawA[j:j+L]:
                    return True

    #print map(doublematch, range(len(A)))
    lo, hi = 0, len(A) / 2
    while lo < hi:
        mi = (lo + hi + 1) / 2
        if doublematch(mi):
            lo = mi
        else:
            hi = mi - 1
    return lo

print solve(rri(), rr())

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

N = int(input())
S = input()
F = [1]*(N//2 + 2)
for i in range(1, len(F)):
    F[i] = F[i]*26

OK = 0
NG = N//2 + 1

def check(l):
    D = set()
    for i in range(N-2*l+1):
        #print(S[i:i+l], S[i+l:i+2*l])
        D.add(S[i:i+l])
        if S[i+l:i+2*l] in D:
            return True
    else:
        return False



while abs(OK - NG) > 1:
    mid = (OK + NG)//2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1, N):
    tmp = "?" * i + S
    c = 0
    m = 0
    for j in range(i, N):
        if S[j] != tmp[j]:
            c = 0
        else:
            c += 1
        m = max(m, c)
    m = min(m, i)
    ans = max(ans, m)

print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
s = input()
ans=0
for i in range(n):
    #print(i,n)
    maxim = i
    num=[0 for k in range(n-i)]
    count=0
    lmax=0
    for j in range(n-i):
        if(s[j]==s[i+j]):
            num[j]=1
            count+=1
            #print(count)
            if(lmax<count):
                lmax=count
        else:
            count=0
    #print(lmax)
    if(ans<lmax):
        ans=min(lmax,maxim)
print(ans)