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: Wrong Answer

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j] and j <= i:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	print(tmp)
	res = max(tmp[1:])
	if ans < res:
		ans = res

print(ans)

Submission status: Wrong Answer

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j] and j < i:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	res = max(tmp[1:])
	if ans < res:
		ans = res

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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


def print(*args):
  pass


a = 0
processed = set()
for pos in range(N):
  s = S[pos]
  if s in processed:
    continue
  processed.add(s)

  q = []
  i = S.find(s, pos + 1)
  while i > 0:
    q.append(i)
    i = S.find(s, i + 1)

  print(pos, q)
  for i in range(len(q)):
    pos2 = q[i]
    j = 0
    n = min(pos2 - pos, N - pos2)
    print(pos, pos2, n)
    for j in range(n):
      if S[pos + j] != S[pos2 + j]:
        print('A')
        break
      if pos + j == pos2:
        print('B')
        break
      print(pos, pos2, j, "ok")

    a = max(j + 1, a)

sys.stdout.write(str(a))

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
def z_algorithm(s):
    ls = len(s)
    Z = [0] * ls
    Z[0] = ls
    i, j = 1, 0
    while i < ls:
        while i + j < ls and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < ls and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
for i in range(1, n-1):
    z = z_algorithm(s[i:])
    print(z)
    ans = max(ans, max(z[1:]))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
def z_algorithm(s):
    ls = len(s)
    Z = [0] * ls
    Z[0] = ls
    i, j = 1, 0
    while i < ls:
        while i + j < ls and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < ls and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
for i in range(n-1):
    z = z_algorithm(s[i:])
    ans = max(ans, max(z[1:]))

print(ans)

Submission status: Wrong Answer

Solution code:
#Z-algorithm
n=int(input())
s=input()
def Zalgo(s):
    ans=0
    L=len(s)
    Z=[0]*L
    Z[0]=L
    i=1;j=0
    while i<L:
        while i+j < L and s[j]==s[i+j]:j+=1
        Z[i]=j
        if Z[i] > ans and Z[i]<i:
            ans=Z[i]
        if j == 0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            k+=1
        i+=k
        j-=k
    return ans
ans=0
for i in range(n):
    p=Zalgo(s[i:])
    if p > ans:
        ans=p
print(ans)

Submission status: Wrong Answer

Solution code:
#Z-algorithm
n=int(input())
s=input()
def Zalgo(s):
    ans=0
    L=len(s)
    Z=[0]*L
    Z[0]=L
    i=1;j=0
    while i<L:
        while i+j < L and s[j]==s[i+j]:j+=1
        Z[i]=j
        if Z[i] > ans and Z[i]<=n//2:
            ans=Z[i]
        if j == 0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            k+=1
        i+=k
        j-=k
    return ans
ans=0
for i in range(n):
    p=Zalgo(s[i:])
    if p > ans:
        ans=p
print(ans)

Submission status: Wrong Answer

Solution code:
#Z-algorithm
n=int(input())
s=input()
def Zalgo(s):
    ans=0
    L=len(s)
    Z=[0]*L
    Z[0]=L
    i=1;j=0
    while i<L:
        while i+j < L and s[j]==s[i+j]:j+=1
        Z[i]=j
        if Z[i]>ans:ans=Z[i]
        if j == 0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            k+=1
        i+=k
        j-=k
    return ans
ans=0
for i in range(n):
  p=Zalgo(s[i:])
  if p > ans and p<=n//2:
    ans=p
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
def Zalgo(s):
    ans=0
    L=len(s)
    Z=[0]*L
    Z[0]=L
    i=1;j=0
    while i<L:
        while i+j < L and s[j]==s[i+j]:j+=1
        Z[i]=j
        if Z[i]>ans:ans=Z[i]
        if j == 0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            k+=1
        i+=k
        j-=k
    return ans
ans=0
for i in range(n):
  p=Zalgo(s[i:])
  if p > ans:
    ans=p
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SparseTable:

    def __init__(self, A, func):
        self.N = len(A)
        self.func = func
        h = 0
        while 1<<h < self.N:
            h += 1
        self.dat = list2d(h, 1<<h, 0)
        self.height = [0] * (self.N+1)

        for i in range(2, self.N+1):
            self.height[i] = self.height[i>>1] + 1
        for i in range(self.N):
            self.dat[0][i] = A[i]
        for i in range(1, h):
            for j in range(self.N):
                self.dat[i][j] = self.func(self.dat[i-1][j], self.dat[i-1][min(j+(1<<(i-1)), self.N-1)])
        
    def get(self, l, r):
        """ 区間[l,r)でのmin,maxを取得 """

        a = self.height[r-l]
        return self.func(self.dat[a][l], self.dat[a][r-(1<<a)])

