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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SuffixArray:

    class SparseTable:

        def __init__(self, A, func):
            self.N = len(A)
            self.func = func
            h = 0
            while 1<<h < self.N:
                h += 1
            self.dat = list2d(h, 1<<h, 0)
            self.height = [0] * (self.N+1)

            for i in range(2, self.N+1):
                self.height[i] = self.height[i>>1] + 1
            for i in range(self.N):
                self.dat[0][i] = A[i]
            for i in range(1, h):
                for j in range(self.N):
                    self.dat[i][j] = self.func(self.dat[i-1][j], self.dat[i-1][min(j+(1<<(i-1)), self.N-1)])
            
        def get(self, l, r):
            """ 区間[l,r)でのmin,maxを取得 """

            a = self.height[r-l]
            return self.func(self.dat[a][l], self.dat[a][r-(1<<a)])

    def __init__(self, S):
        self.k = 1
        self.S = S
        self.N = len(S)
        self.rank = [0] * (self.N+1)
        self.tmp = [0] * (self.N+1)
        self.sa = [0] * (self.N+1)
        self.build_sa()

    # def compare_sa(self, i, j):
    #     if self.rank[i] != self.rank[j]:
    #         return self.rank[i] < self.rank[j]
    #     else:
    #         ri = self.rank[i+self.k] if i + self.k <= self.N else -1
    #         rj = self.rank[j+self.k] if j + self.k <= self.N else -1
    #         return ri < rj

    def compare_sa(self, i, j):
        """ saの比較関数 """

        # 第1キー
        if self.rank[i] == self.rank[j]: res1 =  0
        elif self.rank[i] < self.rank[j]: res1 =  -1
        else: res1 = 1
        # 第2キー
        ri = self.rank[i+self.k] if i + self.k <= self.N else -1
        rj = self.rank[j+self.k] if j + self.k <= self.N else -1
        if ri == rj: res2 = 0
        elif ri < rj: res2 = -1
        else: res2 = 1
        # 比較
        return res1 or res2

    def build_sa(self):
        """ Suffix Arrayの構築 """
        from functools import cmp_to_key

        # 最初は1文字、ランクは文字コード
        for i in range(self.N+1):
            self.sa[i] = i
            self.rank[i] = ord(self.S[i]) if i < self.N else -1

        # k文字についてソートされているところから、　2k文字でソートする
        k = 1
        while k <= self.N:
            self.k = k
            self.sa = sorted(self.sa, key=cmp_to_key(self.compare_sa))
            k *= 2

            # いったんtmpに次のランクを計算し、それからrankに移す
            self.tmp[self.sa[0]] = 0
            for i in range(1, self.N+1):
                self.tmp[self.sa[i]] = self.tmp[self.sa[i-1]] + (1 if self.compare_sa(self.sa[i-1], self.sa[i]) else 0)
            for i in range(self.N+1):
                self.rank[i] = self.tmp[i]

    def build_lcp(self):
        """ LCP配列の構築 """

        self.lcp = [0] * (self.N+1)
        self.rsa = [0] * (self.N+1)
        for i in range(self.N+1):
            self.rsa[self.sa[i]] = i
        h = 0
        self.lcp[0] = 0
        for i in range(self.N):
            # 文字列内での位置iの接尾辞と、接尾辞配列内でその1つ前の接尾辞のLCPを求める
            j = self.sa[self.rsa[i]-1]

            # hを先頭の分1減らし、後ろが一致しているだけ増やす
            if h > 0:
                h -= 1
            while j+h < self.N and i+h < self.N:
                if self.S[j+h] != self.S[i+h]:
                    break
                h += 1
            self.lcp[self.rsa[i]-1] = h

        # 区間取得のためSparseTableを構築
        self.st = self.SparseTable(self.lcp, min)

    def getLCP(self, i, j):
        """ S[i:]とS[j:]の共通文字数を取得 """

        return self.st.get(min(self.rsa[i], self.rsa[j]), max(self.rsa[i], self.rsa[j]))

N = INT()
S = input()

