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()

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1, N//2+1):
    for j in range(N-2*i):
        #j~j+i, k~k+i(k>=j+i)
        one = S[j:j+i]
        if one in S[j+i:]:
            ans = i
            break
print(ans)

Submission status: Wrong Answer

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

len_s = len(s)
max_match = 0
for i in range(0, len_s):
    for j in range( len_s-2, i, -1 ):
        if s[i:j] in s[i+1:]:
            if len(s[i:j]) > max_match:
                max_match = len(s[i:j])
            break

print(max_match)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from math import ceil
N = int(input())
S = input()

res = 0
for st in range(len(S)-1):
    s = S[st:]
    lens = len(s)
    A = [0]*lens
    c = 0
    for i in range(1, lens):
        if i+A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j = max(0, c+A[c]-1)
            while i+j < lens and s[j] == s[i+j]:
                j += 1
            A[i] = j
    A[0] = lens

    res = max(res, max(A[ceil(len(A)/2):]))

print(res)

Submission status: Wrong Answer

Solution code:
from math import ceil
N = int(input())
S = input()

res = 0
for st in range(len(S)-1):
    s = S[st:]
    lens = len(s)
    A = [0]*lens
    c = 0
    for i in range(1, lens):
        if i+A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j = max(0, c+A[c]-1)
            while i+j < lens and s[j] == s[i+j]:
                j += 1
            A[i] = j
    A[0] = lens

    res = max(res, max(A[ceil(len(A)/2):]))

print(res)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.mask30 = (1 << 30) - 1
        self.mask31 = (1 << 31) - 1
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 127) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)
 
        for i in range(self.length):
            self.hash[i+1] = self.calcmod(self.mul(self.hash[i], self.base) + ord(s[i]))
            self.pow[i+1] = self.calcmod(self.mul(self.pow[i], self.base))
    
    def mul(self, l, r):
        lu = l >> 31
        ld = l & self.mask31
        ru = r >> 31
        rd = r & self.mask31
        middle = ld * ru + lu * rd
        return ((lu * ru) << 1) + ld * rd + ((middle & self.mask30) << 31) + (middle >> 30)
    
    def calcmod(self, val):
        val = (val & self.mod) + (val >> 61)
        if val > self.mod:
            val -= self.mod
        return val
 
    def get(self, l, r):
        t = self.calcmod(self.hash[r] - self.mul(self.hash[l], self.pow[r-l]) + self.mod)
        return t
 
n = int(input())
s = input()
RH = RollingHash(s)
 
def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

l = 0; r = n // 2 + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

Submission status: Wrong Answer

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

for x in range(len(s)):
    i = x + 1
    while j+i < len(s):
        j = x
        while i+j < len(s) and s[j] == s[j+i] and j < i:
            j += 1
        maxx = max(maxx, j)
        i += 1

print(maxx)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

class FastRollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
s = input()
RH = RollingHash(s)

def check(l):
    place = {}
    for i in range(0, n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if l - place[hs] > 0:
                return True
        else:
            place[hs] = i
    return False

l = 0; r = n // 2 + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

class FastRollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
s = input()
RH = FastRollingHash(s)

def check(l):
    place = {}
    for i in range(0, n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if l - place[hs] > 0:
                return True
        else:
            place[hs] = i
    return False

l = 0; r = n // 2 + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

class FastRollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
s = input()
RH = FastRollingHash(s)

for i in range(n // 2, -1, -1):
    place = {}
    for j in range(0, n - i + 1):
        hs = RH.get(j, j + i)
        if hs in place:
            if i - place[hs] > 0:
                print(i)
                exit()
        else:
            place[hs] = j
print(0)

Submission status: Wrong Answer

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

for i in range(len(s)):
    pattern = []
    for j in range(len(s)):
        pattern.append(0)
        for num, (k, u) in enumerate(zip(s[i:], s[i+j:])):
            if k == u:
                pattern[j] += 1
            else:
                break
    if max(pattern[1:]) > maxx:
        maxx = max(pattern[1:])

print(maxx)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input()) + ["!"]
dp = [[0] * N for _ in range(N)]
if S[0] == S[1]:
  dp[0][1] = 1
res = 0
for i in range(N):
  for j in range(i, N):
    res = max(dp[i][j], res)
    if i == N - 1 or j == N - 1:
      continue
    if S[i + 1] == S[j + 1] and j - i >= dp[i][j]:
      dp[i + 1][j + 1] = dp[i][j] + 1
    else:
      dp[i + 1][j + 1] = 0
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input()) + ["!"]
dp = [[0] * N for _ in range(N)]
if S[0] == S[1]:
  dp[0][1] = 1
res = 0
for i in range(N):
  for j in range(i, N):
    res = max(dp[i][j], res)
    if i == N - 1 or j == N - 1:
      continue
    if S[i + 1] == S[j + 1] and j - i > dp[i][j]:
      dp[i + 1][j + 1] = dp[i][j] + 1
    else:
      dp[i + 1][j + 1] = 0
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input()) + ["!"]
dp = [[0] * (N + 1) for _ in range(N)]
if S[0] == S[1]:
  dp[0][1] = 1