class SuffixArray:

    def __init__(self, S):
        self.k = 1
        self.S = S
        self.N = len(S)
        self.rank = [0] * (self.N+1)
        self.tmp = [0] * (self.N+1)
        self.sa = [0] * (self.N+1)
        self.build_sa()

    # def compare_sa(self, i, j):
    #     if self.rank[i] != self.rank[j]:
    #         return self.rank[i] < self.rank[j]
    #     else:
    #         ri = self.rank[i+self.k] if i + self.k <= self.N else -1
    #         rj = self.rank[j+self.k] if j + self.k <= self.N else -1
    #         return ri < rj

    def compare_sa(self, i, j):
        """ saの比較関数 """

        # 第1キー
        if self.rank[i] == self.rank[j]: res1 =  0
        elif self.rank[i] < self.rank[j]: res1 =  -1
        else: res1 = 1
        # 第2キー
        ri = self.rank[i+self.k] if i + self.k <= self.N else -1
        rj = self.rank[j+self.k] if j + self.k <= self.N else -1
        if ri == rj: res2 = 0
        elif ri < rj: res2 = -1
        else: res2 = 1
        # 比較
        return res1 or res2

    def build_sa(self):
        """ Suffix Arrayの構築 """
        from operator import itemgetter
        # from functools import cmp_to_key

        # # 最初は1文字、ランクは文字コード
        # for i in range(self.N+1):
        #     self.sa[i] = i
        #     self.rank[i] = ord(self.S[i]) if i < self.N else -1

        # # k文字についてソートされているところから、　2k文字でソートする
        # k = 1
        # while k <= self.N:
        #     self.k = k
        #     self.sa = sorted(self.sa, key=cmp_to_key(self.compare_sa))
        #     k *= 2

        #     # いったんtmpに次のランクを計算し、それからrankに移す
        #     self.tmp[self.sa[0]] = 0
        #     for i in range(1, self.N+1):
        #         self.tmp[self.sa[i]] = self.tmp[self.sa[i-1]] + (1 if self.compare_sa(self.sa[i-1], self.sa[i]) else 0)
        #     for i in range(self.N+1):
        #         self.rank[i] = self.tmp[i]
        suffix_arr = [(self.S[i:], i) for i in range(self.N)]
        suffix_arr.sort(key=itemgetter(1), reverse=1)
        suffix_arr.sort(key=itemgetter(0))
        for i in range(self.N):
            self.sa[i] = suffix_arr[i][1]

    def build_lcp(self):
        """ LCP配列の構築 """

        self.lcp = [0] * (self.N+1)
        self.rsa = [0] * (self.N+1)
        for i in range(self.N+1):
            self.rsa[self.sa[i]] = i
        h = 0
        self.lcp[0] = 0
        for i in range(self.N):
            # 文字列内での位置iの接尾辞と、接尾辞配列内でその1つ前の接尾辞のLCPを求める
            j = self.sa[self.rsa[i]-1]

            # hを先頭の分1減らし、後ろが一致しているだけ増やす
            if h > 0:
                h -= 1
            while j+h < self.N and i+h < self.N:
                if self.S[j+h] != self.S[i+h]:
                    break
                h += 1
            self.lcp[self.rsa[i]-1] = h

        # 区間取得のためSparseTableを構築
        self.st = SparseTable(self.lcp, min)

    def getLCP(self, i, j):
        """ S[i:]とS[j:]の共通文字数を取得 """

        return self.st.get(min(self.rsa[i], self.rsa[j]), max(self.rsa[i], self.rsa[j]))

N = INT()
S = input()

