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:
#!/usr/bin/env python
# coding: utf-8

# In[2]:


N = int(input())
S = input()
"""
13
strangeorange
5
"""


# In[17]:


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


# In[18]:


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


# In[19]:


print(max_cont)


# In[ ]:

Submission status: Wrong Answer

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

    l, r, ans = 0, 0, 0

    while r < N:
        print(l, r)
        if S[l:r] in S[r:N]:
            ans = max(ans, r - l)
            r += 1
        else:
            l += 1

    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Wrong Answer

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


    def check(l):
        if l == 0:
            return True
        # for i in range(n-l*2+1):
        i = 0
        while i < n-l*2+1:
            j = i + l
            # for j in range(i+l, n-l+1):
            while j < n-l+1:
                cnt = 0
                # print(i, j)
                for k in range(l):
                    if s[i+k] == s[j+k]:
                        cnt += 1
                    else:
                        break

                if cnt == l:
                    # print(l, i, j, cnt,)
                    return True
                else:
                    j += max(cnt, 1)
            i += 1

        return False


    # print(6, check(6))
    # print()

    lb = 0
    ub = n // 2 + 1
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check(mid):
            lb = mid
        else:
            ub = mid

    print(lb)

main()

Submission status: Wrong Answer

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


def check(l):
    if l == 0:
        return True
    for i in range(n-l*2 + 1):
        k = 0
        j = i+l
        while j < n:
            # print(i, j-k, k)
            if s[i+k] == s[j]:
                k += 1
            else:
                if j > n-l + 1:
                    break

                if k > 0:
                    j -= 1

                k = 0

            if k == l:
                # print(l, i, j-k+1, k,)
                return True
            j += 1

    return False

# print(6, check(6))
# print()

lb = 0
ub = n // 2 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Submission status: Wrong Answer

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


def check(l):
    if l == 0:
        return True
    for i in range(n-l*2 + 1):
        k = 0
        j = i+l
        while j < n:
            # print(i, j-k, k)
            if s[i+k] == s[j]:
                k += 1
            else:
                if j > n-l:
                    break

                if k > 0:
                    j -= 1

                k = 0

            if k == l:
                # print(l, i, j-k+1, k,)
                return True
            j += 1

    return False

# print(6, check(6))
# print()

lb = 0
ub = n // 2 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Submission status: Wrong Answer

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


def check(l):
    if l == 0:
        return True
    for i in range(n-l*2 + 1):
        cnt = 0
        k = 0
        for j in range(i+l, n):
            if s[i+k] == s[j]:
                k += 1
                cnt += 1
            else:
                if j > n-l:
                    break

                j -= k
                k = 0
                cnt = 0

            if cnt == l:
                # print(l, i, j, cnt,)
                return True

    return False


lb = 0
ub = n // 2 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Submission status: Wrong Answer

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


def check(l):
    if l == 0:
        return True
    for i in range(n-l*2 + 1):
        cnt = 0
        k = 0
        for j in range(i+l, n):
            if s[i+k] == s[j]:
                k += 1
                cnt += 1
            else:
                j -= k
                k = 0
                cnt = 0
                if j > n-l:
                    break

            if cnt == l:
                # print(l, i, j, cnt,)
                return True

    return False


lb = 0
ub = n // 2 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Submission status: Wrong Answer

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


def check(l):
    if l == 0:
        return True
    for i in range(n-l*2):
        for j in range(i+l, n-l+1):
            cnt = 0
            for k in range(l):
                if s[i+k] == s[j+k]:
                    cnt += 1
                else:
                    break

            if cnt == l:
                # print(l, i, j, cnt,)
                return True

    return False


lb = 0
ub = n // 2 + 1
# for i in range(ub+1):
#     print(i, check(i))

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

print(lb)

Submission status: Wrong Answer

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


def check(l):
    if l == 0:
        return True
    for i in range(n-l*2):
        cnt = 0
        k = 0
        for j in range(i+l, n):
            if s[i+k] == s[j]:
                k += 1
                cnt += 1
            else:
                j -= k
                k = 0
                cnt = 0
                # if j > n-l+1:
                #     break

            if cnt == l:
                # print(l, i, j, cnt,)
                return True

    return False


lb = 0
ub = n // 2 + 1
# for i in range(ub+1):
#     print(check(i))
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Submission status: Wrong Answer

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


def check(l):
    if l == 0:
        return True
    for i in range(n-l*2):
        cnt = 0
        k = 0
        for j in range(i+l, n):
            if s[i+k] == s[j]:
                k += 1
                cnt += 1
            else:
                j -= k
                k = 0
                cnt = 0
                # if j > n-l+1:
                #     break

            if cnt == l:
                # print(l, i, j, cnt,)
                return True

    return False


