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

import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return sys.stdin.readline()[:-1]

def main():
    n = II()
    s = S()
    inf = n + 2
    m = [[0 for i in range(n)] for i in range(n)]
    first = [[inf for i in range(n)] for i in range(n)]
    
    lcs = 0
    for i, c in enumerate(s):
        
        if c == s[0]:
            m[i][0] = 1
            first[i][0] = i
            if i != 0:
                lcs = 1
    for i in range(1, n):
        for j in range(1, n):
            if i <= j:
                continue
            if s[i] == s[j]:
                if first[i-1][j-1] > j:
                    m[i][j] = m[i-1][j-1] + 1
                    lcs = max(m[i][j], lcs)
                    if first[i-1][j-1] == inf:
                        first[i][j] = i
                    else:
                        first[i][j] = first[i-1][j-1]
            else:
                m[i][j] = 0

    
    print(lcs)


if __name__ == '__main__':
    main()

Solution (Python):

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

max_length = 0

for i in range(1, n-1):
    tmp_len = 0
    for c1, c2 in zip(s[0:n-i:], s[i::]):
        if c1 == c2:
            tmp_len += 1
        else:
            tmp_len = 0

        max_length = max(max_length, tmp_len)
        if tmp_len >= i:
            break

print(max_length)

Solution (Python):
from collections import defaultdict
N = int(input())
S = input()
def match(n):
  D = defaultdict(list)
  for i in range(N + 1 - n):
    D[S[i:i + n]].append(i)
  for L in D.values():
    if len(L) > 1 and L[-1] - L[0] >= n:
      return True
  return False
def bs(upper, lower):
  if upper - lower == 1:
    return lower
  mid = (upper + lower) // 2
  if match(mid):
    return bs(upper, mid)
  else:
    return bs(mid, lower)
