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):
N = int(input())
S = input().strip()

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

for i in reversed(range(N)):
    for j in reversed(range(N)):
        if i >= j:
            continue
        if S[i] != S[j]:
            dp[i][j] = 0
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min([dp[i][j], j-i])
        ans = max(ans, now)

print(ans)

Solution (Python):
import sys


def main():
    N = int(input())
    s = input()
    a,i,j = 0,0,1
    
    while j < N:
        if s[i:j] in s[j:]:
            a = max(a,j-i)
            j += 1
        else:
            i += 1
        if i == j:
            j += 1
            
    print(a)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

n = int(input())
s = np.array(list(input()))

l = s.size

dp = np.zeros(l, dtype=np.int16)
ans = 0
for i, e in enumerate(s, 1):
    dp_prev = dp.copy()
    mx = np.arange(1, l + 1) - i
    idx = np.hstack([np.full(i, False), s[i:] == e]).astype(np.bool)
    idx_prev = np.roll(idx, -1)
    dp = np.zeros(l, dtype=np.int16)
    dp[idx] = np.minimum(dp_prev[idx_prev] + 1, mx[idx])
    ans = max(ans, dp.max())

print(ans)

Solution (Python):
import numpy as np

n = int(input())
s = np.array(list(input()))

l = s.size

dp = np.zeros(l, dtype=np.int16)
ans = 0
for i, e in enumerate(s, 1):
    dp_prev = dp[:]
    mx = np.arange(1, l + 1) - i
    idx = np.hstack([np.full(i, False), s[i:] == e]).astype(np.bool)
    idx_prev = np.hstack([np.full(i-1, False), s[i:] == e, False]).astype(np.bool)
    dp = np.zeros(l, dtype=np.int16)
    dp[idx] = np.minimum(dp_prev[idx_prev] + 1, mx[idx])
    ans = max(ans, dp.max())

print(ans)

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

l = len(s)

dp = [[0] * (l + 1) for _ in range(l + 1)]

ans = 0
for i, ei in enumerate(s, 1):
    for j, ej in enumerate(s[i:], i+1):
        if ei == ej:
            dp[i][j] = min(dp[i-1][j-1] + 1, j - i)
            ans = max(ans, dp[i][j])

print(ans)

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

l = len(s)

dp = [[0] * (l + 1) for _ in range(l + 1)]
dp[0][0] = 1

ans = 0
for i, ei in enumerate(s, 1):
    for j, ej in enumerate(s[i:], i+1):
        if ei == ej:
            dp[i][j] = min(dp[i-1][j-1] + 1, j - i)
            ans = max(ans, dp[i][j])

print(ans)

Solution (Python):

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

x = 0
for i in range(n):
    s_ = s[:i+1]
    if s_[i - x:] in s_[: i - x]:
        x += 1

print(x)

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

N = int(input())
S = input()
MAX = 0

for i in range(N-1):
    A = z_algo(S[i:])
    for j in range(len(A)):
        if MAX < A[j] and A[j] <= j:
            MAX = A[j]

print(MAX)

Solution (Python):
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    b,M=37,998244353
    x,y=1,0
    f,h=[1],[0]
    f_add,h_add=f.append,h.append
    for c in input():
        x=x*b%M
        f_add(x)
        y=(y*b+c)%M
        h_add(y)
    ok,ng=0,n//2+1
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(n-mid+1):
            k=(h[i+mid]-h[i]*f[mid])%M
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    b,M=37,998244353
    x,y=1,0
    f,h=[1],[0]
    f_add,h_add=f.append,h.append
    for i,c in enumerate(input()):
        x=x*b%M
        f_add(x)
        y=(y*b+c)%M
        h_add(y)
    ok,ng=0,n//2+1
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(n-mid+1):
            k=(h[i+mid]-h[i]*f[mid])%M
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    b=37
    M=998244353
    x,y=1,0
    f=[x]*(n+2)
    h=[y]*(n+2)
    for i,c in enumerate(input()):
        f[i+1]=x=x*b%M
        h[i+1]=y=(y*b+c)%M
    ok,ng=0,n//2+1
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(0,n-mid+1):
            k=(h[i+mid]-h[i]*f[mid])%M
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    b=129
    M=2**61-1
    x,y=1,0
    f=[x]*(n+2)
    h=[y]*(n+2)
    for i,c in enumerate(input()):
        f[i+1]=x=x*b%M
        h[i+1]=y=(y*b+c)%M
    ok,ng=0,n//2+1
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(0,n-mid+1):
            k=(h[i+mid]-h[i]*f[mid])%M
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Solution (Python):
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def main():
    n=int(input())
    s=RollingHash(input())
    ok,ng=0,n
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(0,n-mid+1):
            k=s.get(i,i+mid)
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Solution (Python):
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def check(x):
    d={}
    for i in range(0,n-x+1):
        k=s.get(i,i+x)
        if k in d:
            if d[k]+x<=i:
                return True
        else:
            d[k]=i
    return False
