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:
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):
        for j in range(i+1, n):
            val = SA.get_lcp(i, j)
            if val > j - i:
                val = j - i
            if val > ans:
                ans = val
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

N=int(input())
S=input()
def condition(num):
    if num==0:
        return True
    else:
        flag=0
        data=[]
        for i in range(0,N-num+1):
            data.append([S[i:i+num],i])
        data.sort()
        partdata=[data[i][0] for i in range(0,len(data))]
        partdata=groupby(partdata)
        subdata=[]
        for key,group in partdata:
            g=len(list(group))
            subdata.append(g)
        s=0
        t=subdata[0]-1
        if len(subdata)==1:
            if data[t][1]-data[s][1]>=num:
                flag=1
        for i in range(0,len(subdata)-1):
            if data[t][1]-data[s][1]>=num:
                flag=1
            s=t+1
            t=t+subdata[i+1]
        return flag==1

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

Submission status: Wrong Answer

Solution code:
from itertools import groupby

N=int(input())
S=input()
def condition(num):
    if num==0:
        return True
    else:
        flag=0
        data=[]
        for i in range(0,N-num+1):
            data.append([S[i:i+num],i])
        data.sort()
        partdata=[data[i][0] for i in range(0,len(data))]
        partdata=groupby(partdata)
        subdata=[]
        for key,group in partdata:
            g=len(list(group))
            subdata.append(g)
        s=0
        t=subdata[0]-1
        for i in range(0,len(subdata)-1):
            if data[t][1]-data[s][1]>=num:
                flag=1
            s=t+1
            t=t+subdata[i+1]
        return flag==1

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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


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

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	SS = IS()
	ans = 0
	for l in range(N-1):
		i = 1
		j = 0
		S = copy.copy(SS[l:])
		A = [0]*len(S)
		while (i < len(S)):
			while (i+j < len(S) and S[j] == S[i+j] and  j < i):
				j+=1
			A[i] = j
			if (j == 0):
				i+=1
				continue
			k = 1
			while (i+k < len(S) and k+A[k] < j and k < i):
				A[i+k] = A[k]
				k+=1
			i += k
			j -= k
		ans = max(max(A),ans)
	print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	SS = IS()
	ans = 0
	for l in range(N-1):
		i = 1
		j = 0
		S = copy.copy(SS[l:])
		A = [0]*len(S)
		while (i < len(S)):
			while (i+j < len(S) and S[j] == S[i+j] and  j< i):
				j+=1
			A[i] = j
			if (j == 0):
				i+=1
				continue
			k = 1
			while (i+k < len(S) and k+A[k] < j):
				A[i+k] = A[k]
				k+=1
			i += k
			j -= k
		ans = max(max(A),ans)
	print(ans)

main()

Submission status: Wrong Answer

