Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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)
                #print(ans,i,j)
        else:
            chain=0

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

def isok(d):    #長さdの文字列で重ならない2つの文字列が存在するかを判定
    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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

def isok(d):    #長さdの文字列で重ならない2つの文字列が存在するかを判定
    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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

def isok(d):    #長さdの文字列で重ならない2つの文字列が存在するかを判定
    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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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):  #iは1-indexed
    for j in range(1,i+1):
        if S[i-1]==S[j-1]:  #Sは0-indexedなので-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):  #iは1-indexed
    for j in range(1,i):
        ans=max(ans,min(dp[i][j],i-j))  #2つの文字列は重ならないので最長でもi-j
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)) #最大の文字列一致はd以下
            cnt=0
    else:
        if 0<cnt:   #最後の文字が一致していた場合
            ans=max(ans,min(d,cnt))    #残ったcntも答えの候補になる
print ans

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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


n = int(readline())
s = read().rstrip().decode()
ans = 0
for i in range(n):
    for j, m in enumerate(Z_algo(s[i:])):
        ans = max(ans, min(j, m))
print(ans)

Submission status: Accepted

Solution code:
class RollingHash(object):
    def __init__(self, S, base, mod):
        self.mod = mod
        l = len(S)

        self.hash_lst = [0] * (l + 1)
        self.pow_lst = [1] * (l + 1)

        for i in range(l):
            self.hash_lst[i + 1] = (self.hash_lst[i] * base + ord(S[i])) % mod
            self.pow_lst[i + 1] = (self.pow_lst[i] * base) % mod

    def get_hash(self, left, right):
        return (self.hash_lst[right] - self.hash_lst[left] * self.pow_lst[right - left] % self.mod) % self.mod


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

base = 1007
mod = pow(10, 9) + 7
rh = RollingHash(S, base, mod)

left = 0
right = N // 2

while left <= right:
    mid = (left + right) // 2

    found_hash = {}
    found = False
    for i in range(N - mid + 1):
        h = rh.get_hash(i, i + mid)

        if h not in found_hash:
            found_hash[h] = i
        else:
            if found_hash[h] <= i - mid:
                found = True
                break

    if found:
        left = mid + 1
    else:
        right = mid - 1


print(right)

Submission status: Accepted

Solution code:

# 長さnの文字列Sについて，各iに対しSとS[i:-1]の最長共通接頭辞(LCP)の長さを求める
def Z_algorithm(S): # O(n)
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    LCP[0] = l = n
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        LCP[i] = j
        k = 1
        while l-i > k < j - LCP[k]:
            LCP[i+k] = LCP[k]
            k += 1
        i += k
        j -= k
    return LCP # LCP:list[int,...] (LCP[i]はSとS[i:-1]の最長共通接頭辞の長さ)



N = int(input())
S = input()
ans = 0
for i in range(N):
    lcp = Z_algorithm(S[i:])
    for j in range(len(lcp)):
        if lcp[j]<=j:
            ans = max(ans,lcp[j])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from random import randint