lb = 0
ub = n // 2 + 1
for i in range(ub+1):
    print(check(i))
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Submission status: Wrong Answer

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


def check(l):
    if l == 0:
        return True
    for i in range(n-l*2):
        cnt = 0
        k = 0
        for j in range(i+l, n):
            if s[i+k] == s[j]:
                k += 1
                cnt += 1
            else:
                j -= k
                k = 0
                cnt = 0
                if j > n-l:
                    break

            if cnt == l:
                # print(l, i, j, cnt,)
                return True

    return False


lb = 0
ub = n // 2 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    ans = 0

    for i in range(N):
        s1 = S[0:i+1]
        s2 = S[i+1:N]
        if s1 in s2 and len(s1) < len(s2):
            ans = i+1
        else:
            cache_ans = ans
            for j in range(i):
                s = s1[1 + j:]
                if s in s2:
                    ans = len(s)
                    break
            if len(s2) < ans and len(s1) > len(s2):
                break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    ans = 0

    for i in range(N):
        s1 = S[0:i+1]
        s2 = S[i+1:N]
        if s1 in s2 and len(s1) < len(s2):
            ans = i+1
        else:
            cache_ans = ans
            for j in range(i):
                s = s1[1 + j:]
                if s in s2:
                    ans = len(s)
                    break
            if len(s2) > ans and len(s1) > len(s2):
                break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    ans = 0

    for i in range(N):
        s1 = S[0:i+1]
        s2 = S[i+1:N]
        print(s1, s2)
        if s1 in s2 and len(s1) < len(s2):
            ans = i+1
        else:
            cache_ans = ans
            for j in range(i):
                s = s1[1 + j:]
                if s in s2:
                    ans = len(s)
                    break
            if len(s2) > ans and len(s1) > len(s2):
                break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

hantei = False
ans = 0

isleft = True
kosu_original = N//4
for i in range(N-kosu_original+1):
    temp = S[i:i+kosu_original]
    #print("比較する文字列1:", temp)
    #print("比較する文字列2:",S[0:i] + "|" + S[i+1:],"\n")
    if temp in S[0:i] + "|" + S[i+1:]:
        #print("Trueの時\n-----------------")
        ans = kosu_original
        isleft = False
        break

if isleft:
    for kosu in range(kosu_original-1, 0, -1):
        if hantei:
            break

        for i in range(N-kosu+1):
            if hantei:
                break
            else:
                temp = S[i:i+kosu]
                #print("比較する文字列1:", temp)
                #print("比較する文字列2:",S[0:i] + "|" + S[i+1:],"\n")
            if temp in S[0:i] + "|" + S[i+1:]:
                #print("Trueの時\n-----------------")
                ans = kosu
                hantei = True
                break