sa = SuffixArray(S)
sa.build_lcp()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        lcp = min(sa.getLCP(i, j), j - i)
        ans = max(ans, lcp)
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SparseTable:

    def __init__(self, A, func):
        self.N = len(A)
        self.func = func
        h = 0
        while 1<<h < self.N:
            h += 1
        self.dat = list2d(h, 1<<h, 0)
        self.height = [0] * (self.N+1)

        for i in range(2, self.N+1):
            self.height[i] = self.height[i>>1] + 1
        for i in range(self.N):
            self.dat[0][i] = A[i]
        for i in range(1, h):
            for j in range(self.N):
                self.dat[i][j] = self.func(self.dat[i-1][j], self.dat[i-1][min(j+(1<<(i-1)), self.N-1)])
        
    def get(self, l, r):
        """ 区間[l,r)でのmin,maxを取得 """

        a = self.height[r-l]
        return self.func(self.dat[a][l], self.dat[a][r-(1<<a)])

class SuffixArray:

    def __init__(self, S):
        self.k = 1
        self.S = S
        self.N = len(S)
        self.rank = [0] * (N+1)
        self.tmp = [0] * (N+1)
        self.sa = [0] * (N+1)
        self.build_sa()

    # def compare_sa(self, i, j):
    #     if self.rank[i] != self.rank[j]:
    #         return self.rank[i] < self.rank[j]
    #     else:
    #         ri = self.rank[i+self.k] if i + self.k <= self.N else -1
    #         rj = self.rank[j+self.k] if j + self.k <= self.N else -1
    #         return ri < rj

    # saの比較関数
    def compare_sa(self, i, j):
        # 第1キー
        if self.rank[i] == self.rank[j]: res1 =  0
        elif self.rank[i] < self.rank[j]: res1 =  -1
        else: res1 = 1
        # 第2キー
        ri = self.rank[i+self.k] if i + self.k <= self.N else -1
        rj = self.rank[j+self.k] if j + self.k <= self.N else -1
        if ri == rj: res2 = 0
        elif ri < rj: res2 = -1
        else: res2 = 1
        # 比較
        return res1 or res2

    # Suffix Arrayの構築
    def build_sa(self):
        from functools import cmp_to_key

        # 最初は1文字、ランクは文字コード
        for i in range(N+1):
            self.sa[i] = i
            self.rank[i] = ord(self.S[i]) if i < self.N else -1
    
        # k文字についてソートされているところから、　2k文字でソートする
        k = 1
        while k <= self.N:
            self.k = k
            self.sa = sorted(self.sa, key=cmp_to_key(self.compare_sa))
            k *= 2

            # いったんtmpに次のランクを計算し、それからrankに移す
            self.tmp[self.sa[0]] = 0
            for i in range(1, self.N+1):
                self.tmp[self.sa[i]] = self.tmp[self.sa[i-1]] + (1 if self.compare_sa(self.sa[i-1], self.sa[i]) else 0)
            for i in range(self.N+1):
                self.rank[i] = self.tmp[i]
    
    # LCP配列の構築
    def build_lcp(self):

        self.lcp = [0] * (N+1)
        self.rsa = [0] * (N+1)
        for i in range(self.N+1):
            self.rsa[self.sa[i]] = i
        h = 0
        self.lcp[0] = 0
        for i in range(self.N):
            # 文字列内での位置iの接尾辞と、接尾辞配列内でその1つ前の接尾辞のLCPを求める
            j = self.sa[self.rsa[i]-1]

            # hを先頭の分1減らし、後ろが一致しているだけ増やす
            if h > 0:
                h -= 1
            while j+h < self.N and i+h < self.N:
                if self.S[j+h] != self.S[i+h]:
                    break
                h += 1
            self.lcp[self.rsa[i]-1] = h

        # 区間取得のためSparseTableを構築
        self.st = SparseTable(self.lcp, min)
    
    # S[i:]とS[j:]の共通文字数を取得
    def getLCP(self, i, j):
        return self.st.get(min(self.rsa[i], self.rsa[j]), max(self.rsa[i], self.rsa[j]))

N = INT()
S = input()

sa = SuffixArray(S)
sa.build_lcp()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        lcp = min(sa.getLCP(i, j), j - i)
        ans = max(ans, lcp)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=0
