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:
N = int(input())
S = input()
l = 0
k = 1
for i in range(N - 1):
    while True:
        if S[i : i + k] in S[i + k :]:
            k += 1
        else:
            break
    l = max(l, k - 1)
print(l)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc141/submissions/7548484

n = int(input())
S = input()
N = [0]*n
j = 0
 
for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
r = 0
ans = 0
for i in range(N):
    while True:
        if S.rfind(S[i : r + 1]) >= r + 1:
            r += 1
            ans = max(ans, r - i)
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
r = 1
ans = 0
for i in range(N):
    while True:
        if S.rfind(S[i : r + 1]) >= r + 1:
            r += 1
            ans = max(ans, r - i)
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
#違うアルゴリズム
#これはO(n)で終わる。素晴らしい。
n = int(input())
s = input()

#求める長さ
ans = 0

#iは、区切りのindex。すなわち、検索文字列の末尾index。
for i in range(n):
    if n<i+ans:
        break
    
    if s[i+1:].find(s[i-ans:i+1]) != -1:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
def z_algo(s):
    z = [0]*len(s)
    n = len(s)
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            l = 0
            while l + L < n and s[l] == s[l + i]:
                l += 1
            z[i] = l
            if l > 0:
                R = L + l - 1
        else:
            k = i - L
            right_len = R - i + 1
            if z[k] < right_len:
                z[i] = z[k]
            else:
                L = i
                l = R + 1
                while l < n and s[l - L] == s[l]:
                        l += 1
                z[i] = l - L
                R = l - 1
    return z

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

for i in range(N):
    LCP = z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
#何もアルゴリズム感がないやつ。ただメソッド使うだけ。
n = int(input())
s = input()

#j=0は解なのは確定している。さらに大きくできるか、を調べる。
j = 1

for i in range(n):
    seq = s[i:i+j]
    while s[i+j:].find(seq) != -1:
        j += 1
        seq = s[i:i+j]

#ゆえに、－１すればいい。        
print(j-1)

Submission status: Accepted

Solution code:
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    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
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