print(N // 2 if match(N // 2) else bs(N // 2, 0))

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

m = [[0] * n for _ in range(n)]
lcs = 0


for j in range(1, n):
    if s[j] == s[0]:
        m[0][j] = 1
        lcs = 1


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

print(lcs)

Solution (Python):
from collections import defaultdict as dd

def check(L):
    strings = {}
    for i in range(N - L):
        s= S[i:i+L+1]
        if s in strings:
            start, end = strings[s]
            
            if i > end:
                
                return True
        else:
            strings[s] = i, i + L
    
    
    return False


N = int(raw_input())
S= raw_input()
lo = 0
hi = N/2 + 1
for i in range(13):
    mid= (lo +hi)//2
    has_two = check(mid)
    
    if has_two:
        lo = mid
    else:
        hi = mid
print(hi)

Solution (Python):
N = int(input())
S = input()
ans = 0
for i in range(N):
    if N-i<ans:
        break
    if S[i+1:].find(S[i-ans:i+1])>=0:
        ans += 1
print(ans)

Solution (Python):
def solve():
    N = int(input())
    S = input()
    next_end = 1
    max_length = 0
    for start in range(N-1):
        for end in range(next_end, N):
            text = S[start:end]
            if text in S[end:]:
                max_length = max(len(text), max_length)
                continue
            else:
                if start + 1 == end:
                    next_end = end + 1
                else:
                    next_end = end
            break
    
    print(max_length)

if __name__ == '__main__':
    solve()

Solution (Python):
P = 123456789012419
x = 31
ix = pow(x, P-2, P)
N = int(input())
A = [ord(s)-95 for s in input()]

def chk(k):
    D = {}
    s = 0
    for i in range(k):
        s = (s * x) % P
        s += A[i]
    X = [s]
    D[s] = k-1
    for i in range(k, N):
        s = ((s - pow(x, k-1, P) * A[i-k]) * x + A[i]) % P
        X.append(s)
        if s in D:
            if i - D[s] >= k:
                return 1
        else:
            D[s] = i
    return 0

l = 0
r = N//2 + 1
while r - l > 1:
    m = (l+r) // 2
    if chk(m):
        l = m
    else:
        r = m
print(l)

Solution (Python):

import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n = int(input())
    s = input()
    if len(set(s)) == n:
        print(0)
        return

    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = -10**4

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

    ans = 0
    for d in dp:
        ans = max(ans, max(d))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys


def solve(N: int, S: str):
    
    ans = 0
    x = []
    for i in range(N):
        x.append(S[i])
        xj = ''.join(x)
        if(S[i+1:].count(xj)):
            ans = max(ans, len(xj))
        else:
            x.pop(0)

    print(ans)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = next(tokens)  
    solve(N, S)

if __name__ == '__main__':
    main()

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

mod = 10 ** 9 + 7
hash = [0]
pow = [1]
for s in S :
    hash.append((hash[-1] * 26 + ord(s) - 97) % mod)
    pow.append(pow[-1] * 26 % mod)

M = 0
for i in range(N + 1) :
    for j in range(i + 1, N + 1) :
        for k in range(M + 1, N - j + 1) :
            if i + k > j :
                break
            if (hash[j+k] - hash[j] * (pow[k])) % mod == (hash[i+k] - hash[i] *  pow[k]) % mod :
                M += 1
            else :
                break
                
print(M)

Solution (Python):
n=int(input())
s=input()
a=[[0]*n for i in range(n)]
buf=0
for i in range(n):
    for j in range(i+1,n):
        if i==0:
            if s[i]==s[j]:
                a[i][j]=1
            continue
        if s[i]==s[j]:
            a[i][j]=min(j-i,a[i-1][j-1]+1)
            buf=max(buf,a[i][j])
print(buf)

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

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

for i in range(N):
    if i > 0 and S[0] == S[i]:
        dp[0][i] = 1

ans = 0
for i in range(0, N-1):
    for j in range(i, N-1):
        if S[i+1] == S[j+1]:
            tmp = dp[i][j] + 1
            tmp2 = min(tmp, j-i)
            dp[i+1][j+1] = tmp2
            if tmp2 > ans:
                ans = tmp2
print(ans)

Solution (Python):
MOD = 10000000000000061
def hsh(s):
    tot = 0
    pw = 1
    for c in s:
        tot = (tot*256 + ord(c))%MOD
        pw = (pw*256)%MOD
    return tot, pw

def ok(L, S):
    h, pw = hsh(S[:L])
    D = {}
    D[h] = 0
    for i in range(len(S) - L):
        j = i + 1
        h = ((h*256 - pw*ord(S[i])) + ord(S[i+L]))%MOD
        if h in D:
            if D[h] + L <= j: return True
        else:
            D[h] = j
    return False


raw_input()
S = raw_input()
lo = 0
hi = len(S)//2

while lo < hi:
    mid = (lo + hi + 1)//2
    ans = ok(mid, S)
    if ans:
        lo = mid
    else:
        hi = mid - 1
print(lo)

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

N=int(input())
S=input().strip()


LEN=len(S)

p=26
mod=(1<<50)+1

TABLE=[0]

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)

def hash_ij(i,j): 
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod


MIN=0
MAX=LEN//2

from collections import defaultdict

while MIN!=MAX:
    x=(MIN+MAX+1)//2
    DICT=defaultdict(list)

    for i in range(LEN-x+1):
        DICT[hash_ij(i,i+x)].append(i)

    

    for l in DICT:
        if max(DICT[l])-min(DICT[l])>=x:
            MIN=x
            break
    else:
        MAX=x-1

print(MIN)

Solution (Python):
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, s in enumerate(S):
  if i != 0 and S[i] == S[0]:
    dp[i][0] = 1
    dp[0][i] = 1

for i in range(1, N):
  for j in range(1, N):
    if i != j and S[i] == S[j]:
      if i + dp[i-1][j-1] == j or j + dp[i-1][j-1] == i:
        dp[i][j] = dp[i-1][j-1]
      else:
        dp[i][j] = dp[i-1][j-1] + 1
      ans = max(ans, dp[i][j])
print(ans)

