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: Time Limit Exceeded

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+1):
                for same_num in range(l):
                    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)

        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: Time Limit Exceeded

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+1):
                same_num = 0

                while True:
                    if S[l1+same_num] == S[l2+same_num]:
                        same_num += 1
                        if same_num == l:
                            return True
                    else:
                        break

        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: Time Limit Exceeded

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+1):
                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: Time Limit Exceeded

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_fin = left + l
            i = i_fin
            while i_fin < ln:
                if is_same:
                    break

                if i >= ln:
                    break
                #print(i)
                if S[i] == S[left+same_num]:
                    #print(left, same_num, S[i], S[left+same_num])
                    same_num += 1
                    i += 1

                    if same_num == l:
                        is_same = True
                        break
                else:
                    same_num = 0
                    i_fin += 1
                    i = i_fin

        #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: Time Limit Exceeded

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)
    #print(ln)
    ans = 0
    for left in range(0, ln):
        for right in range(left+1, ln):
            is_same = False
            l = right - left
            if l <= ans:
                continue
            if l > ln/2:
                continue

            same_num = 0

            for i in range(right, ln):
                #print(l, left, right, i, same_num, S[i], S[left+same_num])
                if S[i] == S[left+same_num]:
                    same_num += 1
                    if same_num == l:
                        is_same = True
                        break
                else:
                    same_num = 0

            if is_same:
                ans = max(ans, l)

    return ans


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

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: Time Limit Exceeded

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)
    ans = 0
    for left in range(0, ln):
        for right in range(left+1, ln):
            is_same = False
            l = right - left
            same_num = 0

            for i in range(right, ln):
                #print(l, left, right, i, same_num, S[i], S[left+same_num])
                if S[i] == S[left+same_num]:
                    same_num += 1
                    if same_num == l:
                        is_same = True
                        break
                else:
                    same_num = 0

            if is_same:
                ans = max(ans, l)
            else:
                left = right-1

    return ans


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

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: Time Limit Exceeded

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

def search(x):
    for i in range(n-2*x+1):
        
        if s[i:i+x] in s[i+x:]:


            return True

    return False

l = 0
r = n//2+1
while r > l+1:
    mid = (r+l)//2
    if search(mid):
        l = mid
    else:
        r = mid
print(l)

Submission status: Time Limit Exceeded

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

def search(x):
    for i in range(n-x):
        
        if s[i:i+x] in s[i+x:]:


            return True

    return False

l = -1
r = n+1
while r > l+1:
    mid = (r+l)//2
    if search(mid):
        l = mid
    else:
        r = mid
print(l)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            if i+z[i-c] < c+z[c]:
                z[i] = z[i-c]
            else:
                j = max(0,c+z[c]-i)
                while i+j < n and s[j] == s[i+j]:
                    j += 1
                z[i] = j
                c = i
        return z
    n = I()
    s = input()
    l = 0
    r = n
    while r > l+1:
        m = (l+r) >> 1
        for i in range(n+1-m):
            t = s[i:i+m]
            z = Z_algorithm(t+s)[len(t):]
            k = 0
            cnt = 0
            while k < len(s)-len(t)+1 and cnt < 2:
                if z[k] >= len(t):
                    cnt += 1
                    k += len(t)
                else:
                    k += 1
            if cnt >= 2:
                l = m
                break
        else:
            r = m
    print(l)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            if i+z[i-c] < c+z[c]:
                z[i] = z[i-c]
            else:
                j = max(0,c+z[c]-i)
                while i+j < n and s[j] == s[i+j]:
                    j += 1
                z[i] = j
                c = i
        return z
    n = I()
    s = input()
    l = 0
    r = n
    while r > l+1:
        m = (l+r) >> 1
        for i in range(n+1-m):
            t = s[i:i+m]
            z = Z_algorithm(t+s)[len(t):]
            k = 0
            cnt = 0
            while k < len(s) and cnt < 2:
                if z[k] >= len(t):
                    cnt += 1
                    k += len(t)
                else:
                    k += 1
            if cnt >= 2:
                l = m
                break
        else:
            r = m
    print(l)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            if i+z[i-c] < c+z[c]:
                z[i] = z[i-c]
            else:
                j = max(0,c+z[c]-i)
                while i+j < n and s[j] == s[i+j]:
                    j += 1
                z[i] = j
                c = i
        return z
    n = I()
    s = input()
    l = 0
    r = n
    while r > l+1:
        m = (l+r) >> 1
        for i in range(n-m):
            t = s[i:i+m]
            z = Z_algorithm(t+s)[len(t):]
            k = 0
            cnt = 0
            while k < len(s) and cnt < 2:
                if z[k] >= len(t):
                    cnt += 1
                    k += len(t)
                else:
                    k += 1
            if cnt >= 2:
                l = m
                break
        else:
            r = m
    print(l)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

    for i in range(n-1):
        for j in range(i+1,n):
            for cnt in range(min(j-i,n-j)):
                if s[i+cnt] == s[j+cnt]:
                    continue
                else:
                    cnt -= 1
                    break
            ans = max(ans,cnt+1)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(ord,list(input())))
for i in range(n):s[i]-=97

from random import randint
roli_mod=1370757747362922367
roli_r=randint(2,roli_mod-2)
roli=[0]
roli_rr=1
for i in range(n):
  roli.append((roli[-1]+roli_rr*s[i])%roli_mod)
  roli_rr*=roli_r
  roli_rr%=roli_mod
def roli_hash(i,j):return ((roli[j+1]-roli[i]+roli_mod)%roli_mod)*pow(roli_r,roli_mod-1-i,roli_mod)%roli_mod
def roli_check(i1,j1,i2,j2):return roli_hash(i1,j1)==roli_hash(i2,j2)

ans=0
for i in range(1,n+1):
  d={}
  for j in range(n-i+1):
    h=roli_hash(j,j+i-1)
    if h in d:
      if j-d[h]>=i:
        ans=i
        break
    else:d[h]=j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
nn = int(input())
ss = input()

ans = 0

for i in range(nn-1):
  n = nn-i
  s = ss[i:]
  a = [0]*n
  a[0] = n
  i, j = 1, 0
  while i < n:
    while i+j < n and s[j] == s[i+j]:
      j += 1
    a[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i+k < n and k+a[k] < j:
      a[i+k] = a[k]
      k += 1
    i += k
    j -= k
  for p in range(1, n-1):
    a[p] = min([p, a[p]])
  sub = max(a[1:])
  if ans < sub:
    ans = sub
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(map(ord,list(input())))
dp=[n*[0]for _ in range(n)]
for i in range(n):
  if s[i]==s[0]:
    dp[i][0]=dp[0][i]=1
for i in range(1,n):
  for j in range(1,n):
    if s[i]==s[j]:
      dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if i<j-dp[i][j]+1:ans=max(ans,dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
dp=[n*[0]for _ in range(n)]
for i in range(n):
  if s[i]==s[0]:
    dp[i][0]=dp[0][i]=1
for i in range(1,n):
  for j in range(1,n):
    if s[i]==s[j]:
      dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if i<j-dp[i][j]+1:ans=max(ans,dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

#二分探索
N = ir()
S = sr()

def check(x):
    # x 文字
    bl = False
    for i in range(N):
        for j in range(i+x, N):
            if S[i:i+x] == S[j:j+x]:
                bl = True
    return bl

ok = 0; ng = N
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

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


n = int(input())
s = input()
ans = 0
for i in range(n):
    lcp = Z_algo(s[i:])
    for j in range(len(lcp)):
        tmp = min(j, lcp[j])
        ans = max(ans, tmp)
print(ans)