def main():
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())   
    
    class RollingHash:
        def __init__(self, s):
            self.s = s    # パターン探索を行われる側の文字列
            self.size = len(s)
            self.hashmod = 2 ** 64 - 1
            self.base = randint(2 ** 10, 2 ** 11)
            self.hash_list = self._make_rolling_hash_list()

        def _make_rolling_hash_list(self):
            hash_list = [0] * (self.size + 1)    # [h(s[0:0]), h(s[0:1]), h(s[0:2]), h(s[0:3]), ..., h(s[0:size])]
            prev = 0
            for i in range(1, self.size + 1):
                hash_num = (prev * self.base + ord(self.s[i-1])) % self.hashmod
                hash_list[i] = hash_num
                prev = hash_num
            return hash_list
        
        def calc_interval_hash(self, i, j):
            """
            s[i:j] のハッシュを計算
            """
            return (self.hash_list[j] - self.hash_list[i] * pow(self.base, (j - i), self.hashmod)) % self.hashmod

    
    def span_bisect(rolling):
        left = 1    # 絶対に発見成功するとわかっている
        right = (n // 2) + 1    # 絶対に発見失敗するとわかっている
        while right - left > 1:
            d = dict()
            mid_span = left + (right - left) // 2    # 二分探索で今回選ばれた span
            for i in range(n - mid_span + 1):
                j = i + mid_span
                h = rolling.calc_interval_hash(i, j)
                try:
                    first_j = d[h]
                    if first_j <= i:
                        left = mid_span
                        break
                except KeyError:
                    d[h] = j
            else:
                right = mid_span
        return left


    n = ii()
    s = input()
    if len(list(set(list(s)))) == n:
        print(0)
    else:
        # main
        rolling = RollingHash(s)
        print(span_bisect(rolling))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

def check_bisect(l,h1,b1,h2,b2):
    for j in range(N-2*l+1):
        a1 = get(h1,b1,j,l+j)
        a2 = get(h2,b2,j,l+j)
        for k in range(N-2*l-j+1):
            if a1 == get(h1,b1,j+l+k,2*l+j+k) and a2 == get(h2,b2,j+l+k,2*l+j+k):
                return True
    return False

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
left = 1
right = N // 2
finish = False
if N <= 26:
    s = set(list(S))
    if N <= 3:
        if len(s) < N:
            print('1')
        else:
            print('0')
        finish = True
    else:
        if len(s) == N:
            print('0')
            finish = True
while finish == False:
    if left == right:
        print(left)
        finish = True
    elif right - left == 1:
        if check_bisect(right,h1,b1,h2,b2):
            print(right)
        else:
            print(left)
        finish = True
    else:
        mid = (left+right) // 2
        if check_bisect(mid,h1,b1,h2,b2):
            left = mid
        else:
            right = mid - 1

Submission status: Accepted

Solution code:
import sys
import random
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 文字列アルゴリズム
# RollingHash
# ローリングハッシュ

# 64bit 溢れないように
class RollingHash:
    MASK30 = (1 << 30) - 1
    MASK31 = (1 << 31) - 1
    MOD = (1 << 61) - 1
    POSITVIZER = MOD * ((1 << 3) - 1)

    def __init__(self, S):
        # 事前計算
        Base = random.randrange(129, (1 << 61) - 1)
        self.Base = Base

        L = len(S)
        powMemo = [0] * (L + 1)
        rhash = [0] * (L + 1)

        powMemo[0] = 1
        for i in range(1, L + 1):
            powMemo[i] = self.calcMod(self.Mul(powMemo[i - 1], Base))

        for i in range(L):
            rhash[i + 1] = self.calcMod(self.Mul(rhash[i], Base) + ord(S[i]))

        self.powMemo = powMemo
        self.rhash = rhash

    def getHash(self, begin, length):
        r = self.calcMod(
            self.rhash[begin + length]
            + self.POSITVIZER
            - self.Mul(self.rhash[begin], self.powMemo[length])
        )

        return r

    def Mul(self, l, r):
        lu = l >> 31
        ld = l & self.MASK31
        ru = r >> 31
        rd = r & self.MASK31
        middle = ld * ru + lu * rd

        return (
            ((lu * ru) << 1) + ld * rd + ((middle & self.MASK30) << 31) + (middle >> 30)
        )

    def calcMod(self, val):
        val = (val & self.MOD) + (val >> 61)
        if self.MOD <= val:
            val -= self.MOD
        return val


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

RH = RollingHash(S)


def check(n, RH):
    ret = False
    cnt = defaultdict(int)
    for i in range(0, N - n + 1):
        h = RH.getHash(i, n)

        if not cnt[h]:
            cnt[h] = i + 1
        else:
            f = cnt[h]
            if f + n <= i + 1:
                ret = True
                break

    return ret


l = 0  # OK
r = (N // 2) + 1  # NG

while (r - l) != 1:
    mid = (l + r) // 2
    if check(mid, RH):
        l = mid
    else:
        r = mid

print(l)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 文字列アルゴリズム
# Z-Algorithm
# ZAlgorithm

# AC

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

ans = 0


def Z_Algorithm(S):
    L = len(S)
    Z = [0] * L
    Z[0] = L

    i = 1
    j = 0

    while i < L:
        # 同じなら引き伸ばす
        # 前回のjを引き継ぐ
        while i + j < L and S[j] == S[i + j]:
            j += 1
        Z[i] = j

        # j = 0なら次
        if j == 0:
            i += 1
            continue

        # 同じ数字分横にずらす
        # 右にそれ以上の文字があればcontinue
        k = 1
        while k < j 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:])

    L = len(Z)
    for j in range(1, L):
        l = min(Z[j], j)
        ans = max(l, ans)

print(ans)

Submission status: Accepted

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