n=int(input())
s=RollingHash(input())
ok,ng=0,n
while ng-ok>1:
    mid=ok+ng>>1
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Solution (Python):
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def check(x):
    d={}
    for i in range(0,n-x+1):
        k=s.get(i,i+x)
        if k in d:
            if d[k]+x<=i:
                return True
        else:
            d[k]=i
    return False
n=int(input())
s=RollingHash(input())
ok,ng=0,n
while ng-ok>1:
    mid=ok+ng>>1
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Solution (Python):
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        self.f=f=[1]*(n+1)
        self.h=h=[0]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=f[i]*b%M
            h[i+1]=(h[i]*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
n=int(input())
s=RollingHash(input())
for i in range(1,n):
    d={}
    for j in range(0,n-i+1):
        k=s.get(j,j+i)
        if k in d:
            if d[k]+i<=j:
                break
        else:
            d[k]=j
    else:
        print(i-1)
        break

Solution (Python):
from collections import deque
import copy

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

dq_s = deque([])
for x in s:
    dq_s.append(x)

dq_s_shift = copy.deepcopy(dq_s)

ans = 0

for i in range(n):
    dq_s_shift.appendleft('_')
    count = 0
    
    

    for j in range(i+1,n):
        if dq_s[j] == dq_s_shift[j]:
            count += 1
        else:
            count = 0
        if count >= ans and count <= i+1:
            ans = count
    
    

print(ans)

Solution (Python):
def z_algo(s):
    """文字列sについて、各iについて「SとS[i:|S|]の最長共通接頭辞の長さ」
    を記録した配列をO(|S|)で構築する
    """
    res = [0] * len(s)
    res[0] = len(s)
    i = 1
    j = 0
    while i < len(s):
        while i + j < len(s) and s[j] == s[i + j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res


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

ans = 0
for i in range(n):
    t = z_algo(s[i:n])
    for i, num in enumerate(t):
        ans = max(ans, min(num, i))
print(ans)

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

n = int(input())
s = input().rstrip()

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

ans = 0

for i in range(n):
    s_ = s[i:]
    z_s = z_algo(s_)
    for j in range(len(z_s)):
        ans = max(ans, min(j, z_s[j]))

print(ans)

Solution (Python):
n=int(input())
s=input()
r=n//2
l=-1
while r-l>1:
  mid=(r+l)//2
  d=dict()
  ok=False
  for i in range(n-mid):
    ss=s[i:i+mid+1]
    if ss not in d:
      d[ss]=i
    else:
      if d[ss]+mid<i:
        ok=True
  if ok:
    l=mid
  else:
    r=mid
print(r)

Solution (Python):
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]:
        	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
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	for j,zj in enumerate(tmp):
		if j+1 > zj:
			ans = max(ans,zj)

print(ans)

Solution (Python):
n=int(input())
s=input()
import collections
l=0
h=n//2+1
ans=0
while h>l+1:
    t=(h+l)//2
    d=collections.defaultdict(int)
    for i in range(n-t+1):
        c=s[i:i+t]
        if d[c]==0:
            d[c]=i+1
        else:
            if d[c]+t<=i+1:
                l=t
                break
    else:
        h=t
print(l)

Solution (Python):
BASE = 9973
MOD1 = 10 ** 9 + 7
MOD2 = 998244353


class RollingHash:
    
    
    def __init__(self, S, MOD):
        self.MOD = MOD
        
        self.acc = [0]
        a = 0
        
        for i, c in enumerate(S):
            h = ord(c) - ord("a") + 1
            offset = pow(BASE, i, MOD)
            a = (a + (h * offset)) % MOD
            self.acc.append(a)

    
    
    def hash(self, i, j):
        
        
        offset = pow(BASE, i, self.MOD)
        
        
        offset_inv = pow(offset, self.MOD - 2, self.MOD)
        return ((self.acc[j] - self.acc[i]) * offset_inv) % self.MOD


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


rolling1 = RollingHash(S, MOD1)
rolling2 = RollingHash(S, MOD2)









ok = 0

ng = N
while ng - ok > 1:
    
    m = (ok + ng) // 2

    
    
    former_cache1 = set()
    former_cache2 = set()
    p = False
    
    for i in range(m, N):
        
        j = i + m
        
        if j > N:
            break
        
        former_cache1.add(rolling1.hash(i - m, i))
        former_cache2.add(rolling2.hash(i - m, i))
        
        
        if (
            rolling1.hash(i, j) in former_cache1
            and rolling2.hash(i, j) in former_cache2
        ):
            p = True
    
    if p:
        ok = m
    else:
        ng = m

ans = ok

print(ans)

Solution (Python):
BASE = 9973
MOD = 2 ** 61 - 1


class RollingHash:
    
    
    def __init__(self, S):
        
        self.acc = [0]
        a = 0
        
        for i, c in enumerate(S):
            h = ord(c) - ord("a") + 1
            offset = pow(BASE, i, MOD)
            a = (a + (h * offset)) % MOD
            self.acc.append(a)

    
    
    def hash(self, i, j):
        
        
        offset = pow(BASE, i, MOD)
        
        
        offset_inv = pow(offset, MOD - 2, MOD)
        return ((self.acc[j] - self.acc[i]) * offset_inv) % MOD


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


rolling = RollingHash(S)









ok = 0

ng = N
while ng - ok > 1:
    
    m = (ok + ng) // 2

    
    
    former_cache = set()
    p = False
    
    for i in range(m, N):
        
        j = i + m
        
        if j > N:
            break
        
        former_cache.add(rolling.hash(i - m, i))
        
        if rolling.hash(i, j) in former_cache:
            p = True
        
    
    if p:
        ok = m
    else:
        ng = m

ans = ok

print(ans)

Solution (Python):
n=int(input())
s=input()
l=0
r=n
while r-l>1:
  mid=(r+l)//2
  dic={}
  flag=False
  for i in range(n-mid+1):
    tmp=s[i:i+mid]
    if tmp not in dic:
      dic[tmp]=i+mid
    else:
      if dic[tmp]<=i:
        flag=True
        break
  if flag:
    l=mid
  else:
    r=mid
print(l)

Solution (Python):
n = int(input())
s = input()
"""
def lcs(s, t):
    ls, lt = len(s), len(t)
    dp = [[0] * (lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
    return dp[ls][lt]
"""
def z_algorithm(s):
    ls = len(s)
    Z = [0] * ls
    Z[0] = ls
    i, j = 1, 0
    while i < ls:
        while i + j < ls and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < ls and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
for i in range(n):
    
    z = z_algorithm(s[i:])
    for j, zj in enumerate(z):
        if j+1 > zj:
            ans = max(ans, zj)
    
print(ans)

Solution (Python):


import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
S = input()

def Z_alg(s):
    n = len(s)
    z = [0]*n
    z[0] = n

    L = 0
    R = 0
    for i in range(1, n):
        if(i >= R):  
            L = i
            R = i
            while(R < n and s[R-L] == s[R]):
                R += 1
            z[i] = R-L
        elif(z[i-L] < R-i):  
            z[i] = z[i-L]
        else:  
            L = i
            while(R < n and s[R-L] == s[R]):
                R += 1
            z[i] = R-L

    return z

ans = 0
for i in range(N):
    z = Z_alg(S[i:])
    
    for j, l in enumerate(z):
        ans = max(ans, min(j, l))

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline   
sys.setrecursionlimit(100000000)
from functools import lru_cache
INF = 1000000000
MOD = 10**9+7

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

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

if __name__=='__main__':
    main()

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



class RollingHash:
    
    def __init__(self, seq, base=10 ** 9 + 7, mod=2 ** 89 - 1):
        """
        :param str|typing.Sequence[int] seq:
        :param int base:
        :param int mod:
        """
        if isinstance(seq, str):
            self._seq = seq = list(map(ord, seq))
        else:
            self._seq = seq
        self._base = base
        self._mod = mod

        hashes = [0] * (len(seq) + 1)
        power = [1] * (len(seq) + 1)
        for i, c in enumerate(seq):
            hashes[i + 1] = (hashes[i] * base + c) % mod
            power[i + 1] = power[i] * base % mod
        self._hashes = hashes
        self._power = power

    def get(self, L, r):
        """
        [L, r) のハッシュ値を取得します
        :param int L:
        :param int r:
        """
        if L >= r:
            return 0
        return (self._hashes[r] - self._hashes[L] * self._power[r - L]) % self._mod


N = int(sys.stdin.buffer.readline())
S = sys.stdin.buffer.readline().decode().rstrip()
rh = RollingHash(S)


def test(size):
    l = 0
    r = size
    hist = {}
    while r <= N:
        h = rh.get(l, r)
        if h in hist:
            pl, pr = hist[h]
            if pr <= l:
                return True
        else:
            hist[h] = l, r
        l += 1
        r += 1
    return False


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

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



class RollingHash:
    
    def __init__(self, seq, base=10 ** 9 + 7, mod=2 ** 89 - 1):
        """
        :param str|typing.Sequence[int] seq:
        :param int base:
        :param int mod:
        """
        if isinstance(seq, str):
            self._seq = seq = list(map(ord, seq))
        else:
            self._seq = seq
        self._base = base
        self._mod = mod

        hashes = [0] * (len(seq) + 1)
        power = [1] * (len(seq) + 1)
        for i, c in enumerate(seq):
            hashes[i + 1] = (hashes[i] * base + c) % mod
            power[i + 1] = power[i] * base % mod
        self._hashes = hashes
        self._power = power


    
    def get(self, L, r):
        """
        [L, r) のハッシュ値を取得します
        :param int L:
        :param int r:
        """
        if L >= r:
            return 0
        return (self._hashes[r] - self._hashes[L] * self._power[r - L]) % self._mod


N = int(sys.stdin.buffer.readline())
S = sys.stdin.buffer.readline().decode().rstrip()
rh = RollingHash(S)



def test(size):
    l = 0
    r = size
    hist = {}
    while r <= N:
        h = rh.get(l, r)
        if h in hist:
            pl, pr = hist[h]
            if pr <= l:
                return True
        else:
            hist[h] = l, r
        l += 1
        r += 1
    return False


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

Solution (Python):

n=int(input())
s=input()
def Zalgo(s):
    ans=0
    L=len(s)
    Z=[0]*L
    Z[0]=L
    i=1;j=0
    while i<L:
        while i+j < L and s[j]==s[i+j]:j+=1
        Z[i]=j
        if Z[i] > ans and Z[i]<=i:
            ans=Z[i]
        if j == 0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            k+=1
        i+=k
        j-=k
    return ans
ans=0
for i in range(n):
    p=Zalgo(s[i:])
    if p > ans:
        ans=p
print(ans)

Solution (Python):
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Solution (Python):
import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SuffixArray:

    class SparseTable:

        def __init__(self, A, func):
            self.N = len(A)
            self.func = func
            h = 0
            while 1<<h < self.N:
                h += 1
            self.dat = list2d(h, 1<<h, 0)
            self.height = [0] * (self.N+1)

            for i in range(2, self.N+1):
                self.height[i] = self.height[i>>1] + 1
            for i in range(self.N):
                self.dat[0][i] = A[i]
            for i in range(1, h):
                for j in range(self.N):
                    self.dat[i][j] = self.func(self.dat[i-1][j], self.dat[i-1][min(j+(1<<(i-1)), self.N-1)])
            
        def get(self, l, r):
            """ 区間[l,r)でのmin,maxを取得 """

            a = self.height[r-l]
            return self.func(self.dat[a][l], self.dat[a][r-(1<<a)])

    def __init__(self, S):
        self.k = 1
        self.S = S
        self.N = len(S)
        self.rank = [0] * (self.N+1)
        self.tmp = [0] * (self.N+1)
        self.sa = [0] * (self.N+1)
        self.build_sa()

    
    
    
    
    
    
    

    def compare_sa(self, i, j):
        """ saの比較関数 """

        
        if self.rank[i] == self.rank[j]: res1 =  0
        elif self.rank[i] < self.rank[j]: res1 =  -1
        else: res1 = 1
        
        ri = self.rank[i+self.k] if i + self.k <= self.N else -1
        rj = self.rank[j+self.k] if j + self.k <= self.N else -1
        if ri == rj: res2 = 0
        elif ri < rj: res2 = -1
        else: res2 = 1
        
        return res1 or res2

    def build_sa(self):
        """ Suffix Arrayの構築 """
        

        
        
        
        

        
        
        
        
        
        

        
        
        
        
        
        
        suffix_arr = [(self.S[i:], i) for i in range(self.N+1)]
        suffix_arr.sort()
        for i in range(self.N+1):
            self.sa[i] = suffix_arr[i][1]

    def build_lcp(self):
        """ LCP配列の構築 """

        self.lcp = [0] * (self.N+1)
        self.rsa = [0] * (self.N+1)
        for i in range(self.N+1):
            self.rsa[self.sa[i]] = i
        h = 0
        self.lcp[0] = 0
        for i in range(self.N):
            
            j = self.sa[self.rsa[i]-1]

            
            if h > 0:
                h -= 1
            while j+h < self.N and i+h < self.N:
                if self.S[j+h] != self.S[i+h]:
                    break
                h += 1
            self.lcp[self.rsa[i]-1] = h

        
        self.st = self.SparseTable(self.lcp, min)

    def getLCP(self, i, j):
        """ S[i:]とS[j:]の共通文字数を取得 """

        return self.st.get(min(self.rsa[i], self.rsa[j]), max(self.rsa[i], self.rsa[j]))

N = INT()
S = input()

sa = SuffixArray(S)
sa.build_lcp()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        lcp = min(sa.getLCP(i, j), j - i)
        ans = max(ans, lcp)
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SuffixArray:

    class SparseTable:

        def __init__(self, A, func):
            self.N = len(A)
            self.func = func
            h = 0
            while 1<<h < self.N:
                h += 1
            self.dat = list2d(h, 1<<h, 0)
            self.height = [0] * (self.N+1)

            for i in range(2, self.N+1):
                self.height[i] = self.height[i>>1] + 1
            for i in range(self.N):
                self.dat[0][i] = A[i]
            for i in range(1, h):
                for j in range(self.N):
                    self.dat[i][j] = self.func(self.dat[i-1][j], self.dat[i-1][min(j+(1<<(i-1)), self.N-1)])
            
        def get(self, l, r):
            """ 区間[l,r)でのmin,maxを取得 """

            a = self.height[r-l]
            return self.func(self.dat[a][l], self.dat[a][r-(1<<a)])

    def __init__(self, S):
        self.k = 1
        self.S = S
        self.N = len(S)
        self.rank = [0] * (self.N+1)
        self.tmp = [0] * (self.N+1)
        self.sa = [0] * (self.N+1)
        self.build_sa()

    
    
    
    
    
    
    

    def compare_sa(self, i, j):
        """ saの比較関数 """

        
        if self.rank[i] == self.rank[j]: res1 =  0
        elif self.rank[i] < self.rank[j]: res1 =  -1
        else: res1 = 1
        
        ri = self.rank[i+self.k] if i + self.k <= self.N else -1
        rj = self.rank[j+self.k] if j + self.k <= self.N else -1
        if ri == rj: res2 = 0
        elif ri < rj: res2 = -1
        else: res2 = 1
        
        return res1 or res2

    def build_sa(self):
        """ Suffix Arrayの構築 """
        from functools import cmp_to_key

        
        for i in range(self.N+1):
            self.sa[i] = i
            self.rank[i] = ord(self.S[i]) if i < self.N else -1

        
        k = 1
        while k <= self.N:
            self.k = k
            self.sa = sorted(self.sa, key=cmp_to_key(self.compare_sa))
            k *= 2

            
            self.tmp[self.sa[0]] = 0
            for i in range(1, self.N+1):
                self.tmp[self.sa[i]] = self.tmp[self.sa[i-1]] + (1 if self.compare_sa(self.sa[i-1], self.sa[i]) else 0)
            for i in range(self.N+1):
                self.rank[i] = self.tmp[i]

    def build_lcp(self):
        """ LCP配列の構築 """

        self.lcp = [0] * (self.N+1)
        self.rsa = [0] * (self.N+1)
        for i in range(self.N+1):
            self.rsa[self.sa[i]] = i
        h = 0
        self.lcp[0] = 0
        for i in range(self.N):
            
            j = self.sa[self.rsa[i]-1]

            
            if h > 0:
                h -= 1
            while j+h < self.N and i+h < self.N:
                if self.S[j+h] != self.S[i+h]:
                    break
                h += 1
            self.lcp[self.rsa[i]-1] = h

        
        self.st = self.SparseTable(self.lcp, min)

    def getLCP(self, i, j):
        """ S[i:]とS[j:]の共通文字数を取得 """

        return self.st.get(min(self.rsa[i], self.rsa[j]), max(self.rsa[i], self.rsa[j]))

N = INT()
S = input()

sa = SuffixArray(S)
sa.build_lcp()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        lcp = min(sa.getLCP(i, j), j - i)
        ans = max(ans, lcp)
print(ans)