for i in range(n):
    # 検索元の部分文字列の一文字目i
    for l in range(max_l + 1,((n - i) // 2) + 1):
        # lは検索元の文字列の長さ
        # i文字目からi+l-1文字目がi+l文字目からn-1文字目
        if s[i:i+l] in s[i+l:]:
            if l > max_l:
                max_l = l
        else:
            break
print(max_l)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
f=0
b=-1
for d in range(1,n):
  c=0
  b=-1
  for i in range(n-d):
    if s[i]==s[i+d] and c<d:
      if b==-1:b=i
      c+=1
      f=max(f,c)
      if c>=d:
        break
    else:
      c=0
      b=-1
print(f)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
f=0
b=-1
for d in range(1,n):
  c=0
  b=-1
  for i in range(n-d):
    if c>=d:
      break
    if s[i]==s[i+d]:
      if b==-1:b=i
      c+=1
      f=max(f,c)
    else:
      c=0
      b=-1
print(f)

Submission status: Accepted

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

ans = 0
for l in range(N):
    # Z-algorithm
    A = [-1]*(N-l)
    c = 0
    S = WholeS[l:]
    for i, s in enumerate(S):
        if i == 0:
            continue
        if c+A[c] > i+A[i-c]:
            A[i] = A[i-c]
        else:
            j = max(0, A[c]-i+c)
            while i+j < N-l and S[j] == S[i+j]:
                j += 1
            A[i] = j
            c = i
        ans = max(ans, A[i] if(i>A[i]) else i)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = str(input())
#N = 13
#S = "strangeorange"

lb = 0
ub = N //2 + 1
flag = False
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = set()
    for i in range(N - 2*mid + 1):
        s.add(S[i:mid+i])
        if S[mid+i:i+2*mid] in s:
            flag = True
            break
        else:
            flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

Submission status: Accepted

Solution code:
class ZAlgorithm(object):
    def __init__(self, s: str):
        self.orig_str = s
        self.Z = self.__create_z(s)

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

    def __create_z(self, s: str):
        n = len(s)
        Z = [0]*n
        Z[0] = n
        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
                Z[t] = z
                if z>0:
                    l, r = t, t+z-1
            else:
                p, b = t-l, r-t+1
                if Z[p]<b:
                    Z[t] = Z[p]
                else:
                    i = r+1
                    while i<n and s[i]==s[i-t]:
                        i += 1
                    Z[t] = i-t
                    l, r = t, i-1
        return Z

def f_e():
    n = int(input())
    s = input()
    a = 0
    for i in range(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__":
    f_e()

Submission status: Accepted

Solution code:
def z_algorithm(S):
    """
    文字列の各インデックスについて「SとS[i: len(S) - 1]の最良共通接頭辞の長さ」を求め、
    それを記録した配列Aを O(|S|) で作成します。
    """
    A = [-1 for _ in range(len(S))]
    A[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i + j < len(S) and S[j] == S[i + j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(S) and k + A[k] < j:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


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

ans = 0
for i in range(N - 1):
    s = S[i:]
    A = z_algorithm(s)
    A = [min(i, a) for i, a in enumerate(A)]  # 重複する区間の除去
    ans = max(ans, max(A[1:]))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

CHRtoINT = defaultdict(int)
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]
for i, c in enumerate(atoz):
    CHRtoINT[c] = i

# 文字列 S の長さ x の連続した部分文字列を b, m (base, mod は互いに素)でハッシュ化したリストを返す
def RollingHash(S, x, b1 = 1009, b2 = 1007, m1 = 10**9+7, m2 = 10**9+9):
    h1, h2, B1, B2 = 0, 0, 1, 1
    for c in S[:x]:
        h1 = (h1 * b1 + CHRtoINT[c]) % m1
        h2 = (h2 * b2 + CHRtoINT[c]) % m2
        B1 *= b1
        B2 *= b2
    hash = [(h1, h2)] + [None] * (len(S)-x)
    for i, c in enumerate(S[:-x]):
        h1 = (h1 * b1 - CHRtoINT[c] * B1 + CHRtoINT[S[i+x]]) % m1
        h2 = (h2 * b2 - CHRtoINT[c] * B2 + CHRtoINT[S[i+x]]) % m2
        hash[i+1] = (h1, h2)
    return hash

n, S = int(input()), input()
l, r = 0, n//2+1
while l+1 < r:
    m = (l+r)//2
    OK = False
    hash = RollingHash(S, m)
    dic = defaultdict(int)
    for i, h in enumerate(hash):
        if h in dic:
            if i - dic[h] >= m:
                OK = True
                break
        else:
            dic[h] = i
    if OK:
        l = m
    else:
        r = m
print(l)

Submission status: Accepted

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

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

        if cnt >= i:
            break
    ans = max(ans, min(cnt, i))

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    i = 1
    lcp = 0
    while i < n:
        while i+lcp < n and s[i+lcp] == s[lcp]:
            lcp += 1
        z[i] = lcp

        if lcp == 0:
            i += 1
            continue

        k = 1
        while i+k < n and k+z[k] < lcp:
            z[i+k] = z[k]
            k += 1
        i += k
        lcp -= k

    return z



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

ans = 0
for i in range(n):
    z = z_algorithm(s[i:])
    for j in range(1, n-i):
        ans = max(ans, min(j, z[j]))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
S = list(map(ord, list(input())))
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    if N-m<m:
        return False
    res = 0
    for i in range(m):
        res+=S[i]*power[m-i-1]
        res%=mod
    dic = defaultdict(lambda : -1)
    dic[res] = 0
    for i in range(N-m):
        res = ((res-S[i]*power[m-1])*base
                             +S[i+m])%mod
        if dic[res]>=0:
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False
ok = 0
ng = N+1
while ng-ok>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 zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    res = 0
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j
 
        if Z[i] <= i:
            res = max(res, Z[i])
 
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]
 
            if Z[i+k] <= i+k:
                res = max(res, Z[i+k])
 
            k += 1
        i += k
        j -= k
    return res
 
ans = 0
for i in range(N):
    _S = S[i:]
    res = zal(_S)
    ans = max(ans, res)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    dic = {}
    for i in range(N-m+1):
        s = S[i:i+m]
        if s in dic.keys():
            if dic[s]+m<=i:
                return True
        else:
            dic[s] = i
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
def f_e_dp():
    n = int(input())
    s = input()
    dp = [[0]*(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] = min(j-i, dp[i+1][j+1]+1)
    print(max([sorted(r, reverse=True)[0] for r in dp]))

if __name__ == "__main__":
    f_e_dp()

Submission status: Accepted

Solution code:
def f_e_dp():
    n = int(input())
    s = input()
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in reversed(range(n)):
        for j in reversed(range(n)):
            if s[i]==s[j] and i<j:
                dp[i][j] = dp[i+1][j+1]+1
    a = 0
    for i in range(n):
        for j in range(n):
            if i<j:
                a = max(a, min(j-i, dp[i][j]))
    print(a)

if __name__ == "__main__":
    f_e_dp()

Submission status: Accepted

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

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

ok = 0
ng = N // 2 + 1

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

print(ok)

Submission status: Accepted

Solution code:
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    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
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        S = input().rstrip()

        ans = 0
        for i in range(N - 1):
            ans = max(self.longest_common_subsequence(S[i:]), ans)

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_start, z_box_end, = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 計算済みの Z-Value(一致する文字列長)を利用
                # 一致範囲が Z-Box の範囲内
                if z[i - z_box_start] <= z_box_end - i:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 一致範囲が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    check_target = z_box_end + 1
                    while check_target < len(s) and s[check_target] == s[check_target - i]:
                        check_target += 1
                    z[i] = check_target - i
                    # Z-Box の更新
                    z_box_start, z_box_end = i, check_target - 1

        # "重ならず" の制約を値に反映          
        for i, v in enumerate(z):
            z[i] = min(v, i)

        # 最大長を返却
        return max(z[1:])


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:

N = int(input())

S = input()
CS = S

ans = 0

for i in range(N):

    now = 0
    for j in range(N):

        if S[j] == CS[j]:
            now += 1
        else:
            ans = max(ans, min(i,now) )
            now = 0

    ans = max( ans , min(i,now) )

    CS = " "+CS

print (ans)

Submission status: Accepted

Solution code:
#ABC-141-D
def main():
    n=int(input())
    s=str(input())
    
    dp=[[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(i,n):
            if i==j:
                dp[i][j]==i
                
            elif i==0:
                if s[i]==s[j]:
                    dp[i][j]=1
            
            else:
                 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(i,n):
            ans=max(ans,min(j-i,dp[i][j]))
            
    print(ans)
    
main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
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

#C
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

#D
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

#E
def E():
    n = I()
    s = S()
    l = 0
    r = n
    M = 10**640+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

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 左端＝右端だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
    return max(min(i,x) for i,x in enumerate(lcp))

def main():
    n = int(input())
    s = input()[:-1]
    ans = 0
    for i in range(n):
        ans = max(ans, LcpByZ(s[i:]))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = 0
        p = 1
        for i in range(1, len(t) + 1):
            h = hash_table[i] = (h * base + t[i - 1]) % hash_md
            p = pw[i] = p * base % hash_md

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

    n = int(input())
    s = input()[:-1]

    # 初期化
    base = 31
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0] * (len(t) + 1)
    pw = [1] * (len(t) + 1)
    hash_ini(t)

    # 長さを二分探索
    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        w = (ok + ng) // 2
        hashes = []
        for i in range(w):
            hashes.append(hash_ij(i, i + w))
        passed = set()
        for i in range(w, n - w + 1):
            passed.add(hashes[i - w])
            cur = hash_ij(i, i + w)
            if cur in passed:
                ok = w
                break
            hashes.append(cur)
        else:
            ng = w

    print(ok)

main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
for i in reversed(range(N)):
    for j in reversed(range(N)):
        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(i, N):
        ans = max(min(dp[i][j], j-i), ans)
print(ans)

Submission status: Accepted

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

def z_algorithm(str):
    len_str = len(str)
    p = [0] * len_str
    j = 0
    for i in range(1, len_str):
        if i + p[i-j] < j + p[j]:
            p[i] = p[i-j]
        else:
            k = max(0, j+p[j]-i)
            while i + k < len_str and str[k] == str[i+k]:
                k += 1
            p[i] = k
            j = i
    p[0] = len_str
    return p

ans = 0
for x in range(n):
    temp = [] + z_algorithm(s[x:])
    for y in range(n - x):
        z = min(temp[y], y)
        ans = max(ans, z)

print(ans)

Submission status: Accepted

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

length = 0 

for i in range(N):
    l1 = i
    l2 = i + length
    _word = S[l1:l2]
    _S = S[l2:]
    while _word in _S:
        l2 += 1
        _word = S[l1:l2]
        _S = S[l2:]
    length = max(len(_word)-1, length)

print(length)

Submission status: Accepted

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

length = 0 

for i in range(N):
    l1 = i
    l2 = i + length
    _word = S[l1:l2]
    _S = S[l2:]
    while _word in _S and l1 + len(_word) <= l2:
        l2 += 1
        _word = S[l1:l2]
        _S = S[l2:]
    length = max(len(_word)-1, length)

print(length)

Submission status: Accepted

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

n =1
ans = 0

for i in range(N):
    s = S[i:i+n]
    while S[i+n:].find(s) != -1:
        n += 1
        s = S[i:i+n]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# ABC141E - Who Says a Pun?
class RollingHash:
    def __init__(self, source: str, base=1000000007, mod=9007199254740997):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self):  # compute hash of interval [0, right)
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self):  # computer mod of power of base
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, l: int, r: int):  # compute hash of interval [left, right)
        return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.mod


def main():
    N = int(input())
    S = input().rstrip()
    rh, ok, ng = RollingHash(S, 27, 10 ** 9 + 7), 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, memo = 0, set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = 1
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC141E - Who Says a Pun?
class RollingHash:
    def __init__(self, source: str, base=1000000007, mod=9007199254740997):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self):  # compute hash of interval [0, right)
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self):  # computer mod of power of base
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, l: int, r: int):  # compute hash of interval [left, right)
        return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.mod


