Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Wrong Answer

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

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

ans = 0
for i in range(n-1):
	res = z_algo(s[i:])
	tmp = max(res[1:])
	ans = max(ans, tmp)
	if ans > (n-i) // 2:
		break

print(ans)

Submission status: Wrong Answer

Solution code:
class HashString:
    def __init__(self, S, l, r, b=2**16-1, p=2**16):
        self.S, self.l, self.r, self.b, self.p = S, l, r, b, p
        h = 0
        for i in range(l, r):
            h = (h*b+ord(S[i])) % p
        self.hash = h

    def pop_left(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h-ord(S[l])*pow(b, r-l-1, p)) % p
        self.l += 1

    def pop_right(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = ((h-ord(S[r-1])) * pow(b, p-2, p)) % p
        self.r -= 1

    def push_left(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h+ord(S[l-1])*pow(b, r-l, p)) % p
        self.l -= 1

    def push_right(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h*b+ord(S[r])) % p
        self.r += 1

    def shift_left(self):
        self.push_left()
        self.pop_right()

    def shift_right(self):
        self.push_right()
        self.pop_left()


def ok(k):
    # 長さkの連続部分列で重ならずに2回以上現れるものがある
    for i in range(n-2*k+1):
        hSi = HashString(S, i, i+k)
        hSj = HashString(S, i+k, i+2*k)
        if hSi.hash == hSj.hash:
            return True
        for j in range(i+2*k, n):
            hSj.shift_right()
            if hSi.hash == hSj.hash:
                return True
    return False


if __name__ == '__main__':
    n = int(input())
    S = list(input())

    # 二分探索でTrueになる最大のkを求める
    l, r = 0, n+1
    while r-l > 1:
        c = (l+r)//2
        if ok(c):
            l = c
        else:
            r = c
    print(l)

Submission status: Wrong Answer

Solution code:
class HashString:
    def __init__(self, S, l, r, b=2, p=2**6):
        self.S, self.l, self.r, self.b, self.p = S, l, r, b, p
        h = 0
        for i in range(l, r):
            h = (h*b+ord(S[i])) % p
        self.hash = h

    def pop_left(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h-ord(S[l])*pow(b, r-l-1, p)) % p
        self.l += 1

    def pop_right(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = ((h-ord(S[r-1])) * pow(b, p-2, p)) % p
        self.r -= 1

    def push_left(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h+ord(S[l-1])*pow(b, r-l, p)) % p
        self.l -= 1

    def push_right(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h*b+ord(S[r])) % p
        self.r += 1

    def shift_left(self):
        self.push_left()
        self.pop_right()

    def shift_right(self):
        self.push_right()
        self.pop_left()


def ok(k):
    # 長さkの連続部分列で重ならずに2回以上現れるものがある
    for i in range(n-2*k+1):
        hSi = HashString(S, i, i+k)
        hSj = HashString(S, i+k, i+2*k)
        if hSi.hash == hSj.hash:
            return True
        for j in range(i+2*k, n):
            hSj.shift_right()
            if hSi.hash == hSj.hash:
                return True
    return False


if __name__ == '__main__':
    n = int(input())
    S = list(input())

    # 二分探索でTrueになる最大のkを求める
    l, r = 0, n+1
    while r-l > 1:
        c = (l+r)//2
        if ok(c):
            l = c
        else:
            r = c
    print(l)

Submission status: Wrong Answer

Solution code:
class HashString:
    def __init__(self, S, l, r, b=2, p=10**9+7):
        self.S, self.l, self.r, self.b, self.p = S, l, r, b, p
        h = 0
        for i in range(l, r):
            h = (h*b+ord(S[i])) % p
        self.hash = h

    def pop_left(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h-ord(S[l])*pow(b, r-l-1, p)) % p
        self.l += 1

    def pop_right(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = ((h-ord(S[r-1])) * pow(b, p-2, p)) % p
        self.r -= 1

    def push_left(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h+ord(S[l-1])*pow(b, r-l, p)) % p
        self.l -= 1

    def push_right(self):
        S, l, r, b, p, h = self.S, self.l, self.r, self.b, self.p, self.hash
        self.hash = (h*b+ord(S[r])) % p
        self.r += 1

    def shift_left(self):
        self.push_left()
        self.pop_right()

    def shift_right(self):
        self.push_right()
        self.pop_left()


def ok(k):
    # 長さkの連続部分列で重ならずに2回以上現れるものがある
    p = 10**9+7
    t = pow(p, k, p)
    for i in range(n-2*k+1):
        hSi = HashString(S, i, i+k)
        hSj = HashString(S, i+k, i+2*k)
        if hSi.hash == hSj.hash:
            return True
        for j in range(i+2*k, n):
            hSj.shift_right()
            if hSi.hash == hSj.hash:
                return True
    return False


if __name__ == '__main__':
    n = int(input())
    S = list(input())

    # 二分探索でTrueになる最大のlを求める
    l, r = 0, n+1
    while r-l > 1:
        c = (l+r)//2
        if ok(c):
            l = c
        else:
            r = c
    print(l)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
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()))

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

n = inp()
s = input()
res = 0
for i in range(n-1):
    a = z_algo(s[i:])
    ln = n-i
    res = max(res, max(x for x in a[(ln+1)//2:]))
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*n
    ans = 0
    for i in range(1, n):
        for j in reversed(range(i)):
            if s[i] == s[j]:
                dp[j] += 1
                if 0 < j:
                    dp[j] += dp[j-1]
                if i-j < dp[j]:
                    dp[j] = i-j
                if ans < dp[j]:
                    ans = dp[j]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alphabet={moji:alphabetlist.index(moji) for moji in alphabetlist}

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

def condition(num):
    if num==0:
        return True

    data=[]
    x=0
    for i in range(num):
        x+=alphabet[S[i]]*26**i

    data.append((x,0))

    for i in range(0,N-num+1):
        if i==0:
            continue
        else:
            x=x//26+alphabet[S[i+num-1]]*26**(num-1)
            data.append((x,i))

    data.sort()
    min=data[0][1]
    max=data[0][1]
    for i in range(0,len(data)-1):
        if data[i][0]==data[i+1][0]:
            max=data[i+1][1]
        else:
            if max-min>=num:
                return True
            min=data[i+1][1]
            max=data[i+1][1]

    return False

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:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()
    S = [ord(i) for i in S]

    ln = len(S)

    def same(l):
        h1 = 0
        h2 = 0
        b1 = 26
        b2 = 27
        k1 = 1
        k2 = 1
        bl1 = power(b1, l, mod)
        bl2 = power(b2, l, mod)
        for i in range(l):  # 最初の検索対象のhashを作る
            ht = S[l - 1 - i]
            h1 += ht * k1
            h2 += ht * k2
            k1 *= b1
            k2 *= b2

            h1 %= mod2
            h2 %= mod2
            k1 %= mod2
            k2 %= mod2

        hl1 = [h1]
        hl2 = [h2]
        for i in range(l, ln):
            h1 = h1 * b1 + S[i] - S[i-l]* bl1
            h2 = h2 * b2 + S[i] - S[i-l]* bl2
            hl1.append(h1)
            hl2.append(h2)

        lnh = len(hl1)
        for i in range(lnh):
            for j in range(lnh):
                if i-j < l:
                    continue
                if hl1[i] == hl1[j] and hl2[i] == hl2[j]:
                    return True


        return False


    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A = 1234567
MOD = 1000000007

def ok(length):
    rolling_hash = 0
    head = pow(A, length, MOD)
    occurence = {}
    for i in range(n):
        rolling_hash = (rolling_hash * A + ord(s[i])) % MOD
        if i - length >= 0:
            rolling_hash = (rolling_hash - head * ord(s[i-length])) % MOD
        if rolling_hash not in occurence:
            occurence[rolling_hash] = []
        occurence[rolling_hash].append(i)

    for key in occurence:
        if occurence[key][-1] - occurence[key][0] >= length:
            return True
    return False

bottom, top = 0, n

while top - bottom > 1:
    mid = (top + bottom) // 2
    if ok(mid):bottom = mid
    else: top = mid

print(bottom)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()
    S = [ord(i) for i in S]

    ln = len(S)

    def same(l):
        for l1 in range(0, ln-l-l):
            l2 = l1 + l
            same_num = 0

            while l2 <= ln - l:
                if S[l2+same_num] == S[l1+same_num]:
                    same_num += 1
                    if same_num == l:
                        return True
                else:
                    same_num = 0
                    l2 += 1
        return False


    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N = iip(False)
    S = input()
    S = [i for i in S]

    ln = len(S)

    def same(l):
        for l1 in range(0, ln-l):
            for l2 in range(l1+l, ln - l):
                for same_num in range(l):
                    #print(l1, l2, same_num, S[l1+same_num], S[l2+same_num])
                    if not S[l1+same_num] == S[l2+same_num]:
                        break
                else:
                    return True
        return False

    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)
        #print(l, is_same)

        #print(l, is_same)
        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N = iip(False)
    S = input()
    S = [i for i in S]

    ln = len(S)

    mn = 0
    mx = ln // 2

    def same(l):
        for left in range(0, ln-l):
            for i in range(left+l, ln - l):
                for same_num in range(l):
                    if not S[i+same_num] == S[left+same_num]:
                        break
                else:
                    return True
        return False

    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        #print(l, is_same)
        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N = iip(False)
    S = input()
    S = [i for i in S]

    ln = len(S)

    mn = 0
    mx = ln // 2
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = False

        for left in range(0, ln-l):
            if is_same:
                break

            for i in range(left+l, ln - l):
                if is_same:
                    break
                for same_num in range(l):
                    if not S[i+same_num] == S[left+same_num]:
                        break
                else:
                    is_same = True


        #print(l, is_same)
        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N = iip(False)
    S = input()
    S = [i for i in S]
    #print(S)

    ln = len(S)

    mn = 0
    mx = ln
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = False
        for left in range(0, ln):
            if is_same:
                break
            same_num = 0

            i = left + l
            while True:
                if is_same:
                    break

                if i >= ln:
                    break
                #print(i)
                if S[i] == S[left+same_num]:
                    same_num += 1
                    i += 1
                    if same_num == l:
                        is_same = True
                        break
                else:
                    same_num = 0
                    i -= same_num
                    i += 1

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()