sa = SuffixArray(S)
sa.build_lcp()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        lcp = min(sa.getLCP(i, j), j - i)
        ans = max(ans, lcp)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SparseTable:

    def __init__(self, A, func):
        self.N = len(A)
        self.func = func
        h = 0
        while 1<<h < self.N:
            h += 1
        self.dat = list2d(h, 1<<h, 0)
        self.height = [0] * (self.N+1)

        for i in range(2, self.N+1):
            self.height[i] = self.height[i>>1] + 1
        for i in range(self.N):
            self.dat[0][i] = A[i]
        for i in range(1, h):
            for j in range(self.N):
                self.dat[i][j] = self.func(self.dat[i-1][j], self.dat[i-1][min(j+(1<<(i-1)), self.N-1)])
        
    def get(self, l, r):
        """ 区間[l,r)でのmin,maxを取得 """

        a = self.height[r-l]
        return self.func(self.dat[a][l], self.dat[a][r-(1<<a)])

class SuffixArray:

    def __init__(self, S):
        self.k = 1
        self.S = S
        self.N = len(S)
        self.rank = [0] * (self.N+1)
        self.tmp = [0] * (self.N+1)
        self.sa = [0] * (self.N+1)
        self.build_sa()

    # def compare_sa(self, i, j):
    #     if self.rank[i] != self.rank[j]:
    #         return self.rank[i] < self.rank[j]
    #     else:
    #         ri = self.rank[i+self.k] if i + self.k <= self.N else -1
    #         rj = self.rank[j+self.k] if j + self.k <= self.N else -1
    #         return ri < rj

    def compare_sa(self, i, j):
        """ saの比較関数 """

        # 第1キー
        if self.rank[i] == self.rank[j]: res1 =  0
        elif self.rank[i] < self.rank[j]: res1 =  -1
        else: res1 = 1
        # 第2キー
        ri = self.rank[i+self.k] if i + self.k <= self.N else -1
        rj = self.rank[j+self.k] if j + self.k <= self.N else -1
        if ri == rj: res2 = 0
        elif ri < rj: res2 = -1
        else: res2 = 1
        # 比較
        return res1 or res2

    def build_sa(self):
        """ Suffix Arrayの構築 """
        # from functools import cmp_to_key

        # # 最初は1文字、ランクは文字コード
        # for i in range(self.N+1):
        #     self.sa[i] = i
        #     self.rank[i] = ord(self.S[i]) if i < self.N else -1

        # # k文字についてソートされているところから、　2k文字でソートする
        # k = 1
        # while k <= self.N:
        #     self.k = k
        #     self.sa = sorted(self.sa, key=cmp_to_key(self.compare_sa))
        #     k *= 2

        #     # いったんtmpに次のランクを計算し、それからrankに移す
        #     self.tmp[self.sa[0]] = 0
        #     for i in range(1, self.N+1):
        #         self.tmp[self.sa[i]] = self.tmp[self.sa[i-1]] + (1 if self.compare_sa(self.sa[i-1], self.sa[i]) else 0)
        #     for i in range(self.N+1):
        #         self.rank[i] = self.tmp[i]
        suffix_arr = [(self.S[i:], i) for i in range(self.N)]
        suffix_arr.sort()
        for i in range(self.N):
            self.sa[i] = suffix_arr[i][1]

    def build_lcp(self):
        """ LCP配列の構築 """

        self.lcp = [0] * (self.N+1)
        self.rsa = [0] * (self.N+1)
        for i in range(self.N+1):
            self.rsa[self.sa[i]] = i
        h = 0
        self.lcp[0] = 0
        for i in range(self.N):
            # 文字列内での位置iの接尾辞と、接尾辞配列内でその1つ前の接尾辞のLCPを求める
            j = self.sa[self.rsa[i]-1]

            # hを先頭の分1減らし、後ろが一致しているだけ増やす
            if h > 0:
                h -= 1
            while j+h < self.N and i+h < self.N:
                if self.S[j+h] != self.S[i+h]:
                    break
                h += 1
            self.lcp[self.rsa[i]-1] = h

        # 区間取得のためSparseTableを構築
        self.st = SparseTable(self.lcp, min)

    def getLCP(self, i, j):
        """ S[i:]とS[j:]の共通文字数を取得 """

        return self.st.get(min(self.rsa[i], self.rsa[j]), max(self.rsa[i], self.rsa[j]))

N = INT()
S = input()

sa = SuffixArray(S)
sa.build_lcp()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        lcp = min(sa.getLCP(i, j), j - i)
        ans = max(ans, lcp)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
l=0
r=n
while r-l!=1:
  mid=(r+l)//2
  dic={}
  flag=False
  for i in range(n-mid+1):
    tmp=s[i:i+mid]
    if tmp not in dic:
      dic[tmp]=i+mid
    else:
      if dic[tmp]<=i:
        flag=True
        break
  if flag==True:
    l=mid
  else:
    r=mid