r=n
while r-l!=1:
  mid=(r+l)//2
  dic={}
  flag=False
  for i in range(n-mid+1):
    tmp=s[i:i+mid]
    if tmp not in dic:
      dic[tmp]=i+mid
    else:
      if dic[tmp]<=i:
        flag=True
        break
  if flag==True:
    l=mid
  else:
    r=mid
print(l)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    s = input()
    a,i,j = 0,0,1
    
    while j < N:
        if s[i:j] in s[j:]:
            a = max(a,j-i)
            j += 1
        else:
            i += 1
        if i == j:
            i += 1
            j += 2
            
    print(a)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for v in range(N):
    for h in range(N):
        if h == 0 or v == 0:
            if S[v] == S[h]:
                dp[v][h] = min(1, abs(v-h))
        elif S[v] == S[h]:
            dp[v][h] = min(dp[v-1][h-1] + 1, abs(v-h))

ans = 0
for i in range(N):
    tmp = max(dp[i])
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Accepted

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    A = [A[i] if A[i] <= i else 0 for i in range(N)]
    return max(A)

ans = 0
for i in range(n):
    ans = max(ans, z_algo(s[i:]))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
lb, ub = -1, N//2 + 1
while ub - lb > 1:
    m = (lb + ub) // 2
    s1 = S[:m]
    s2 = S[m:2*m]
    ss = set()
    ok = False
    for i in range(2*m, N):
        ss.add(s1)
        if s2 in ss:
            ok = True
            break
        s1 = s1[1:] + s2[0]
        s2 = s2[1:] + S[i]
    ss.add(s1)
    if s2 in ss:
        ok = True
    if ok:
        lb = m
    else:
        ub = m
print(lb)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
def output():
    left, right = 0, n//2+1
    while left < right-1:
        mid = (left+right)//2
        if check(mid):
            left = mid
        else:
            right = mid
    return left
def check(x):
    hashes = set()
    for i in range(n - 2*x + 1):
        hashes.add(s[i: i+x])
        if s[i+x: i+2*x] in hashes:
            return True
    return False
print(output())

Submission status: Accepted

Solution code:
import hashlib

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


def output():
    left, right = 0, n//2+1
    while left < right-1:
        mid = (left+right)//2
        if check(mid):
            left = mid
        else:
            right = mid
    return left


def check(x):
    hashes = set()
    for i in range(n - 2*x + 1):
        hashes.add(s[i: i+x])
        if s[i+x: i+2*x] in hashes:
            return True
    return False


print(output())

Submission status: Accepted

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

l = 0
r = 1
ans = 0
# 順番に見ていく

while r < n:
  if s[l:r] in s[r:]:
    ans = max(ans, r - l)
    r += 1
  else:
    l += 1
  if l == r:
    l += 1
    r += 2
print(ans)

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

if __name__ == "__main__":
    n = int(input())
    s = input().rstrip()
    ord_base = ord("a") - 1
    a = [ord(ch) - ord_base for ch in s]
    SA = SuffixArray(a)
    ans = 0
    for i in range(n+1):
        for j in range(i+1, n+1):
            val = SA.get_lcp(i, j)
            if val > j - i:
                val = j - i
            if val > ans:
                ans = val
    print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    dp = [[0] * 5005 for _ in range(5005)]
    for i in range(N-1,-1,-1):
        for j in range(N-1,-1,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1

    ans = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            ans = max(ans, now)

    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import groupby

N=int(input())
S=input()
def condition(num):
    if num==0:
        return True
    else:
        flag=0
        data=[]
        for i in range(0,N-num+1):
            data.append([S[i:i+num],i])
        data.sort()
        partdata=[data[i][0] for i in range(0,len(data))]
        partdata=groupby(partdata)
        subdata=[]
        for key,group in partdata:
            g=len(list(group))
            subdata.append(g)
        s=0
        t=subdata[0]-1
        if len(subdata)==1:
            if data[t][1]-data[s][1]>=num:
                flag=1
        for i in range(0,len(subdata)-1):
            if data[t][1]-data[s][1]>=num:
                flag=1
            s=t+1
            t=t+subdata[i+1]
        if data[t][1]-data[s][1]>=num:
            flag=1
        return flag==1

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)