for i in range(N - 1):
  for j in range(i + 1, N):
    p = dp[i][j + 1]
    q = dp[i + 1][j]
    if j + 1 - dp[i][j + 1] + 1 <= i:
      p = 0
    if j - dp[i + 1][j] + 1 <= i + 1:
      q = 0
    if S[i + 1] == S[j + 1]:
      r = dp[i][j] + 1
      if j - dp[i][j] + 1 <= i + 1:
        r = 0
      dp[i + 1][j + 1] = max(p, q, r)
    else:
      dp[i + 1][j + 1] = max(p, q)
res = 0
for l in dp:
  res = max(l + [res])
print(res)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

    rt = 0
    lt = 0

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

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

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

                lt = k
                rt = i - 1
    return Z

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

print(ans)

Submission status: Wrong Answer

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

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

    print(max_string)
    return 0

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

Submission status: Wrong Answer

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

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

    print(max_string)
    return 0

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

Submission status: Wrong Answer

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

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

    print(max_string)
    return 0

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

Submission status: Wrong Answer

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

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

    print(max_string)
    return 0

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

def find_max_duplication(string):
    possible_max_len = len(string) // 2
    is_odd = len(string) % 2
    for i in range(possible_max_len, 0, -1):
        find, target = string[:i], string[i:]
        # if is_odd:
        #     find, target = string[:possible_max_len], string[possible_max_len:]
        # else:
        #     find, target = string[:possible_max_len], string[possible_max_len:]
        if find in target:
            print(len(find))
            break
        print(0)


if __name__ == '__main__':
    string = receive_string()
    find_max_duplication(string)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

p = 0
max_len = 0
while p < len(S)-1:
	q = p+1
	while S[p] != S[q]:
		q += 1
		if q >= len(S):
			break
	if q >= len(S):
		p += 1
		continue
	dir = 0
	while (p+dir < q) and (S[p + dir] == S[q + dir]):
		dir += 1
		if q+dir >= len(S):
			break
	if max_len < dir:
		max_len = dir
	p += dir

print(max_len)

Submission status: Wrong Answer

Solution code:

import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    res = 0
    for i in range(n-1, -1, -1):
        for j in range(n-1, i, -1):
            if s[i] == s[j]:
                if j == n-1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i+1][j+1]+1
                res = max(res, dp[i][j])
    print(res)


main()

Submission status: Wrong Answer

Solution code:

import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'
    dp = [[-1] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

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

    max_val = 0
    for i in range(n-1):
        for j in range(i, n):
            length = dp[i][j]
            # i: 0
            # length: 2
            # j: 2
            if i + length - 1 < j:
                max_val = max(max_val, dp[i][j])
    if max_val == 0:
        print(0)
    else:
        print(max_val)


main()

Submission status: Wrong Answer

Solution code:

import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'
    dp = [[-1] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

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

    max_val = 0
    for i in range(n-1):
        for j in range(i, n):
            length = dp[i][j]
            # i: 0
            # length: 2
            # j: 2
            if i + length - 1 < j:
                max_val = max(max_val, dp[i][j])
    if max_val == 0:
        print(0)
    else:
        print(max_val)


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC141 E
#Z-algorithm

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    L,R = 0,0
    for i in range(1, n):
        if i >= R: #過去の結果が使えない
            L = R = i
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
        elif Z[i-L] < R-i:#過去の結果が全て使える
            Z[i] = Z[i - L]
        else:#過去の結果が一部使える
            L = i
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
    return Z

n = I()
s = input()
ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j,z in enumerate(Z):
        if j <= z:
            continue
        ans = max(ans,z)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC141 E
#Z-algorithm

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    L,R = 0,0
    for i in range(1, n):
        if i >= R: #過去の結果が使えない
            L = R = i
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
        elif Z[i-L] < R-i:#過去の結果が全て使える
            Z[i] = Z[R - L]
        else:#過去の結果が一部使える
            L = i
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
    return Z

n = I()
s = input()
ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j,z in enumerate(Z):
        if j < z:
            continue
        ans = max(ans,z)
print(ans)