Solution (Python):
def lrs(str):
    n = len(str)
    LCSRe = [[0 for x in range(n + 1)]
             for y in range(n + 1)]
    res = ""
    res_length = 0
    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (str[i - 1] == str[j - 1] and
                    LCSRe[i - 1][j - 1] < (j - i)):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

                if (LCSRe[i][j] > res_length):
                    res_length = LCSRe[i][j]
                    index = max(i, index)

            else:
                LCSRe[i][j] = 0


    if (res_length > 0):
        for i in range(index - res_length + 1,
                       index + 1):
            res = res + str[i - 1]

    return res


if __name__ == "__main__":
    a = int(input())
    s = input()

    print(len(lrs(s)))

Solution (Python):
n = int(input())
s = input()
s_table = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(i, n):
        if i != j and s[i] == s[j]:
            s_table[i][j] = 1
            s_table[j][i] = 1


ans = 0
for i in range(n):
    cnt = 0
    start = i
    j = 0
    while i < n and j < n:
        
        if s_table[i][j] == 1 and start != j:
            
            cnt += 1
            ans = max(cnt, ans)
        else:
            cnt = 0
            start = i + 1
        i += 1
        j += 1
print(ans)

Solution (Python):
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

MOD = 10**9 + 7
P = 97
def solve(N, S):
    A = [0]
    rawA = []
    
    ha = 0
    
    for c in S:
        x = ord(c) - ord('a') + 2
        rawA.append(x)
        
        
        
        ha += x
        A.append(ha)
        
        
    

    def gethash(i, j):
        ha = A[j] - A[i]
        
        ha %= MOD
        
        return ha

    
    
    
    
    def doublematch(L):
        if L == 0: return True
        for i in xrange(N - L + 1):
            for j in xrange(i + L, N - L + 1):
                if gethash(i, i+L) == gethash(j, j+L) and rawA[i:i+L] == rawA[j:j+L]:
                    return True

    
    lo, hi = 0, len(A) / 2
    while lo < hi:
        mi = (lo + hi + 1) / 2
        if doublematch(mi):
            lo = mi
        else:
            hi = mi - 1
    return lo

print solve(rri(), rr())

Solution (Python):
def longestRepeatedSubstring(str):

    n = len(str)
    LCSRe = [[0 for x in range(n + 1)]
             for y in range(n + 1)]

    res = ""
    res_length = 0

    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (str[i - 1] == str[j - 1] and
                    LCSRe[i - 1][j - 1] < (j - i)):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

                if (LCSRe[i][j] > res_length):
                    res_length = LCSRe[i][j]
                    index = max(i, index)

            else:
                LCSRe[i][j] = 0


    if (res_length > 0):
        for i in range(index - res_length + 1,
                       index + 1):
            res = res + str[i - 1]

    return res


if __name__ == "__main__":
    a = int(input())
    s = input()

    print(len(longestRepeatedSubstring(s)))

Solution (Python):
def inpl(): return list(map(int, input().split()))

