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
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    L,R = 0,0 
    for i in range(1, n):
        if i > R: 
            L = R = i
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
            R -= 1
        elif Z[i-L] < R-i+1:
            Z[i] = Z[i - L]
        else:
            L = i
            R += 1
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
            R -= 1
    return Z

n = I()
s = input()
ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j,z in enumerate(Z):
        if j < z:
            continue
        ans = max(ans,z)
print(ans)

Solution (Python):




import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    L,R = 0,0
    for i in range(1, n):
        if i >= R: 
            L = 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

n = I()
s = input()
ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j,z in enumerate(Z):
        if j < z:
            continue
        ans = max(ans,z)
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def si(): return input().rstrip()
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



class RollingHash():
    """ロリハ。容易に衝突するので注意。"""
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:  
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)

        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
        if opt == 2:  
            for i, e in enumerate(s):
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2

        if self.opt == 2:
            return (res1, res2)
        else:
            return res1


def ABC131E():
    N = ii()
    S = si()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Solution (Python):
import sys

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def si(): return input().rstrip()
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



class RollingHash():
    """ロリハ。容易に衝突するので注意。"""
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:  
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)

        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
        if opt == 2:  
            for i, e in enumerate(s):
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2

        if self.opt == 2:
            return (res1, res2)
        else:
            return res1


def ABC131E():
    N = ii()
    S = si()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Solution (Python):
import sys

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



class RollingHash():
    """ロリハ。容易に衝突するので注意。"""
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:  
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)

        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
        if opt == 2:  
            for i, e in enumerate(s):
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1


def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S, opt=1)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Solution (Python):
import sys

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)


def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

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

class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1


    
rh = RollingHash(S, opt=1)

def check(n: int):
    d = dict()
    for i in range(N - n + 1):
        p = rh.get(i, i + n)
        if p in d.keys():
            if(i - d[p] >= n):
                return True
        else:
            d[p] = i
    return False
    
ok, ng = 0, N // 2 + 1
while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
n = int(input())
s = list(input())
ans = 0
for i in range(1,n):
    tmpans = 0
    streak = 0
    for j in range(n-i):
        if s[j] == s[j+i]:
            streak += 1
        else:
            tmpans = max(tmpans,min(i,streak))
            streak = 0
    tmpans = max(tmpans,min(i,streak))
    ans = max(tmpans,ans)
print(ans)

Solution (Python):
n = int(input())
s = list(input())
ansl = []
for i in range(1,n):
    ans = 0
    count = 0
    for j in range(n-i):
        
        if s[j] == s[j+i]:
            count += 1
        else:
            if count > 0:
                if count > ans:
                    ans = min(count,i)
                count = 0
    if count > ans:
        ans = min(count,i)
    ansl.append(ans)
print(max(ansl))

Solution (Python):
n=int(input());s=input()
ans=i=j=0
while j<n:
  t=s[i:j]
  if t in s[j:]:
    ans=max(ans,j-i)
    j+=1
  else:
    i+=1
print(ans)

Solution (Python):
def main(size, text):
    pattern = ""
    matchlen = 0

    for i in range(size):
        pattern += text[i]
        while (len(pattern) > 0 and len(pattern) <= len(text[i+1:])):
            if pattern in text[i+1:]:
                matchlen = max(matchlen, len(pattern))
                break
            else:
                pattern = pattern[1:]
    
    return matchlen

if __name__ == '__main__':
    N = int(input())
    S = input()
    print (main(N, S))

Solution (Python):


n = int(input())
s = input()
 
a = ""
ans = 0
for i in range(n):
    a += s[i]
    while(len(a) > 0):
        if a in s[i+1:]:    
            ans = max(ans,len(a))
            break
        else:               
            a = a[1:]
print(ans)

Solution (Python):
def Z(s,ls):
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and s[j] == s[i+j]:
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    for i in range(ls):
        lcp[i] = min(lcp[i],i)
    return max(lcp)

n = int(input())
s = list(map(ord,list(input())))
print(max(Z(s[i:],n-i) for i in range(n)))

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)


def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Solution (Python):
import sys

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1



def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S, opt=1)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d.keys():
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)


def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d.keys():
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Solution (Python):
N = int(input())
S = input()
l, r = 0, N

def pow_mod(a, b, m):
  ab = 1
  for _ in range(b):
    ab = (ab * a) % m
  return ab

def c2n(c):
  return ord(c) - 97

def hash(s, B, H):
  sh = 0
  for c in s:
    sh = (sh * B + c2n(c)) % H
  return sh

def t(n):
  B, H = 10 ** 8 + 7, 2 ** 64

  if n*2 > N:
    return False
  s, t = S[:n], S[n:n*2]
  sh, th = hash(s, B, H), hash(t, B, H)
  if sh == th:
    return True
  ss = set([sh])
  Bn = pow_mod(B, n, H)
  for i in range(0, N-2*n):
    sh = (sh * B - c2n(S[i]) * Bn + c2n(S[i+n])) % H
    th = (th * B - c2n(S[i+n]) * Bn + c2n(S[i+2*n])) % H
    ss.add(sh)
    if th in ss:
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)

