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:
import sys
def input(): return sys.stdin.readline().rstrip()


def is_ok(arg, S):
    # 条件を満たすかどうか？問題ごとに定義
    dic = {}
    ans = False
    for i in range(len(S)-arg+1):
        c = S[i:i+arg]
        if c in dic:
            if i-dic[c] >= arg:
                ans = True
                break
        else:
            dic[c] = i
    return ans


def meguru_bisect(ng, ok, S):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, S):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    N = int(input())
    S = input()
    print(meguru_bisect((N//2)+1, -1, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

l = 0 # max proven possible
r = N # min proven impossible
while l + 1 < r:
  x = (l + r) // 2
  first_loc = {}
  possible = False
  for i in range(N-x+1):
    #print(i, N-x, first_loc)
    sub = S[i:i+x]
    #print(sub)
    if sub in first_loc:
      if first_loc[sub] <= i - x:
        #print(sub, first_loc[sub], i, x, i-x)
        possible = True
        break
    else:
      first_loc[sub] = i
  if possible:
    l = x
  else:
    r = x
print(l)

Submission status: Accepted

Solution code:
class DisjointSparseTable:
    def __init__(self, a, op=lambda a, b: max(a, b), e=0):
        # Operator
        self.op = op
        # Identity element
        self.e = e
        self.n = len(a)
        self.level = (self.n - 1).bit_length()
        self.size = 2 ** self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()

    def build(self):
        for i in range(1, self.level):
            step = 2 ** i
            lv = self.level - 1 - i
            for mid in range(step, self.n + step, step * 2):
                # Forward
                val = self.e
                for j in range(step):
                    val = self.op(val, self.table[-1][mid + j])
                    self.table[lv][mid + j] = val
                # Backward
                val = self.e
                for j in range(step):
                    val = self.op(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val

    # Returns f[l:r)
    def fold(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r - 1).bit_length()
        return self.op(self.table[lv][l], self.table[lv][r - 1])


class SuffixArray:
    def __init__(self, S):
        ord_base = ord("a") - 1
        a = [ord(ch) - ord_base for ch in S]
        self.a = a + [0]
        self.k = max(self.a) + 1
        self.n = len(self.a)
        self.sa = self.SA_IS(self.a, self.n, self.k)
        # Construct LCP disjoint sparse table
        self.rank = [0] * self.n
        for i, item in enumerate(self.sa):
            self.rank[item] = i
        self.lcp = self.build_LCP(self.a, self.sa, self.rank)
        self.lcp_dst = DisjointSparseTable(self.lcp, op=lambda a, b: min(a, b), e=10 ** 9)

    # Find the start or end of each bucket
    def get_buckets(self, a, k, end=True):
        bucket = [0] * k
        for item in a:
            bucket[item] += 1
        sumation = 0
        for i in range(k):
            sumation += bucket[i]
            if end:
                bucket[i] = sumation
            else:
                bucket[i] = sumation - bucket[i]
        return bucket

    def induce_SAl(self, a, sa, n, k, lstype):
        bucket = self.get_buckets(a, k, end=False)
        for i in range(n):
            j = sa[i] - 1
            if j >= 0 and (not lstype & (1 << j + 1)):
                sa[bucket[a[j]]] = j
                bucket[a[j]] += 1

    def induce_SAs(self, a, sa, n, k, lstype):
        bucket = self.get_buckets(a, k, end=True)
        for i in range(n - 1, -1, -1):
            j = sa[i] - 1
            if j >= 0 and lstype & (1 << j + 1):
                bucket[a[j]] -= 1
                sa[bucket[a[j]]] = j

    def is_LMS(self, index, lstype):
        return lstype >> (index + 1) & 1 and not (lstype >> index & 1)

    def is_stype(self, index, lstype):
        return lstype >> (index + 1) & 1

    def SA_IS(self, a, n, k):
        # L-type or S-type
        # LS-type array in bits, 1-indexed, initialized with S-type first
        lstype = 1
        prev_type = 0
        prev_item = self.k
        for i, item in enumerate(a[::-1]):
            shift = n - i
            if item == prev_item:
                lstype |= prev_type << shift
            elif item < prev_item:
                lstype |= 1 << shift
                prev_type = 1
            else:
                prev_type = 0
            prev_item = item
        # Bucket array
        bucket = self.get_buckets(a, k)
        # Find ends of buckets
        sa = [-1] * n
        for i in range(n - 1, 0, -1):
            if self.is_LMS(i, lstype):
                bucket[a[i]] -= 1
                sa[bucket[a[i]]] = i
        self.induce_SAl(a, sa, n, k, lstype)
        self.induce_SAs(a, sa, n, k, lstype)

        lcm_cnt = 0
        for i in range(n):
            if self.is_LMS(sa[i], lstype):
                sa[lcm_cnt] = sa[i]
                lcm_cnt += 1
        for i in range(lcm_cnt, n):
            sa[i] = -1

        # Rename LCM strings
        name = 1;
        prev = sa[0]
        sa[lcm_cnt + sa[0] // 2] = 0
        for pos in sa[1: lcm_cnt]:
            diff = False
            for d in range(n):
                if a[pos + d] != a[prev + d] or (self.is_stype(pos + d, lstype) != self.is_stype(prev + d, lstype)):
                    diff = True
                    break
                elif d > 0 and (self.is_LMS(pos + d, lstype) or self.is_LMS(prev + d, lstype)):
                    break
            if diff:
                name += 1;
                prev = pos
            pos //= 2
            sa[lcm_cnt + pos] = name - 1
        sub_a = []
        for i in range(lcm_cnt, n):
            if sa[i] >= 0:
                sub_a.append(sa[i])

        # Recursively sort LMS sub strings
        if name < lcm_cnt:
            sub_sa = self.SA_IS(sub_a, len(sub_a), name + 1)
        else:
            sub_sa = sa[:lcm_cnt]
            for i in range(lcm_cnt):
                sub_sa[sub_a[i]] = i
        bucket = self.get_buckets(a, k, end=True)
        j = 0
        for i in range(1, n):
            if self.is_LMS(i, lstype):
                sub_a[j] = i
                j += 1
        # Earn correctly sorted LCMs
        for i in range(lcm_cnt):
            sa[i] = sub_a[sub_sa[i]]
        for i in range(lcm_cnt, n):
            sa[i] = -1
        for i in range(lcm_cnt - 1, -1, -1):
            j = sa[i];
            sa[i] = -1
            bucket[a[j]] -= 1
            sa[bucket[a[j]]] = j

        # Correct induced sorting
        self.induce_SAl(a, sa, n, k, lstype)
        self.induce_SAs(a, sa, n, k, lstype)
        return sa

    def build_LCP(self, a, sa, rank):
        # Add sentinel
        sa.append(-1)
        lcp = [0] * len(a)
        same_cnt = 0
        for index1 in range(len(a)):
            if same_cnt != 0:
                same_cnt -= 1
            index2 = sa[rank[index1] + 1]
            while a[index1 + same_cnt] == a[index2 + same_cnt]:
                same_cnt += 1
            lcp[rank[index1]] = same_cnt
        # Remove sentinel
        sa.pop()
        return lcp

    def get_lcp(self, l, r):
        rank_l = self.rank[l]
        rank_r = self.rank[r]
        if rank_l > rank_r:
            rank_l, rank_r = rank_r, rank_l
        return self.lcp_dst.fold(rank_l, rank_r)

    def search(self, b):
        m = len(b)
        l = 0;
        r = self.n + 1
        matched = 0
        while r - l > 1:
            mid = (l + r) // 2
            lm_lcp = self.get_lcp(l, mid)
            if matched < lm_lcp:
                l = mid
            elif matched > lm_lcp:
                r = mid
            else:
                a_itr = self.sa[mid] + matched;
                b_itr = matched
                diff = 0
                while b_itr < m and a_itr < self.n:
                    if b[b_itr] != self.a[a_itr]:
                        diff = b[b_itr] - self.a[a_itr]
                        break
                    a_itr += 1;
                    b_itr += 1
                if diff >= 0:
                    l = mid
                    matched = b_itr
                else:
                    r = mid
        return matched, l

def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y

res = 0
N = int(input())
S = input()
SA = SuffixArray(S)
for i in range(N + 1):
    for j in range(i + 1, N + 1):
        lcp = SA.get_lcp(i, j)
        temp = min2(lcp, j-i)
        res = max2(res, temp)
print(res)

Submission status: Accepted

Solution code:
def Z_algo(S):
    L = len(S)
    lcp = [0]*L
    i = 1
    j = 0
    lcp[0] = L
    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 i + k < L and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    return lcp

def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y

res = 0
N = int(input())
S = input()
for i in range(N):
    lcp = Z_algo(S[i:])
    for j, s in enumerate(lcp):
        temp = min2(s, j)
        res = max2(res, temp)
print(res)

Submission status: Accepted

Solution code:
def z_al(s):
    le = len(s)
    res = [0 for i in range(le)]
    i, j = 1, 0
    while i < le:
        while i + j < le and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < le and res[k] + k < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
n = int(input())
s = input()
ans = 0
for i in range(n):
    s2 = s[i:]
    res = z_al(s2)
    for j in range(len(s2)):
        ans = max(ans, min(res[j], j))
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

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

print(ans)

Submission status: Accepted

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

lb=0
rb=N+1
while rb-lb>1:
    mid = (lb + rb) // 2
    x = 0
    for i, s in enumerate(S[:mid]):
        x += pow(26, i) * (ord(s) - ord('a'))
    m = pow(26, mid - 1)
    a = [x]
    for i, s in enumerate(S[mid:]):
        x -= ord(S[i]) - ord('a')
        x //= 26
        x += m * (ord(s) - ord('a'))
        a += [x]
    f = 0
    se = set([])
    for i, x in enumerate(a):
        if i >= mid:
            se.add(a[i - mid])
        if x in se:
            f = 1
            break
    if f:
        lb=mid
    else:
        rb=mid
print(lb)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

def main(N, S):
    dp = np.zeros((N + 1, N + 1), dtype=np.int64)
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i,j] = min(j - i, dp[i - 1,j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8[:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    from my_module import main
    N = int(input())
    S = np.array([ord(_) for _ in input()])
    print(main(N, S))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

def main(N, S, dp):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i,j] = min(j - i, dp[i - 1,j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8[:],i8[:,:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    from my_module import main
    N = int(input())
    S = np.array([ord(_) for _ in input()])
    dp = np.zeros((N + 1, N + 1), dtype=int)
    print(main(N, S, dp))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

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 max(min(i,Z_alg[i]) for i in range(N))

N = I()
S = S()
ans = 0
while len(S):
  ans = max(ans,Z_algorithm(S))
  S = S[1:]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding:utf-8

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    from collections import defaultdict
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    P1 = 2**127-1
    P2 = 2**31-1
    P1 = 10**9*7
    P2 = 10**7-9
    base = 26
    N = II()
    S = list(map(ord,list(input())))
    pow1 = [1]*N
    pow2 = [1]*N
    for i in range(N-1):
        pow1[i+1] = pow1[i]*base%P1
        pow2[i+1] = pow2[i]*base%P2
    hash1 = [0]*(N+1)
    hash2 = [0]*(N+1)
    hash1[1] = hash2[1] = S[0]
    for i in range(2,N+1):
        hash1[i] = (hash1[i-1]*base + S[i-1]) % P1
        hash2[i] = (hash2[i-1]*base + S[i-1]) % P2
    
    def f(x):
        hashes = defaultdict(lambda : -1)
        for i in range(N-x+1):
            #S[i:i+x]
            h1 = (hash1[i+x] - hash1[i] * pow1[x]) % P1
            h2 = (hash2[i+x] - hash2[i] * pow2[x]) % P2
            if hashes[(h1,h2)] == -1:
                hashes[(h1,h2)] = i
            elif hashes[(h1,h2)] + x <= i:
                return True
        # print(hashes)
        return False
    
    ok = -1
    ng = N//2+1
    while ng-ok > 1:
        
        m = (ok+ng)//2
        # print(m)
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    from collections import defaultdict
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    P1 = 2**127-1
    P2 = 2**31-1
    base = 26
    N = II()
    S = list(map(ord,list(input())))
    pow1 = [1]*N
    pow2 = [1]*N
    for i in range(N-1):
        pow1[i+1] = pow1[i]*base%P1
        pow2[i+1] = pow2[i]*base%P2
    hash1 = [0]*(N+1)
    hash2 = [0]*(N+1)
    hash1[1] = hash2[1] = S[0]
    for i in range(2,N+1):
        hash1[i] = (hash1[i-1]*base + S[i-1]) % P1
        hash2[i] = (hash2[i-1]*base + S[i-1]) % P2
    
    def f(x):
        hashes = defaultdict(lambda : -1)
        for i in range(N-x+1):
            #S[i:i+x]
            h1 = (hash1[i+x] - hash1[i] * pow1[x]) % P1
            h2 = (hash2[i+x] - hash2[i] * pow2[x]) % P2
            if hashes[(h1,h2)] == -1:
                hashes[(h1,h2)] = i
            elif hashes[(h1,h2)] + x <= i:
                return True
        # print(hashes)
        return False
    
    ok = -1
    ng = N//2+1
    while ng-ok > 1:
        
        m = (ok+ng)//2
        # print(m)
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
S = LS2()


def Z_algorithm(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
        if j == 0:
            i += 1
            continue
        # S[0:j] == S[i:i+j] となっている
        A[i] = j
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A


ans = 0
for i in range(N):
    A = Z_algorithm(S)
    for j in range(N-i):
        if A[j] <= j:
            ans = max(ans,A[j])
    del S[0]

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    # flags[n][m]: n 番目の文字と同じ文字がその m 個後にあれば1
    flags = [[0] * N for _ in range(N)]
    for n, c in enumerate(S):
        for m in range(1, N - n):
            if c == S[n + m]:
                flags[n][m] = 1
    ans = 0
    for m in range(1, N):
        from_n = -1
        for to_n in range(N):
            if flags[to_n][m] == 0:
                ans = max(ans, min(m, to_n - from_n - 1))
                from_n = to_n
        if from_n != to_n:
            ans = max(ans, min(m, to_n - from_n - 1))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    print(res)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
 
max_len = 0
j = 0
 
for i in range(n):
    while j < n and s[i:j] in s[j:]:
        j += 1
    max_len = max(max_len,j-i-1)
 
print(max_len)

Submission status: Accepted

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

def kAlgo(S, N):
    szS = N
    Z = [0]*szS
    Z[0] = szS
    i = 1 #current pos
    j = 0 #伸ばす幅
    while i < szS:
        while (i + j < szS) and (S[j] == S[i+j]): j += 1
        #set Z[i]
        Z[i] = j

        if j == 0:
            i += 1
            continue

        #optimize
        k = 1
        while (k < j) and (k + Z[k] < j):
            Z[i+k] = Z[k]
            k += 1

        i += k
        j -= k

    ans = 0
    for i in range(N):
        if Z[i] > i: Z[i] = i
    return max(Z[1:])

ans = 0
for i in range(N-1):
    lenz = kAlgo(S[i:], N-i)
    if ans < lenz:
        ans = lenz

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
ans = 0
j = 0
for i in range(N):
  while j < N and S[i:j] in S[j:]:
    j += 1
  ans = max(ans,j-i-1)
print(ans)

Submission status: Accepted

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

max_len = 0
j = 0

for i in range(n):
    while j < n and s[i:j] in s[j:]:
        j += 1
    max_len = max(max_len,j-i-1)

print(max_len)

Submission status: Accepted

Solution code:
class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7) -> None:
        self._base = base
        self._mod = mod
        self._hash = [0] * (len(source) + 1)
        self._power = [0] * (len(source) + 1)

        self._power[0] = 1
        for i, c in enumerate(source, 1):
            self._hash[i] = (self._hash[i - 1] * self._base + ord(c)) % self._mod
            self._power[i] = self._power[i - 1] * self._base % self._mod

    def get_hash(self, left: int, right: int) -> int:
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                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__":
    abc141_e()

Submission status: Accepted

Solution code:
from typing import List, Tuple


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash, self._power = self._build(source)

    def _build(self, source: str) -> Tuple[List[int], List[int]]:
        """Compute "hash" and "mod of power of base" of interval [0, right)."""
        hash_, power = [0] * (len(source) + 1), [0] * (len(source) + 1)
        power[0] = 1
        for i, c in enumerate(source, 1):
            hash_[i] = (hash_[i - 1] * self._base + ord(c)) % self._mod
            power[i] = power[i - 1] * self._base % self._mod
        return hash_, power

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                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__":
    abc141_e()

Submission status: Accepted

Solution code:
from typing import List, Tuple


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash, self._power = self._build(source)

    def _build(self, source: str) -> Tuple[List[int], List[int]]:
        """Compute "hash" and "mod of power of base" of interval [0, right)."""
        length = len(source)
        hash_, power = [0] * (length + 1), [0] * (length + 1)
        power[0] = 1
        for i, c in enumerate(source, 1):
            hash_[i] = (hash_[i - 1] * self._base + ord(c)) % self._mod
            power[i] = power[i - 1] * self._base % self._mod
        return hash_, power

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                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__":
    abc141_e()

Submission status: Accepted

Solution code:
# ABC141E - Who Says a Pun?
def resolve():
    N = int(input())
    S = input().rstrip()
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(hash(S[i : i + mid]))
            if hash(S[i + mid : i + 2 * mid]) in memo:
                flg = True
                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


resolve()