Submission status: Accepted

Solution code:
def z_algorithm(S):
    n = len(S)
    A = [0] * n
    A[0] = n
    L = 0
    R = 0
    # 過去にS[R]まで調べたとする
    for i in range(1, n):
        if R <= i:
            L = R = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
        elif A[i - L] < R - i:
            A[i] = A[i - L]
        else:
            L = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
    return A


def main():
    N = int(input())
    S = input()
    answer = 0
    for i in range(N):
        a = z_algorithm(S[i:])
        for j in range(1, N - i):
            cnt = min(j, a[j])
            if cnt > answer:
                answer = cnt

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	SS = IS()
	ans = 0
	for l in range(N-1):
		i = 1
		j = 0
		S = copy.copy(SS[l:])
		A = [0]*len(S)
		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
		for m in range(len(S)):
			ans = max(ans, min(m, A[m]))
	print(ans)

main()

Submission status: Accepted

Solution code:
def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans


n = int(input())
S = input()

candidates = []
for i in range(n):
    candidates.append(z_algolithm(S, i))

print(max(candidates))

Submission status: Accepted

Solution code:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R1=RollingHash(S,37,10**9+7)
R2=RollingHash(S,29,10**9+9)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=(R1.get(l,l+ln),R2.get(l,l+ln))
        if tmp in D:
            if D[tmp]+ln<=l:
                ans=max(ln,ans)
        else:
            D[tmp]=l
print(ans)

Submission status: Accepted

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

s=[[0]*N for i in range(N)]
k=0
for k in range(N):
  s[k]= [0]*k + z_algo(S[k:])

ans=0
for i in range(N):
  for j in range(i+1,N):
    if s[i][j]+i > j:
      ans = max(ans,j - i)
    else:
      ans=max(s[i][j],ans)
    
print(ans)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 二分探索
N = ir()
S = sr()

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

left = 0 # 可能
right = N
while right > left + 1:
    mid = (right+left) // 2
    if check(mid):
        left = mid
    else:
        right = mid

print(left)
# 54

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
dp = [[0 for i in range(n+5)] for j in range(n+5)]
res = 0
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if i >= j: continue
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
        else:
            dp[i][j] = 0
for i in range(n):
    for j in range(n):
        tmp = min(j-i, dp[i][j])
        res = max(res, tmp)
print(res)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1; j = 0
    A[0] = l = N
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
res = 0
for i in range(n):
    c = z_algo(s[i:])
    # print(c)
    for j,t in enumerate(c):
        tmp = min(j,t)
        res = max(res, tmp)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]

for l in range(N)[::-1]:
    for r in range(l+1, N)[::-1]:
        dp[l][r] = dp[l+1][r+1]+1 if S[l]==S[r] else 0

ans = 0 
for l in range(N)[::-1]:
    for r in range(l+1, N)[::-1]:
        ans = max(ans, min(r-l, dp[l][r]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def z_algo(S):
    N = len(S)

    A = [0] * N
    A[0] = N
    i = 1
    j = 0

    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N - i > k < j - A[k]:
            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):
    A = z_algo(S[i:])
    for idx, length in enumerate(A):
        if idx + 1 > length:
            ans = max(ans, length)

print(ans)

Submission status: Accepted

Solution code:
def z_algorithm(s):
  n = len(s)
  z = [None] * n
  z[0] = n
  
  i = 1
  j = 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 z[k] + k < j:
      z[i + k] = z[k]
      k += 1
    i += k
    j -= k
  return z

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

answer = 0
for j in range(N):
  T = S[j:]
  Z = z_algorithm(T + "$" + S)
  lenT = len(T)
  lenZ = len(Z)
  for i in range(lenT, lenZ - lenT):
    if i + Z[i] < lenZ - lenT + 1:
      answer = max(answer, Z[i])

print(answer)

Submission status: Accepted

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N):
    X = S[:N-k]
    Y = S[k:]
    cur = 0
    cnt = 0
    for i in range(N-k):
        if X[i]!=Y[i]:
            cmax = max(cmax,min(cnt,k))
            cur = i
            cnt = 0
        else:
            cnt += 1
    cmax = max(cmax,min(cnt,k))
print(cmax)