Solution (Python):
import random
import string
N = int(input())
S = input()
l, r = 0, N

def pow_mod(a, b, m):
  ab = 1
  for _ in range(b):
    ab = (ab * a) % m
  return ab

def c2n(c):
  return ord(c) - 97

def hash(s, B, H):
  sh = 0
  for c in s:
    sh = (sh * B + c2n(c)) % H
  return sh

def t(n):
  B, H = 10 ** 8 + 7, 2 ** 64

  if n*2 > N:
    return False
  s, t = S[:n], S[n:n*2]
  sh, th = hash(s, B, H), hash(t, B, H)
  if sh == th:
    return True
  ss = set([sh])
  Bn = pow_mod(B, n, H)
  for i in range(0, N-2*n):
    sh = (sh * B - c2n(S[i]) * Bn + c2n(S[i+n])) % H
    th = (th * B - c2n(S[i+n]) * Bn + c2n(S[i+2*n])) % H
    ss.add(sh)
    if th in ss:
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)

Solution (Python):
n=int(input());s=input()
ans=i=j=0
while j<n:
  t=s[i:j]
  if t in s[j:]:
    ans=max(ans,j-i)
    j+=1
  else:
    i+=1
print(ans)

Solution (Python):
N = int(input()) + 1
S = " "+input()
d = [[0]*N for _ in range(N)]
r = 0
for i in range(N):
    for j in range(i-1,0,-1):
        d[i][j] = d[i-1][j-1] + 1 if S[i] == S[j] else 0
        r = max(r, min(d[i][j], i-j))
print(r)

Solution (Python):
n,s=open(0)
a = i = j = 0
while s[j:]:
  if s[i:j] in s[j:]:
    a = max(a, j-i)
    j+=1
  else:
    i+=1
print(a)

Solution (Python):
class ZAlgorithm(object):
    def __init__(self, s: str):
        self.lcp = self.__create_z(s)

    def __call__(self, i: int):
        return self.lcp[i]

    def __create_z(self, s: str):
        n = len(s)
        lcp = [n] + [0]*(n-1)
        l, r = 0, 0

        for t in range(1, n):
            if t>r:
                z = 0
                while t+z<n and s[0+z]==s[t+z]:
                    z += 1
                lcp[t] = z
                if z>0:
                    l, r = t, t+z-1
            else:
                p, b = t-l, r-t+1
                if lcp[p]<b:
                    lcp[t] = lcp[p]
                else:
                    i = r+1
                    while i<n and s[i]==s[i-t]:
                        i += 1
                    lcp[t] = i-t
                    l, r = t, i-1
        return lcp

def main():
    n, s = open(0).read().split()
    a = 0
    for i in range(int(n)-1):
        ss = s[i:]
        z_algo = ZAlgorithm(ss)
        for j in range(len(ss)):
            a = max(a, min(z_algo(j), j))
    print(a)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]

for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1



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

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]

print(maxp)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def Z(s):
    """
    s: str
    return list of int with length len(s)
    """
    
    n=len(s)
    z=[0]*n
    z[0]=n
    
    L,R=0,0
    for i in range(1,n):
        if i>=R: 
            L=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
def resolve():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) 
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()

Solution (Python):
def z(s):
    n = len(s)
    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
    return a
n = int(input())
s = input()
r = 0
for i in range(n):
    a = z(s[i:])
    for j in range(len(a)):
        if a[j] <= j:
            r = max(r, a[j])
print(r)

Solution (Python):
def zalg(pattern, text):
  L = pattern + "$" + text
  N = len(L)
  Z = [0] * (N)
  i = 1
  j = 0
  while i < N:
    while i + j < N and L[j] == L[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

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

ans = 0
for i in range(N):
  Z = zalg(S[i:], S)
  for j in range(1, N):
    ans = max(ans, min(Z[-j], N - i - j))

print(ans)

Solution (Python):
N = int(input())
S = input()
dp = [[0] * (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
result = 0
for i in range(N):
    for j in range(i + 1, N):
        t = dp[i][j]
        if t > j - i:
            t = j - i
        if t > result:
            result = t
print(result)

Solution (Python):


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

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

Solution (Python):


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

dp = [[0] * (N + 1) for _ in range(N + 1)]
result = 0
for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] == S[j]:
            t = dp[i + 1][j + 1] + 1
            dp[i][j] = t
            if t > j - i:
                t = j - i
            if t > result:
                result = t
print(result)

Solution (Python):
N = int(input())
S = input()
dp = [[0] * (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] = 0
        else:
            dp[i][j] = dp[i + 1][j + 1] + 1
result = 0
for i in range(N):
    for j in range(i + 1, N):
        t = dp[i][j]
        if t > j - i:
            t = j - i
        if t > result:
            result = t
print(result)

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

result = 0
for i in range(N - 1, 0, -1):
    if i <= result:
        break
    t = 0
    for j in range(N - i):
        if S[j] == S[j+i]:
            t += 1
            if t > result:
                result = t
            if result == i:
                break
        else:
            t = 0

print(result)