print(l,r)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
if n==2:
  if s[0]==s[1]:
    print(1)
  else:
    print(0)
else:
  l=-1
  r=n//2
  while r-l!=1:
    mid=(r+l)//2
    dic={}
    flag=False
    for i in range(n-mid):
      tmp=s[i:i+mid]
      if tmp not in dic:
        dic[tmp]=i+mid
      else:
        if dic[tmp]<=i:
          flag=True
          break
    if flag==True:
      l=mid
    else:
      r=mid
  print(r)

Submission status: Wrong Answer

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

for i in range(n//2):
    le = n//2 - i
    ls = set([])
    for j in range(n-le+1):
        t = s[j:j+le]
        if t in ls:
            print(le)
            exit()
        else:
            ls.add(t)
print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
lb, ub = -1, N//2 + 1
while ub - lb > 1:
    m = (lb + ub) // 2
    s1 = S[:m]
    s2 = S[m:2*m]
    ss = set()
    ok = False
    for i in range(2*m, N):
        ss.add(s1)
        if s2 in ss:
            ok = True
            break
        s1 = s1[1:] + s2[0]
        s2 = s2[1:] + S[i]
    if s2 in ss:
        ok = True
    if ok:
        lb = m
    else:
        ub = m
print(lb)

Submission status: Wrong Answer

Solution code:
class DisjointSparseTable:
    def __init__(self, a, op=lambda a, b : max(a,b), e=0):
        # Operator
        self.op = op
        # Identity element
        self.e = e
        self.n = len(a)
        self.level = (self.n - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()

    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.n + step, step*2):
                # Forward
                val = self.e
                for j in range(step):
                    val = self.op(val, self.table[-1][mid + j])
                    self.table[lv][mid + j] = val
                # Backward
                val = self.e
                for j in range(step):
                    val = self.op(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val

    # Returns f[l:r)
    def fold(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return self.op(self.table[lv][l], self.table[lv][r-1])


class SuffixArray:
    def __init__(self, a):
        self.a = a + [0]
        self.k = max(self.a) + 1
        self.n = len(self.a)
        self.sa = self.SA_IS(self.a, self.n, self.k)
        # Construct LCP disjoint sparse table
        self.rank = [0] * self.n
        for i, item in enumerate(self.sa):
            self.rank[item] = i
        self.lcp = self.build_LCP(self.a, self.sa, self.rank)
        self.lcp_dst = DisjointSparseTable(self.lcp, op=lambda a,b : min(a,b), e=0)

    # Find the start or end of each bucket
    def get_buckets(self, a, k, end=True):
        bucket = [0] * k
        for item in a:
            bucket[item] += 1
        sumation = 0
        for i in range(k):
            sumation += bucket[i]
            if end:
                bucket[i] = sumation
            else:
                bucket[i] = sumation - bucket[i]
        return bucket

    def induce_SAl(self, a, sa, n, k, lstype):
        bucket = self.get_buckets(a, k, end=False)
        for i in range(n):
            j = sa[i] - 1
            if j >= 0 and (not lstype & (1 << j + 1)):
                sa[bucket[a[j]]] = j
                bucket[a[j]] += 1

    def induce_SAs(self, a, sa, n, k, lstype):
        bucket = self.get_buckets(a, k, end=True)
        for i in range(n-1, -1, -1):
            j = sa[i] - 1
            if j >= 0 and lstype & (1 << j + 1):
                bucket[a[j]] -= 1
                sa[bucket[a[j]]] = j
    
    def is_LMS(self, index, lstype):
        return lstype >> (index+1) & 1 and not (lstype >> index & 1)

    def is_stype(self, index, lstype):
        return lstype >> (index+1) & 1

    def SA_IS(self, a, n, k):
        # L-type or S-type
        # LS-type array in bits, 1-indexed, initialized with S-type first
        lstype = 1
        prev_type = 0
        prev_item = self.k
        for i, item in enumerate(a[::-1]): 
            shift = n - i
            if item == prev_item:
                lstype |= prev_type << shift 
            elif item < prev_item:
                lstype |= 1 << shift 
                prev_type = 1
            else:
                prev_type = 0
            prev_item = item
        # Bucket array
        bucket = self.get_buckets(a, k)
        # Find ends of buckets
        sa = [-1] * n
        for i in range(n - 1, 0, -1):
            if self.is_LMS(i, lstype):
                bucket[a[i]] -= 1
                sa[bucket[a[i]]] = i
        self.induce_SAl(a, sa, n, k, lstype)
        self.induce_SAs(a, sa, n, k, lstype)

        lcm_cnt = 0
        for i in range(n):
            if self.is_LMS(sa[i], lstype):
                sa[lcm_cnt] = sa[i]
                lcm_cnt += 1
        for i in range(lcm_cnt, n):
            sa[i] = -1

        # Rename LCM strings
        name = 1; prev = sa[0] 
        sa[lcm_cnt + sa[0] // 2] = 0
        for pos in sa[1: lcm_cnt]:
            diff = False
            for d in range(n):
                if a[pos + d] != a[prev + d] or (self.is_stype(pos + d, lstype) != self.is_stype(prev + d, lstype)):
                    diff = True
                    break
                elif d > 0 and (self.is_LMS(pos + d, lstype) or self.is_LMS(prev + d, lstype)):
                    break
            if diff:
                name += 1; prev = pos
            pos //= 2
            sa[lcm_cnt + pos] = name - 1
        sub_a = []
        for i in range(lcm_cnt, n):
            if sa[i] >= 0:
                sub_a.append(sa[i])
            
        # Recursively sort LMS sub strings
        if name < lcm_cnt:
            sub_sa = self.SA_IS(sub_a, len(sub_a), name + 1)
        else:
            sub_sa = sa[:lcm_cnt]
            for i in range(lcm_cnt):
                sub_sa[sub_a[i]] = i
        bucket = self.get_buckets(a, k, end=True)
        j = 0
        for i in range(1, n):
            if self.is_LMS(i, lstype):
                sub_a[j] = i
                j += 1
        # Earn correctly sorted LCMs
        for i in range(lcm_cnt):
            sa[i] = sub_a[sub_sa[i]]
        for i in range(lcm_cnt, n):
            sa[i] = -1
        for i in range(lcm_cnt - 1, -1, -1):
            j = sa[i]; sa[i] = -1
            bucket[a[j]] -= 1
            sa[bucket[a[j]]] = j

        # Correct induced sorting
        self.induce_SAl(a, sa, n, k, lstype)
        self.induce_SAs(a, sa, n, k, lstype)
        return sa
    
    def build_LCP(self, a, sa, rank):
        # Add sentinel
        sa.append(-1)
        lcp = [0] * len(a)
        same_cnt = 0
        for index1 in range(len(a)):
            if same_cnt != 0:
                same_cnt -= 1
            index2 = sa[rank[index1] + 1]
            while a[index1 + same_cnt] == a[index2 + same_cnt]:
                same_cnt += 1
            lcp[rank[index1]] = same_cnt
        # Remove sentinel
        sa.pop()
        return lcp

    def get_lcp(self, l, r):
        rank_l = self.rank[l]
        rank_r = self.rank[r]
        if rank_l > rank_r:
            rank_l, rank_r = rank_r, rank_l
        return self.lcp_dst.fold(rank_l, rank_r)

    def search(self, b):
        m = len(b)
        l = 0; r = self.n + 1
        matched = 0
        while r - l > 1:
            mid = (l + r) // 2
            lm_lcp = self.get_lcp(l, mid)
            if matched < lm_lcp:
                l = mid
            elif matched > lm_lcp:
                r = mid
            else:
                a_itr = self.sa[mid] + matched; b_itr = matched
                diff = 0
                while b_itr < m and a_itr < self.n:
                    if b[b_itr] != self.a[a_itr]:
                        diff = b[b_itr] - self.a[a_itr]
                        break
                    a_itr += 1; b_itr += 1
                if diff >= 0:
                    l = mid
                    matched = b_itr
                else:
                    r = mid
        return matched, l

if __name__ == "__main__":
    n = int(input())
    s = input().rstrip()
    ord_base = ord("a") - 1
    a = [ord(ch) - ord_base for ch in s]
    SA = SuffixArray(a)
    ans = 0
    for i in range(n+1):
        for j in range(i+1, n+1):
            val = SA.get_lcp(i, j)
            if val > j - i:
                val = j - i
            if val > ans:
                ans = val
    print(ans)