suc=[0]*(n-1)
ans=0
for i,c in enumerate(s):
    for j in range(n-1):
        idx=(i+1+j)%n
        if idx==0:
            suc[j]=0#またぐのは禁止
        if c==s[idx]:
            suc[j]+=1
            suc[j]=min(suc[j],j+1,n-1-j)#最大j+1を超えると重なるため
            ans=max(ans,suc[j])
        else:
            suc[j]=0
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    s = input().rstrip()
    l, r = 0, 0
    res = 0
    while r < n:
        r += 1
        if not s[l:r] in s[r:]:
            l += 1
            res = max(res, r-l)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    s = input().rstrip()
    l, r = 0, 0
    res = 0
    while r < n:
        r += 1
        if not s[l:r] in s[r:]:
            l += 1
            res = max(res, r-l)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import random
base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1
def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1



hash = set()
l = 0
r = n
while r - l > 1:
    m = l + (r-l)//2
    hash = dict()
    flag = 0
    for i in range(n-m+1):
        h = rolling_hash(i, i+m)
        if h not in hash.keys():
            hash[h] = i
        elif hash[h]+m <= i:
            flag = 1
            break
    if flag == 1:
        l = m
    else:
        r = m

print(l)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    sn = [ord(c) - 96 + x for c in s]

    lmax = n // 2
    m1 = 10 ** 9 + 7
    m2 = 2 ** 61 - 1

    ans = 0

    ng = n + 1
    ok = 0

    while abs(ng - ok) > 1:
        l = (ng + ok) // 2
        found = False

        appeared = set()
        diff = pow(m1, l - 1, m2)

        h_init = 0

        for i in range(l):
            h_init += sn[i] * pow(m1, l - 1 - i, m2)
            h_init %= m2

        hashlist = [0] * n
        hashlist[l - 1] = h_init
        h = h_init

        for i in range(l, n):
            h -= sn[i - l] * diff
            h *= m1
            h += sn[i]
            h %= m2
            hashlist[i] = h
            if i - l >= 0:
                appeared.add(hashlist[i - l])
            if h in appeared:
                found = True
                break

        if found:
            ok = l
        else:
            ng = l

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
S=list(input())
dp=[[0]*(n+1) for i in range(n+1)]#i文字目まで、j文字目までの長さ
for i in range(1,n):
  for j in range(i+1,n+1):
    if S[i-1]==S[j-1]:
      if j-i<dp[i-1][j-1]+1:
        dp[i][j]=dp[i-1][j-1]
      else:
        dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n+1):
  for j in range(n+1):
    if dp[i][j]>ans:
      ans=dp[i][j]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
Z = [0 for _ in range(n)]
ans = 0
for begin in range(n):
    Z[begin] = n-begin
    i = begin + 1
    j = 0
    while i < n:
        while i+j < n and s[begin+j] ==s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < n and k+Z[begin+k] < j:
            Z[i+k] = Z[begin+k]
            k += 1
        i += k
        j -= k
    for i in range(begin,n):
        l = min(i-begin,Z[i])
        ans = max(ans,l)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
def main():
    n = int(input())
    s = list(input())
    for i in range(n):
        s[i] = ord(s[i]) - ord("a")
    s = np.array(s)
    dp = np.zeros((n+1, n+1), dtype=np.int64)
    tmp = np.arange(0, n+1)
    t = np.zeros((n+1, n+1))
    for i in range(n+1):
        t[i] += tmp
        tmp -= 1
#    for i in range(n+1):
#        print(t[i])
    for i in range(n):
        c = s[i]
        equal = (c == s)
#        print(equal)
        dp[i+1][1:] += equal
        dp[i+1][1:] += equal * dp[i][:-1]
#    for i in range(n+1):
#        print(dp[i])
    dp = np.minimum(dp, t)