def main():
    N = int(input())
    S = input().rstrip()
    rh, ok, ng = RollingHash(S, 1007, 10 ** 9 + 7), 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, memo = 0, set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = 1
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC141E - Who Says a Pun?
class RollingHash:
    def __init__(self, source: str, base=1000000007, mod=9007199254740997):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self):  # compute hash of interval [0, right)
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self):  # computer mod of power of base
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, l: int, r: int):  # compute hash of interval [left, right)
        return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.mod


def main():
    N = int(input())
    S = input().rstrip()
    rh, ok, ng = RollingHash(S), 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, memo = 0, set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = 1
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


if __name__ == "__main__":
    main()

Submission status: Accepted

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

n = 1
ans = 0


for i in range(N):
    s = S[i:i+n]
    while S[i+n:].find(s) != -1:
        n += 1
        s = S[i:i+n]
        ans += 1
print(ans)

Submission status: Accepted

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

max = 0
index = 0
for i in range(1,len(S)-1):
    s1=S[index:i]
    s2=S[i:]
    if s1 in s2:
        max=len(s1)
    else:
        index+=1
        
print(max)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l1 = length = 0
l2 = 1

while (l2 + length < N):
    if S[l1:l2] in S[l2:]:
        length = l2 - l1
        l2 += 1
    else:
        l1 += 1
        l2 = l1 + length + 1
print(length)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    l1 = length = 0
    l2 = 1

    while (l2 + length < N):
        if S[l1:l2] in S[l2:]:
            length = l2 - l1
            l2 += 1
        else:
            l1 += 1
            l2 = l1 + length + 1
    print(length)

main()

Submission status: Accepted

Solution code:
N=int(input())
S=input()
l,u=0,N
while l+1<u:
    m=(l+u)//2
    s=set()
    for i in range(N-m*2+1):
        s.add(S[i:i+m])
        if S[i+m:i+m*2] in s:
            l=m
            break
    if l!=m:
        u=m
print(l)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
sride = 1
count = 0
max_num = 0
for i in range(N-1):
  for j in range(N-sride):
    if S[j] == S[j+sride]:
      count += 1
      max_num = max(max_num, count)
    else:
      count = 0
    if count == sride:
      break
  sride += 1
  count = 0
print(max_num)