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

Solution (Python):
from collections import defaultdict


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    low = 0
    high = (N >> 1) + 1
    while high - low > 1:
        mid = (high + low) >> 1
        is_match = False
        m = N-mid+1
        d = defaultdict(list)
        for i in range(0, m):
            d[S[i:i+mid]].append(i)
        for v in d.values():
            if v[-1] - v[0] >= mid:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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

def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0
    for i in range(1, n):
        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
  
ans = 0
for i in range(n):
  z = Z_algo(s[i:])
  for i,zi in enumerate(z):
    ans = max(ans,min(i,z[i]))
    
print(ans)

Solution (Python):
import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = []
    for m in [999999937, 10**9+7]:
        b = random.randint(10000, m-1)
        rh = RollingHash(S, b=b, m=m)
        low = 0
        high = (N+1) // 2 + 1
        dmax = defaultdict(int)
        dmin = defaultdict(int)
        while high - low > 1:
            dmax.clear()
            dmin.clear()
            mid = (high + low) // 2
            for i in range(0, N-mid+1):
                h = rh.get(i, i+mid)
                dmax[h] = max(dmax[h], i+1)
                dmin[h] = max(dmin[h], N+1-i)
            is_match = False
            for h in dmax.keys():
                if dmax[h] - (N+2 - dmin[h]) >= mid:
                    is_match = True
                    break
            if is_match:
                low = mid
            else:
                high = mid
        ans.append(low)
    return min(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
n = int(input())
s = input()
ret = 0
for d in range(1, n - 1):
    l = 0
    for i in range(n - d):
        if s[i] == s[i + d]:
            l += 1
        else:
            l = 0
        ret = max(ret, min(l, d))
print(ret)

Solution (Python):
n = int(input())
s = input()
dp = [[0 for i in range(5001)] for j in range(5001)]

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

res = 0
for i in range(n):
	for j in range(n):
		if i >= j:
			continue
		x = min(dp[i][j], j-i)
		res = max(x,res)
print (res)

Solution (Python):
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]:
            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


def resolve():
    n = int(input())
    s = input()
    ans = 0
    for i in range(n):
        a = z_algo(s[i:])
        for index, j in enumerate(a):
            if j <= index:
                ans = max(ans, j)
    print(ans)


if __name__ == '__main__':
    resolve()

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

dp = [[0 for _ in range(N+1)] for _ 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
        else:
            dp[i][j] = 0

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

Solution (Python):
import math

def main():
    n = int(input())
    s = input()
    ans = solve(n, s)
    print(ans)


def solve(n, s):
    ans = 0
    for i in range(n - 1):
        tmp = Z(s[i:])
        t = [min(tmp[j], j)for j in range(n - i)]
        ans = max(ans, max(t))
        
    return ans

def Z(s):
    l = len(s)
    ans = [l for _ in range(l)]

    i, j = 1, 0
    while i < l:
        while i + j < l and s[j] == s[i + j] :
            j += 1
        ans[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ans[k] < j:
            ans[i + k] = ans[k]
            k += 1
        i += k
        j -= k
    return ans

if __name__ == '__main__':
    main()

Solution (Python):




n = int(input())
s = input()

s += '_'

ans = 0
for i in range(1, n):
    tmp = 0
    for j in range(i, n + 1):
        if s[j - i] == s[j]:
            tmp += 1
            if tmp >= i:
                ans = i
                break
        else:
            ans = max(ans, tmp)
            tmp = 0

print(ans)

Solution (Python):

import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            h2i[srh.calc(i, i+m)].append(i)

        for l in h2i.values():
            n = l[-1] - l[0]
            if n >= m:
                return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            n = l[-1] - l[0]
            if n >= m:
                return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S, rand=True, num=2)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        import random
        import math
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S, num=5)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        import random
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S, num=2)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    b = Bisect(f)
    return b.bisect_right(0, 1, N) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))



if __name__ == '__main__':
    main()

Solution (Python):
n,s=open(0);j=r=0
for i in range(int(n)):
    while (j<int(n))and(s[i:j] in s[j:]):j+=1
    r=max(r,j-i-1)
print(r)

Solution (Python):
I=input;n=int(I());s=I();j=r=0
for i in range(n):
    while (j<n)and(s[i:j] in s[j:]):j+=1
    r=max(r,j-i-1)
print(r)

Solution (Python):
I=input;n=int(I());s=I();j=1;r=[]
for i in range(n):
    while (j<n)and(s[i:j] in s[j:]):j+=1
    r.append(j-i-1)
print(max(r))

Solution (Python):
n = int(input())
s = input()
j = 1
result = []
for i in range(n):
    while (j < n-1) and (s[i:j] in s[j:]):
        j += 1
    result.append(j-i-1)
print(max(result))

Solution (Python):
n = int(input())
s = input()
j = 1
result = []
for i in range(n):
    while (j < n-1) and (s[i:j] in s[:i]+"0"+s[j:]):
        j += 1
    result.append(j-i-1)
print(max(result))

Solution (Python):
n = int(input())
s = input()
j = 1
result = [0]
for i in range(n):
    while (j < n-1) and (s[i:j] in s[:i]+"0"+s[j:]):
        j += 1
    result.append(j-i-1)