#    for i in range(n+1):
#        print(dp[i])
    ans = 0
    for i in range(1, n):
        tmp = dp[i][i+1:]
        tmp = tmp[ans<tmp]
        if 0 < len(tmp):
            ans = max(ans, max(tmp))
    print(int(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

N=int(input())
S=input()
S=[S[i] for i in range(0,N)]

ans=0
for i in range(0,N):
    data=Z_algorithm(S)
    for j in range(0,len(data)):
        ans=max(min(data[j],j),ans)
    S=S[1:]
print(ans)

Submission status: Accepted

Solution code:



"""
N <= 5 * 10**3　なので、２重ループぐらいなら間に合うか？

例３
strangeorange
**range*range

他に２回以上出てくるものとして
r,a, みたいな単体
ra, nge みたいな最長の部分文字列の一部
みたいな感じなので
l,r (r=l+1~N-1)を持っておいて、S[l:r+1] = S[r+1:XX]になるものがあればさらに右をみて～みたいな？

"""


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


l = 0
r = 1
ans = 0
while True:
    if l == N-1:
        break
    while S[l:r] in S[r:]:
        r += 1

    ans = max(ans, r - l - 1)
    #print(l,r, S[l:r], S[r:], ans)
    l += 1
    if l == r:
        r = l + 1

print(ans)

Submission status: Accepted

Solution code:
#Z-Algorithm
#文字列が与えられた時、各 i について「S と S[i:] の最長共通接頭辞の長さ」を記録した配列 A を O(len(S)) で構築するアルゴリズム
#s : 文字列
#あとで要復習！
def z_algorithm(s):
    N = len(s)
    z_alg = [0]*N
    z_alg[0] = N
    i = 1
    j = 0
    
    while i < N:
        while i+j < N and s[j] == s[i+j]: # 伸ばせるだけ伸ばす
            j += 1
        z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k+z_alg[k] < j: # 今までで求められている場所ならば計算を省略
            z_alg[i+k] = z_alg[k]
            k += 1
        i += k
        j -= k
    return z_alg

n = int(input())
S = input()
max_ = 0
for i in range(n):
    k = S[i:len(S)]
    li = z_algorithm(k)
    for j in range(len(li)):
        if li[j] < j+1:
            max_ = max(max_, li[j])
print(max_)

Submission status: Accepted

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

res = 0
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i in reversed(range(N)):
    for j in reversed(range(i + 1, N)):
        if S[i] == S[j]:
            dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1)
        res = max(res, min(dp[i][j], j - i))
        
print(res)

Submission status: Accepted

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


class RollingHash:
    base1 = 1007
    base2 = 2009
    mod1 = 10 ** 9 + 7
    mod2 = 10 ** 9 + 9
    
    def __init__(self, s):
        self.s = s
        
        n = len(s)
        self.hash1 = [0] * (n + 1)
        self.hash2 = [0] * (n + 1)
        self.power1 = [1] * (n + 1)
        self.power2 = [1] * (n + 1)
        for i in range(n):
            self.hash1[i + 1] = (self.hash1[i] * self.base1 + ord(s[i])) % self.mod1
            self.hash2[i + 1] = (self.hash2[i] * self.base2 + ord(s[i])) % self.mod2
            self.power1[i + 1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i + 1] = (self.power2[i] * self.base2) % self.mod2
            
    def get_hash(self, l, r):
        """Gets hash of S[left:right]"""
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.mod1
        if res1 < 0:
            res1 += self.mod1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.mod2
        if res2 < 0:
            res2 += self.mod2
            
        return (res1, res2)
    
    def get_lcp(self, a, b):
        """Gets lcp of S[a:] and S[b:]"""
        low = 0
        high = min(len(self.hash1) - a, len(self.hash1) - b)
        
        while high - low > 1:
            mid = (low + high) >> 1
            if self.get_hash(a, a + mid) != self.get_hash(b, b + mid):
                high = mid
            else:
                low = mid
                
        return low


def check(d):
    ctr = {}
    for i in range(N - d + 1):
        p = rh.get_hash(i, i + d)
        if p in ctr:
            if i - ctr[p] >= d:
                return True
        else:
            ctr[p] = i
            
    return False


rh = RollingHash(S)
left = 0
right = N // 2 + 1
while right - left > 1:
    mid = (left + right) >> 1
    if check(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Accepted

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

from collections import defaultdict

def check(l):
    d = defaultdict(lambda: -1)
    for i in range(n-l+1):
        if d[s[i:i+l]] != -1:
            if d[s[i:i+l]] + l <= i:
                return True
        else:
            d[s[i:i+l]]=i
    return False

ok=0
ng=len(s)

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

print(ok)

Submission status: Accepted

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

def z_algorithm(s):
    n = len(s)
    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):
    lcp = z_algorithm(S[i:])
    for j in range(N - i):
        res = max(res, min(lcp[j], j))
        
print(res)

Submission status: Accepted

Solution code:
def ok(k):
    # 長さkの連続部分列で重ならずに2回以上現れるものがある
    D = {}
    for i in range(n-k+1):
        s = S[i:i+k]
        try:
            if D[s]+k <= i:
                return True
        except:
            D[s] = i
    return False


n = int(input())
S = input()
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)