else:
    for kosu in range(N//2, kosu_original, -1):
        if hantei:
            break

        for i in range(N-kosu+1):
            if hantei:
                break
            else:
                temp = S[i:i+kosu]
                #print("比較する文字列1:", temp)
                #print("比較する文字列2:",S[0:i] + "|" + S[i+1:],"\n")
            if temp in S[0:i] + "|" + S[i+1:]:
                #print("Trueの時\n-----------------")
                ans = kosu
                hantei = True
                break

print(ans)

Submission status: Wrong Answer

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

hantei = False
ans = 0
for kosu in range(N//2, 0, -1):
    if hantei:
        break

    for i in range(N-kosu+1):
        if hantei:
            break
        else:
            temp = S[i:i+kosu]
            #print("比較する文字列1:", temp)
            #print("比較する文字列2:",S[0:i] + "|" + S[i+1:],"\n")
        if temp in S[0:i] + "|" + S[i+1:]:
            #print("Trueの時\n-----------------")
            ans = kosu
            hantei = True
            break
print(ans)

Submission status: Wrong Answer

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

ans = 0
for kosu in range(1, N//2+1):
    hantei = False
    for i in range(N-kosu):
        if hantei:
            break
        else:
            temp = S[i:i+kosu]
            # print("temp:", temp)
            # print("比較する文字列",S[0:i] + "|" + S[i+1:])
        if temp in S[0:i] + "|" + S[i+1:]:
            # print("Trueの時")
            ans = len(list(temp))
            hantei = True
            break
print(ans)

Submission status: Wrong Answer

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]:
        j += 1
    dp[i] = j - i
print(max(dp))

Submission status: Wrong Answer

Solution code:
from pprint import pprint

def longest_match(N, S):
    table = [[0 for _ in range(N+1)] for _ in range(N+1)]
    result = 0
    for i in range(0, N):
        for j in range(i+1, N):
            if S[i] == S[j]:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = table[i][j]
            result = max(result, min(j-i, table[i+1][j+1]))
    return result

def solve(N, S):
    longest = longest_match(N, S)
    return longest

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from pprint import pprint

def longest_match(N, S):
    table = [[0 for _ in range(N+1)] for _ in range(N+1)]
    result = 0
    for i in range(N):
        for j in range(i+1, N):
            if S[i] == S[j] and i + table[i][j] + 1 <= j:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = table[i][j]
            result = max(result, table[i+1][j+1])
    return result

def solve(N, S):
    longest = longest_match(N, S)
    return longest

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from pprint import pprint

def longest_match(N, S):
    table = [[0 for _ in range(N+1)] for _ in range(N+1)]
    result = 0
    for i in range(N):
        for j in range(i+1, N):
            if S[i] == S[j] and i + table[i][j] + 1 < j:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = table[i][j]
            result = max(result, table[i+1][j+1])
    return result

def solve(N, S):
    longest = longest_match(N, S)
    return longest

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def longest_match(N, S):
    table = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(i+1, N):
            if S[i] == S[j] and table[i][j] + 1 <= j - i:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = table[i][j]
    return max([max(row) for row in table])

def solve(N, S):
    longest = longest_match(N, S)
    return longest

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def sort_bucket(s, bucket, order):
    d = defaultdict(list)
    for i in bucket:
        key = s[i + order // 2:i + order]
        d[key].append(i)
    result = []
    for k, v in sorted(d.items()):
        if len(v) > 1:
            result += sort_bucket(s, v, 2 * order)
        else:
            result.append(v[0])
    return result

def suffix_array_ManberMyers(s): 
    return sort_bucket(s, (i for i in range(len(s))), 1)
    
def lcp_array(s, sa):
    # http://codeforces.com/blog/entry/12796
    n = len(s)
    k = 0
    lcp = [0] * n
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
        
    for i in range(n):
        j = sa[rank[i] - 1]
        if k:
            k -= 1
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[rank[i]] = min(k, abs(j-i));

            
    return lcp
  
n = int(input())
s = input()
sa = suffix_array_ManberMyers(s)
e = lcp_array(s, sa)
print(max(e))

Submission status: Wrong Answer

Solution code:
def longest_match(N, S):
    table = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(i+1, N):
            if S[i] == S[j]:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = table[i][j]
    return max([max(row) for row in table])

def solve(N, S):
    longest = longest_match(N, S)
    return longest

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def sort_bucket(s, bucket, order):
    d = defaultdict(list)
    for i in bucket:
        key = s[i + order // 2:i + order]
        d[key].append(i)
    result = []
    for k, v in sorted(d.items()):
        if len(v) > 1:
            result += sort_bucket(s, v, 2 * order)
        else:
            result.append(v[0])
    return result

def suffix_array_ManberMyers(s): 
    return sort_bucket(s, (i for i in range(len(s))), 1)
    
def lcp_array(s, sa):
    # http://codeforces.com/blog/entry/12796
    n = len(s)
    k = 0
    lcp = [0] * n
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
        
    for i in range(n):
        if rank[i] == n-1:
            k = 0
            continue
        j = sa[rank[i] + 1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[rank[i]] = min(k,abs(j-i));
        if k:
            k -= 1
            
    return lcp
  
n = int(input())
s = input()
sa = suffix_array_ManberMyers(s)
e = lcp_array(s, sa)
print(min(max(e), len(s) // 2))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def sort_bucket(s, bucket, order):
    d = defaultdict(list)
    for i in bucket:
        key = s[i + order // 2:i + order]
        d[key].append(i)
    result = []
    for k, v in sorted(d.items()):
        if len(v) > 1:
            result += sort_bucket(s, v, 2 * order)
        else:
            result.append(v[0])
    return result

def suffix_array_ManberMyers(s): 
    return sort_bucket(s, (i for i in range(len(s))), 1)
    
def lcp_array(s, sa):
    # http://codeforces.com/blog/entry/12796
    n = len(s)
    k = 0
    lcp = [0] * n
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
        
    for i in range(n):
        if rank[i] == n-1:
            k = 0
            continue
        j = sa[rank[i] + 1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[rank[i]] = k;
        if k:
            k -= 1
            
    return lcp
  
n = int(input())
s = input()
sa = suffix_array_ManberMyers(s)
e = lcp_array(s, sa)
print(max(e))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def sort_bucket(s, bucket, order):
    d = defaultdict(list)
    for i in bucket:
        key = s[i + order // 2:i + order]
        d[key].append(i)
    result = []
    for k, v in sorted(d.items()):
        if len(v) > 1:
            result += sort_bucket(s, v, 2 * order)
        else:
            result.append(v[0])
    return result

def suffix_array_ManberMyers(s): 
    return sort_bucket(s, (i for i in range(len(s))), 1)
    
def lcp_array(s, sa):
    # http://codeforces.com/blog/entry/12796
    n = len(s)
    k = 0
    lcp = [0] * n
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
        
    for i in range(n):
        if rank[i] == n-1:
            k = 0
            continue
        j = sa[rank[i] + 1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[rank[i]] = min(k, abs(j-i));
        if k:
            k -= 1
            
    return lcp
  
n = int(input())
s = input()
sa = suffix_array_ManberMyers(s)
e = lcp_array(s, sa)
print(max(e))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    list=[]
    flg=False
    for i in range(n-m+1):
        if s[i:i+m] in list:
            flg=True
            break
        else:
            list.append(s[i:i+m])
    if flg:
        l=m
    else:
        r=m-1
print(l)

Submission status: Wrong Answer

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

def get_keys_from_value(d, val):
    return [k for k, v in d.items() if v == val]

n = INT()
s = input()

a=0
i=0
j=1

while j<n:
    print(s[i:j],s[j:])
    if s[i:j] in s[j:]:
        a = max(a,len(s[i:j]))
        j+=1
    else:
        i+=1
    if i==j:
        i+=1
        j+=2

print(a)

Submission status: Wrong Answer

Solution code:
import math
n = int(raw_input().strip())
a = raw_input()

leng = 1
max_len = 0
for leng in range(1,int(math.ceil(n/2))):
  for i in range(0,n-leng+1):
    for j in range(i+1,n-leng+1):

      # print "i = ",i,"j = ",j," length = ",leng
      if a[i:i+leng]==a[j:j+leng]:
        # print a[i:i+leng]
        max_len = leng
        break
    if max_len==leng:
      break


print max_len

Submission status: Wrong Answer

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

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

dp = [[0] * N for i in range(N)]
max_leng2 = 0 
for i in range(0, N):
    leng2 = 0

    j = i - 1
    while j > -1:
        if S[i] == S[j]:
            sta_j = j
            if j != 0:
                leng2 = dp[i-1][sta_j-1] + 1
            else: 
                leng2 = 1
            dp[i][sta_j] = leng2
            max_leng2 = max(max_leng2, leng2)
        j -= 1
print(max_leng2)

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 0
max_reach = -1
for i in range(N):
    if i < max_reach:
        continue
    for j in range(i+max_length,N):
        if S[i:j] in S[j:N]:
            continue
        else:
            if j == i+max_length:
                break
            elif j > max_length:
                max_length = j-i-1
                max_reach = j-i-1
                break
print(max_length)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
#LCSRe i番目とj番目でそれぞれ終わるような共通文字列の長さ
#i < j であるi文字目とj文字目が等しいならLCSRe[i + 1][j + 1] = LCSRe[i][j] + 1
#res_lengthよりLCSReの更新した値が大なら、その時のindexをiへ、res_lengthも更新

def longestRepeatedSubstring(s): 
  n = len(s) 
  LCSRe = [[0 for _ in range(n + 1)] for _ 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 s[i - 1] == s[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 + s[i - 1] 
  return res_length
print(longestRepeatedSubstring(S))

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 0
max_reach = -1
for i in range(N):
    if i < max_reach:
        continue
    for j in range(i+max_length,N):
        if S[i:j] in S[j:N]:
            continue
        else:
            if j == max_length:
                break
            elif j > max_length:
                max_length = j-1
                max_reach = i+j-1
                break
print(max_length)

Submission status: Wrong Answer

Solution code:
def strTint(s):
    return ord(s)-96

alpha = {}
for i in range(97,97+26):
    alpha[chr(i)] = i - 96

def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    
    b = 27
    mod1 = 10**9+7
    mod2 = 10**9+9
    D = {}
    for i in range(N):
        H = strTint(S[i])
        H1 = H%mod1
        #H2 = H%mod2
        if not H1 in D:
            D[H1] = [1,i,i]
        for j in range(i+1,min(i+N//2+2,N)):
            H1 = (H1*b + strTint(S[j]))%mod1
            if not H1 in D:
                D[H1] = [j-i+1,i,i]
            else:
                D[H1][-1] = i
    
    ans = 0
    for i in D:
        L = D[i][0]
        tmp = 0
        if D[i][1] + L <= D[i][-1] and ans < L:
            ans = L
    g = time.time()
    print(g-star)
    print(ans)
    
main()

Submission status: Wrong Answer

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

ans = 0
left, right = 0, 1
while right < N:
    s = S[left:right]
    if s in S[left:]:
        ans = max(ans, len(s))
        right += 1
    else:
        left += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
#LCSRe i番目とj番目でそれぞれ終わるような共通文字列の長さ
#i < j であるi文字目とj文字目が等しいならLCSRe[i + 1][j + 1] = LCSRe[i][j] + 1
#res_lengthよりLCSReの更新した値が大なら、その時のindexをiへ、res_lengthも更新

def longestRepeatedSubstring(s): 
  n = len(s) 
  LCSRe = [[0 for _ in range(n + 1)] for _ 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 s[i - 1] == s[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 + s[i - 1] 
  return res_length
print(longestRepeatedSubstring(S))

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 0
max_reach = -1
for i in range(N):
    if i < max_reach:
        continue
    for j in range(max_length,N-max_length-i):
        if S[i:i+j] in S[i+j:N]:
            continue
        else:
            if j == max_length:
                break
            elif j > max_length:
                max_length = j-1
                max_reach = i+j-1
                break
print(max_length)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=0
  for j in range(i,n):
    t+=(ord(s[j])-97)*(100**(j-i))
    if 0<d[t]<i and j-i+1>ans:
      ans=j-i+1
    elif d[t]==0 and i+2*(j-i+1)<=n:
      d[t]=j
    
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=0
  for j in range(i,n):
    t+=(ord(s[j])-97)*(10**(j-i))
    if 0<d[t]<i and j-i+1>ans:
      ans=j-i+1
    elif d[t]==0 and i+2*(j-i+1)<=n:
      d[t]=j
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 0
max_reach = -1
for i in range(N):
    if i < max_reach:
        continue
    for j in range(max_length,N):
        if S[i:i+j] in S[i+j:N]:
            continue
        else:
            if j == max_length:
                break
            elif j > max_length:
                max_length = j-1
                max_reach = i+j-1
                break
print(max_length)

Submission status: Wrong Answer

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

ans = 0

# 2文字以上
for i in range(0, N - 3):
    for j in range(i + 2, N):
        if S[i:i + 2] == S[j:j + 2]:
            length, max_length = 2, j
            i, j = i + 1, j + 1
            while True:
                if i + 1 == max_length or j + 1 == N:
                    break
                else:
                    i, j = i + 1, j + 1
                    if S[i] == S[j]:
                        length += 1
                    else:
                        break
            if length > ans:
                ans = length

# 1文字
if ans == 0:
    for i in range(N - 1):
        s = S[i]
        if s in S[i + 1:]:
            ans = 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 0
max_reach = -1
for i in range(N):
    if i < max_reach:
        continue
    for j in range(max_length,N):
        if S[i:i+j] in S[i+j:N]:
            continue
        else:
            if j == max_length:
                break
            elif (j-1) > max_length:
                max_length = j-1
                max_reach = i+j-1
                break
print(max_length)

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 0
max_reach = -1
for i in range(N):
    if i < max_reach:
        continue
    for j in range(max_length,N):
        if S[i:i+j] in S[i+j:N]:
            continue
        else:
            if j == max_length:
                break
            elif (j-1) > max_length:
                max_length = j-1
            max_reach = i+j-1
            break
print(max_length)

Submission status: Wrong Answer

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

lenS = len(s)
#print(lenS)
ans = 0
for i in reversed(range(1,lenS//2+1)):
	for j in range(0, n-2*i):
		#tempS1 = s[j:j+i]
		#print(tempS)
		#tempS2 = s[j+i:]
		if (s[j:j+i] in s[j+i:]):
			ans = i
			break
			#print(s[j+i+k-1:j+2*i+k-1], i, j, k)
	if (ans > 0):
		break
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 1
max_reach = -1
for i in range(N):
    if i < max_reach:
        continue
    for j in range(max_length,N):
        if S[i:i+j] in S[i+j:N]:
            continue
        else:
            if (j-1) > max_length:
                max_length = j-1
            max_reach = i+j-1
            break
print(max_length)

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 1
max_reach = -1
for i in range(N):
    if i < max_reach:
        continue
    for j in range(max_length,N):
        if S[i:i+j] in S[i+j:N]:
            continue
        else:
            if (j-1) > max_length:
                max_length = j-1
            max_reach = i+j
            break
print(max_length)