print(max(result))

Solution (Python):
n = int(input())
s = input()
j = 1
result = [0]
end = n//2 + 1
for i in range(n):
    while (j < n-1) and (s[i:j] in s[:i]+"0"+s[j:]):
        j += 1
    result.append(j-i-1)
print(max(result))

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

def zalgo(S):
  N = len(S)
  res = [0] * N
  res[0] = N
  i = 1
  j = 0
  while i < N:
    while i + j < N and S[j] == S[i + j]:
      j += 1
    res[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i + k < N and k + res[k] < j:
      res[i + k] = res[k]
      k += 1
    i += k
    j -= k
  return res

res = 0
for i in range(N):
  T = S[i:]
  lcp = zalgo(T)
  for j in range(len(T)):
    l = min(lcp[j],j)
    if res < l:
      res = l

print(res)

Solution (Python):


n = int(input())
s = input()

ans = 0
for i in range(1,n):
    chain = 0
    for j in range(n-i):
        if(s[j]==s[i+j]):
            chain+=1
            if(ans<chain):
                ans = min(chain,i)
                
        else:
            chain=0

print(ans)

Solution (Python):
def z_algorithm(s: str) -> list:
	n = len(s)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while i + j < n and s[j] == s[i + j]:
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < n and k + Z[k] < j:
			Z[i + k] = Z[k]
			k += 1
		i += k
		j -= k
	return Z


def main():
	n = int(input())
	s = input()
	ans = 0
	for i in range(n):
		t = max(min(i,x) for i,x in enumerate(z_algorithm(s[i:])))
		ans = max(ans, t)
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

def isok(d):    
    D={}    
    for i in range(N-d+1):
        x=S[i:i+d]
        if x not in D:  
            D[x]=i
        else:  
            if d<=i-D[x]:   
                return True
            else:           
                pass        
    else:
        return False

h=N
l=0
while h-l!=1:
    m=(h+l)/2
    if isok(m):
        l=m
    else:
        h=m
print l

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

def isok(d):    
    D={}    
    for i in range(N-d+1):
        x=S[i:i+d]
        if x not in D:  
            D[x]=i
        else:  
            if d<=i-D[x]:   
                return True
            else:           
                pass        
    else:
        return False

h=N
l=0
while h-l!=1:
    m=(h+l)/2
    if isok(m):
        l=m
    else:
        h=m
print l

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

def isok(d):    
    D={}    
    for i in range(N-d+1):
        x=S[i:i+d]
        if x not in D:  
            D[x]=i
        else:  
            if d<=i-D[x]:    
                return True
            else:           
                pass        
    else:
        return False

h=N
l=0
while h-l!=1:
    m=(h+l)/2
    if isok(m):
        l=m
    else:
        h=m
print l

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()
S=S[::-1]

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

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

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

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

ans=0
for d in range(1,N):
    cnt=0
    for s,t in zip(S[d:N],S[:N-d]):
        if s==t:
            cnt+=1
        else:
            ans=max(ans,min(d,cnt)) 
            cnt=0
    else:
        if 0<cnt:   
            ans=max(ans,min(d,cnt))    
print ans

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class RollingHash(object):
    _base1, _base2 = 1007, 1009
    _mod1, _mod2 = 10 ** 9 + 9, 10 ** 9 + 7

    def __init__(self,s):
        self._n=len(s)
        H1, H2 = [0] * (self._n + 1), [0] * (self._n + 1)
        P1, P2 = [1] * (self._n + 1), [1] * (self._n + 1)
        for i in range(self._n):
            H1[i + 1] = (H1[i] * self._base1 + ord(s[i])) % self._mod1
            H2[i + 1] = (H2[i] * self._base2 + ord(s[i])) % self._mod2
            P1[i + 1] = P1[i] * self._base1 % self._mod1
            P2[i + 1] = P2[i] * self._base2 % self._mod2
        self._H1, self._H2 = H1, H2
        self._P1, self._P2 = P1, P2

    def __len__(self):
        return self._n

    def __getitem__(self,x):
        l, r = x.start, x.stop;
        return ((self._H1[r] - self._P1[r - l] * self._H1[l] % self._mod1) % self._mod1,
                (self._H2[r] - self._P2[r - l] * self._H2[l] % self._mod2) % self._mod2)

from collections import defaultdict
def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

    def check(k):
        D=defaultdict(lambda:-1)
        for i in range(n-k+1):
            h=rh[i:i+k]
            if(D[h]!=-1):
                if(i-D[h]>=k): return True
            else:
                D[h]=i
        return False

    left = 0
    right = n
    while right - left > 1:
        mid = (left + right) // 2
        if check(mid):
            left = mid
        else:
            right = mid
    print(left)
resolve()

Solution (Python):
N = int(input())
S = list(input())
dp = [[0]*N for _ in range(N)]
dp[N-1][N-1] = 1
for i in range(N-1, -1, -1):
  if S[i] == S[-1]:
    dp[N-1][i] = 1

for i in range(N-1, -1, -1):
  if S[i] == S[-1]:
    dp[i][N-1] = 1

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

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