Solution code:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R1=RollingHash(S,37,10**9+7)
R2=RollingHash(S,29,10**9+9)
ans=0
for ln in range(1,N//2+1):
    D=set()
    for l in range(N-ln+1):
        tmp=(R1.get(l,l+ln),R2.get(l,l+ln))
        if tmp in D:
            ans=max(ln,ans)
        D.add(tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R=RollingHash(S,37,10**9+7)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=R.get(l,l+ln)
        if not(tmp in D):
            D[tmp]=[l,l]
        D[tmp][1]=max(D[tmp][1],l)
        D[tmp][0]=min(D[tmp][0],l)
    #print(ln,D)
    for k in D:
        if D[k][1]-D[k][0]>=ln:
            ans=max(ans,ln)
print(ans)

Submission status: Wrong Answer

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

s=[[0]*N for i in range(N)]
k=0
while(k<N-1):
  i=k+1
  j=0
  while(i<N):
    while(i+j<N):
      if S[i+j]==S[j+k]:
        j+=1
      else:
        break
    s[k][i]=j
    if j == 0:
      i+=1
      continue
    else:
      l = 1
      while(i+l < N and l + s[k][l] < j):
        s[k][i+l]=s[k][l]
        l+=1
      i += l
      j -= l
  k+=1
ans=0
for i in range(N):
  for j in range(i+1,N):
    if s[i][j]+i > j:
      ans = max(ans,j - i)
    else:
      ans=max(s[i][j],ans)
print(ans)

Submission status: Wrong Answer

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

s=[[0]*N for i in range(N)]
k=0
while(k<N-1):
  i=k+1
  j=0
  while(i<N):
    while(i+j<N):
      if S[i+j]==S[j+k]:
        j+=1
      else:
        break
    s[k][i]=j
    if j == 0:
      i+=1
      continue
    else:
      l = 1
      while(i+l < N and l + s[k][l] < j):
        s[k][i+l]=s[k][l]
        l+=1
      i += l
      j -= l
  k+=1
ans=0
for i in range(N):
  for j in range(i+1,N):
    if s[i][j]+i >= j:
      ans = max(ans,j - i - 1)
    else:
      ans=max(s[i][j],ans)
print(ans)

Submission status: Wrong Answer

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

s=[[0]*N for i in range(N)]
k=0
while(k<N-1):
  i=k+1
  j=0
  while(i<N):
    while(i+j<N and k+j < i):
      if S[i+j]==S[j+k]:
        j+=1
      else:
        break
    s[k][i]=j
    if j == 0:
      i+=1
      continue
    else:
      l = 1
      while(i+l < N and l + s[k][l] < j and s[k][l]<l):
        s[k][i+l]=s[k][l]
        l+=1
      i += l
      j -= l
  k+=1
ans=0
for i in range(N):
  ans=max(ans,max(s[i]))
print(ans)

Submission status: Wrong Answer

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

s=[[0]*N for i in range(N)]
k=0
while(k<N-1):
  i=k+1
  j=0
  while(i<N):
    while(i+j<N and k+j < i):
      if S[i+j]==S[j+k]:
        j+=1
      else:
        break
    s[k][i]=j
    if j == 0:
      i+=1
      continue
    else:
      l = 1
      while(i+l < N and l + s[k][l] < j):
        s[k][i+l]=s[k][l]
        l+=1
      i += l
      j -= l
  k+=1
ans=0
for i in range(N):
  ans=max(ans,max(s[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
def z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
res = 0
for i in range(n-1):
    c = z_algo(s[i:])
    # print(c)
    for j,t in enumerate(c):
        if t > n//2 or j == 0: continue
        res = max(res, t)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1; j = 0
    A[0] = l = N
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
res = 0
for i in range(n-1):
    c = z_algo(s[i:])
    # print(c)
    for j,t in enumerate(c):
        if t > n//2 or j == 0: continue
        res = max(res, t)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1; j = 0
    A[0] = l = N
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
res = 0
for i in range(n):
    c = z_algo(s[i:])
    # print(c)
    for j,t in enumerate(c):
        if t > n//2 or j == 0: continue
        res = max(res, t)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]

for l in range(N)[::-1]:
    for r in range(l+1, N)[::-1]:
        dp[l][r] = dp[l+1][r+1]+1 if S[l]==S[r] else 0

ans = 0 
for i in range(N):
    for j in range(N):
        ans = max(ans, dp[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ans = 0
ans = 0
l, r = 0, 1

while l<N:
    while r<N:
        v = 0
        for i in range(r-l):
            if r+i>=N or l+i>=r:break
            if S[l+i]!=S[r+i]:continue
            v+=1
        ans = max(ans, v)
        r+=v if v!=0 else 1
    l+=1
    r=l+1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ans = 0
ans = 0
l, r = 0, 1

while l<N:
    s1 = S[l]
    v = 0
    while r<N:
        s2 = S[r]
        if s1!=s2:
            r+=1
            continue
        v = 1
        for i in range(1, r-l):
            if r+i>=N or l+i>=r:break
            if S[l+i]!=S[r+i]:continue
            v+=1
        ans = max(ans, v)
        r+=v
    l+=1
    r=l+1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ans = 0
ans = 0
l, r = 0, 1

while l<N:
    s1 = S[l]
    v = 0
    while r<N:
        s2 = S[r]
        if s1!=s2:
            r+=1
            continue
        v = 1
        for i in range(1, r-l):
            if r+i>=N or l+i>=r:break
            v+=1
            if S[l+i]!=S[r+i]:continue
        ans = max(ans, v)
        r+=v
    l+=1
    r=l+1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ans = 0
ans = 0
l, r = 0, 1

while l<N:
    s1 = S[l]
    v = 0
    while r<N:
        s2 = S[r]
        if s1!=s2:
            r+=1
            continue
        v = 1
        for i in range(1, r-l):
            if r+i>=N or l+i>=r:break
            v+=1
            if S[l+i]!=S[r+i]:continue
        ans = max(ans, v)
        l+=v
        r+=v
    if v==0:
        l+=1
        r=l+1
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7
from collections import defaultdict

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
h = defaultdict(list)
for i in range(n):
    for j in range(i+1,min(n+1,i+100)):
        t = s[i:j]
        h[t].append((i,j))
mx = mx2 = 0
for t in h:
    if len(t)<mx or len(h[t])<2:
        continue
    m = len(h[t])
    for x in range(m-1):
        for y in range(x+1,m):
            if h[t][x][1]<=h[t][y][0] or \
               h[t][y][1]<=h[t][x][0]:
                mx = max(mx,len(t))
                if len(t)==100:
                    z = h[t][x][1]
                    u = h[t][y][1]
                    k = abs(z-u)-100
                    for j in range(k):
                        if z+j>=n or u+j>=n or s[z+j]!=s[u+j]:
                            break
                        mx2 = max(mx2, 100+j+1)
print(max(mx,mx2))

Submission status: Wrong Answer

Solution code:
def z_algo(S):
    N = len(S)

    A = [0] * N
    A[0] = N
    i = 1
    j = 0

    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


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

ans = 0
for i in range(N):
    A = z_algo(S[i:])
    if len(A) > 1:
        ans = max(ans, max(A[1:]))

print(ans)

Submission status: Wrong Answer

Solution code:
def z_algorithm(s):
  n = len(s)
  z = [None] * n
  z[0] = n
  
  i = 1
  j = 0
  while i < n:
    while i + j < n and s[j] == s[i + j]:
      j += 1
    z[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i + k < n and z[k] + k < j:
      z[i + k] = z[k]
      k += 1
    i += k
    j -= k
  return z

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

answer = 0
for j in range(N):
  T = S[j:]
  Z = z_algorithm(T + "$" + S)
  length = len(T)
  for i in range(len(T) + 1, len(Z) - len(T)):
    answer = max(answer, Z[i])

print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [ord(i) for i in input()]

ans = 0

for l in range(1, N):
    cnt = 0
    for i in range(N - l):
        if S[i] == S[i + l]:
            cnt += 1
        else:
            cnt = 0
        if cnt >= l:
            break
    ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

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

def z_algorithm(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    tmp = 0
    for a in A:
        if 2 * a > N:
            continue
        else:
            tmp = max(tmp, a)
    return tmp

ans = 0
for i in range(N):
    ans = max(ans, z_algorithm(S[i:]))

print (ans)

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 9 + 9
q = 1007
q2 = 2009

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q2) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q2 + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	rolling_Hash1 = [None] * (N - M + 1)
	rolling_Hash1[0] = val1
	rolling_Hash2 = [None] * (N - M + 1)
	rolling_Hash2[0] = val2

	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q2 - A[i] * mul2 + A[i + M]) % p2
		rolling_Hash1[i + 1] = val1
		rolling_Hash2[i + 1] = val2

		if Droll1[val1] == -1:
			Droll1[val1] = i + 1
		else:
			if rolling_Hash1[i + 1] == rolling_Hash1[Droll1[val1]] and rolling_Hash2[i + 1] == rolling_Hash2[Droll1[val1]] and i + 1 - Droll1[val1] >= M:
				return M

	print(rolling_Hash1)

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 9 + 9
q = 1007
q2 = 2009

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q2) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q2 + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q2 - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 21
p2 = 2147483647
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()