N = int(input())
S = input()
F = [1]*(N//2 + 2)
for i in range(1, len(F)):
    F[i] = F[i]*26

OK = 0
NG = N//2 + 1

def check(l):
    D = set()
    for i in range(N-2*l+1):
        
        D.add(S[i:i+l])
        if S[i+l:i+2*l] in D:
            return True
    else:
        return False



while abs(OK - NG) > 1:
    mid = (OK + NG)//2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

Solution (Python):
N = int(input())
S = input()
ans = 0
for i in range(1, N):
    tmp = "?" * i + S
    c = 0
    m = 0
    for j in range(i, N):
        if S[j] != tmp[j]:
            c = 0
        else:
            c += 1
        m = max(m, c)
    m = min(m, i)
    ans = max(ans, m)

print(ans)

Solution (Python):
import math
n = int(input())
s = input()
ans=0
for i in range(n):
    
    maxim = i
    num=[0 for k in range(n-i)]
    count=0
    lmax=0
    for j in range(n-i):
        if(s[j]==s[i+j]):
            num[j]=1
            count+=1
            
            if(lmax<count):
                lmax=count
        else:
            count=0
    
    if(ans<lmax):
        ans=min(lmax,maxim)
print(ans)

Solution (Python):

import sys
def input():
	return sys.stdin.readline().strip()

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

dp = [[0]*N for i in range(N)]

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

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


h = {}
for i in range(26):
    h[chr(ord('a') + i)] = i

base1 = 1009
base2 = 1007
mod1 = 1000000007
mod2 = 1000000009

pow1 = [1]*(n+1)
pow2 = [1]*(n+1)
hash1 = [0]*(n+1)
hash2 = [0]*(n+1)
for i in range(n):
    hash1[i+1] = (hash1[i]+h[s[i]]) * base1 % mod1
    hash2[i+1] = (hash2[i]+h[s[i]]) * base2 % mod2
    pow1[i+1] = pow1[i] * base1 % mod1
    pow2[i+1] = pow2[i] * base2 % mod2



def get(l, r):
    t1 = ((hash1[r] - hash1[l] * pow1[r-l]) % mod1 + mod1) % mod1
    t2 = ((hash2[r] - hash2[l] * pow2[r-l]) % mod2 + mod2) % mod2
    return (t1, t2)

from collections import deque, defaultdict


def check(k):
    
    if k > n:
        return False
    que1 = deque()

    d = defaultdict(int)
    
    for i in range(k):
        if i+k<=n:
            a = get(i, i+k)
            que1.append(a)
        else:
            break
    for i in range(k, n-k+1):
        a = que1.popleft()
        d[a] += 1
        b = get(i, i+k)
        if d[b] > 0:
            return True
        que1.append(b)
    
    return False

left = 0
right = n

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

print(left)

Solution (Python):
N = int(input())
S = input()
dp = [[0]*N for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1,N):
        if(S[i]==S[j]):
            if(i==0):
                dp[i][j] = 1
            else:
                last = dp[i-1][j-1]
                if(j-last == i):
                    continue
                dp[i][j] = last+1

                ans = max(dp[i][j],ans)
print(ans)

Solution (Python):

tmp = input()
my_str = input()

start = 0
end = 1
max_len = 0

while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1

print(max_len)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



def Z_algo(S):
    n=len(S)
    A=[0]*n
    A[0]=n
    i=1
    j=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
    return A

N = I()
S = str(input())

T = ''.join(list(reversed(S)))

dp = [0]*N
for i in range(1,N):
    a = Z_algo(T[N-i-1:])
    b = []
    for j in range(len(a)):
        b.append(min(a[j],j))
    dp[i] = max(dp[i-1], max(b))

print(dp[N-1])

Solution (Python):
import sys
readline = sys.stdin.readline
N = int(readline())
S = tuple(map(ord, readline().strip()))

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

for j in range(N-1, -1, -1):
    for i in range(j-1, -1, -1):
        k = dp[i+1][j+1]
        if S[i] != S[j]:
            continue
        if i+k == j:
            dp[i][j] = k
        else:
            dp[i][j] = k+1
print(max(max(d) for d in dp))

Solution (Python):
def check(S, l):
    idx = {}
    for i in range(len(S)-l+1):
        x = S[i:i+l]
        if x not in idx:
            idx[x] = i
        else:
            if idx[x]+l <= i:
                return True
    return False


def main():
    N = int(input())
    S = input()
    lo = 0
    hi = N//2
    while lo < hi:
        mid = -(-(lo+hi)//2)
        if check(S, mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

def input():
    return sys.stdin.readline()[:-1]

from collections import defaultdict

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

def is_pos(n,S,N):
    dd = defaultdict(int)
    flag =True
    for i in range(N-n+1):
        s = dd[S[i:i+n]]
        if s!=0:
            if i+1-s>=n:
                flag=False
                break
        else:
            dd[S[i:i+n]]=i+1
    return flag


def bisect(i,j,S,N):
    while j-i>1:
        if is_pos((i+j)//2,S,N):
            j = (i+j)//2
        else:
            i = (i+j)//2
    return i

print(bisect(0,N//2 + 1, S, N))

Solution (Python):
def Z_algorithm(S):
    l=len(S)
    A=[0]*l
    A[0]=l
    i=1; j=0
    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 main():
    n=int(input())
    S=input()
    ans=0
    for i in range(1,n):
        s=S[:i]
        t=S[i:]
        l=len(t)
        T=t+'-'+s
        Z=Z_algorithm(T)
        
        ans=max(ans,max(Z[l:]))
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):

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 A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return


def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return


def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return


def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return


def E():
    n = I()
    s = S()
    l = 0
    r = n
    M = 10**64+1
    b = 26
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in alp:
        f[i] = ord(i)-ord("a")
    pb = [pow(b,i,M) for i in range(n+1)]
    while r-l > 1:
        m = (l+r)>>1
        d = defaultdict(lambda : float("inf"))
        hash = 0
        for i in s[:m]:
            hash *= b
            hash += f[i]
            hash %= M
        d[hash] = 0
        t = pb[m]
        for i in range(n-m):
            si = s[i]
            hash *= b
            hash -= t*f[si]
            hash += f[s[i+m]]
            hash %= M
            if d[hash]+m <= i+1:
                l = m
                break
            if i+1 < d[hash]:
                d[hash] = i+1
        else:
            r = m
    print(l)
    return


def F():

    return


if __name__ == "__main__":
    E()

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()


def f(ss):
	n = len(ss) 
	LCSRe = [[0 for x in range(n + 1)] 
				for y in range(n + 1)] 
	res = ""
	res_length = 0

	index = 0
	for i in range(1, n + 1): 
		for j in range(i + 1, n + 1): 
			if (ss[i - 1] == ss[j - 1] and
				LCSRe[i - 1][j - 1] < (j - i)): 
				LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
				if (LCSRe[i][j] > res_length): 
					res_length = LCSRe[i][j] 
					index = max(i, index)
			else: 
				LCSRe[i][j] = 0
	if (res_length > 0): 
		for i in range(index - res_length + 1, index + 1): 
			res = res + ss[i - 1] 

	return res_length

n = ni()
s = ns()
print(f(s))

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

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

ans = 0
for i in range(1,n):
    res = 0
    r = 0
    for a,b in zip(s,s[i:]):
        if a == b:
            res += 1
            if res > r: r = res
        else:
            res = 0

    if r > i: r = i
    if ans < r: ans = r

print(ans)

Solution (Python):

import sys
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = len(S)
    return Z


def solve(N: int, S: str):

    ans = 0
    for i in range(N-1):        
        z = z_algorithm(S[i:])  
        for j, zz in enumerate(z):  
            ans = max(min(j, zz), ans)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = next(tokens)  
    solve(N, S)


if __name__ == '__main__':
    main()

Solution (Python):



def solve(n, s):
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    res_len = 0
    idx = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if s[i - 1] == s[j - 1] and dp[i - 1][j - 1] < j - i:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > res_len:
                    res_len = dp[i][j]
                    idx = max(i, idx)
            else:
                dp[i][j] = 0
    return res_len


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


if __name__ == "__main__":
    main()

Solution (Python):

n = int(input())
s = input()
D = [[0] * n for i in range(n)]

for i in range(n):
    D[0][i] = int(s[0]==s[i])
    D[i][0] = int(s[0]==s[i])
D[0][0] = 0

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



print(max([max(D[i]) for i in range(n)]))

Solution (Python):
n=int(input())
s=input()
a=0
i=0
j=1
while j<n:
	if s[i:j] in s[j:]:
		a=max(a,len(s[i:j]))
		j+=1
	else:
		i+=1
	if i==j:
		i+=1
		j+=2
print(a)

Solution (Python):
def LRS(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = ""
    res_length = 0
  
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res 
  
n = int(input())
s = input()

print(len(LRS(s)))