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:
from typing import List


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._build_hash_from_zero(source)
        self._power = self._build_base_power(len(source))

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

    def _build_base_power(self, length: int) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (length + 1)
        for i in range(1, length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    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


class RollingHash:
    """Rolling Hash"""

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

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

    def _build_hash_from_zero(self, source: str) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        for i, c in enumerate(source, 1):
            res[i] = (res[i - 1] * self._base + ord(c)) % self._mod
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        for i in range(1, self._length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    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


class RollingHash:
    """Rolling Hash"""

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

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

    def _build_hash_from_zero(self) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        prev = 0
        for i, c in enumerate(self._source, 1):
            res[i] = (prev * self._base + ord(c)) % self._mod
            prev = res[i]
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        prev = 1
        for i in range(1, self._length + 1):
            res[i] = prev * self._base % self._mod
            prev = res[i]
        return res

    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


class RollingHash:
    """Rolling Hash"""

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

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

    def _build_hash_from_zero(self) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        for i, c in enumerate(self._source, 1):
            res[i] = (res[i - 1] * self._base + ord(c)) % self._mod
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        for i in range(1, self._length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    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


class RollingHash:
    __slots__ = ["_source", "_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        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) -> List[int]:
        """Compute hash of interval [0, right)."""
        hash_from_zero = [0] * (self._length + 1)
        cur = 0
        for i, c in enumerate(self._source, 1):
            cur = (cur * self._base + ord(c)) % self._mod
            hash_from_zero[i] = cur
        return hash_from_zero

    def _get_base_pow(self) -> List[int]:
        """Compute mod of power of base."""
        power = [0] * (self._length + 1)
        power[0] = 1
        cur = 1
        for i in range(1, self._length + 1):
            cur *= self._base % self._mod
            power[i] = cur
        return power

    def get_hash(self, left: int, right: int):
        """Compute 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


class RollingHash:
    __slots__ = ["source", "length", "base", "mod", "hash", "power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        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) -> List[int]:
        """Compute hash of interval [0, right)."""
        hash_from_zero = [0] * (self.length + 1)
        cur = 0
        for i, c in enumerate(self.source, 1):
            cur = (cur * self.base + ord(c)) % self.mod
            hash_from_zero[i] = cur
        return hash_from_zero

    def _get_base_pow(self) -> List[int]:
        """Compute mod of power of base."""
        power = [1] * (self.length + 1)
        cur = 1
        for i in range(1, self.length + 1):
            cur *= self.base % self.mod
            power[i] = cur
        return power

    def get_hash(self, left: int, right: int):
        """Compute 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


class RollingHash:
    __slots__ = ["source", "length", "base", "mod", "hash", "power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        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) -> List[int]:
        """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) -> List[int]:
        """Compute 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, left: int, right: int):
        """Compute 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, 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__":
    abc141_e()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


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

"""
Z algorithm
def Z(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    L, R = 0, 0
    for i in range(1, n):
        if i >= R:
            L = R = i
            # 一致が続く限り伸ばす
            while(R < n and s[R - L] == s[R]):
                R += 1
            # LCAを書き込む
            # 頭から一致しない場合はR - L = i - i = 0
            z[i] = R - L
        # 全て利用できる場合
        elif z[i - L] < R - i:
            z[i] = z[i - L]
        # 一部利用できる場合
        else:
            L = i
            while(R < n and s[R - L] == s[R]):
                R += 1
            z[i] = R - L
    return z

# [5, 0, 3, 0, 1]
#print(Z('ababa'))

N = getN()
S = input()
ans = 0
for i in range(N):
    z = Z(S[i:])
    k = len(z)
    for j in range(k):
        # '' と 'ababa'
        # 'a' と 'baba'
        # 'ab' と 'aba'
        # ans は j('', 'a', 'ab')の長さ以上にならない（ダブらないため）
        ans = max(ans, min(j, z[j]))
print(ans)
"""

# Rolling hash
N = getN()
S = list(map(ord, list(input())))
# 適当
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 = {res: 0}
    for i in range(N - m):
        res = ((res - S[i] * power[m - 1]) * base + S[i + m]) % mod
        if res in dic.keys():
            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:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():


    class SuffixArray:
        """
        construct:
            suffix array: O(N(logN)^2)
            lcp array: O(N)
            sparse table: O(NlogN)
        query:
            get_lcp: O(1)
        """

        def __init__(self, s):
            """
            s: str
            """
            self.__s = s
            self.__n = len(s)
            self.__suffix_array()
            self.__lcp_array()
            self.__sparse_table()

        # suffix array
        def __suffix_array(self):
            s = self.__s
            n = self.__n
            # initialize
            sa = list(range(n))
            rank = [ord(s[i]) for i in range(n)]
            tmp = [0]*n
            k = 1
            def cmp_key(i): return (rank[i], rank[i+k] if i+k < n else -1)
            # iterate
            while(k <= n):
                sa.sort(key=cmp_key)
                tmp[sa[0]] = 0
                for i in range(1, n):
                    tmp[sa[i]] = tmp[sa[i-1]]+(cmp_key(sa[i-1]) < cmp_key(sa[i]))
                rank = tmp[:]
                k <<= 1
            self.__sa = sa
            self.__rank = rank

        # LCP array
        def __lcp_array(self):
            n = self.__n
            s = self.__s
            sa = self.__sa
            rank = self.__rank
            lcp = [0]*n
            h = 0
            for i in range(n):
                j = sa[rank[i]-1]
                if h > 0:
                    h -= 1
                while j+h < n and i+h < n and s[j+h] == s[i+h]:
                    h += 1
                lcp[rank[i]] = h
            self.__lcp = lcp

        # sparse table (LCPのminをとるindexを持つ)
        def __sparse_table(self):
            n = self.__n
            logn = max(0, (n-1).bit_length())
            table = [[0]*n for _ in range(logn)]
            table[0] = list(range(n))
            # construct
            for i in range(1, logn):
                for k in range(n):
                    if k+(1 << (i-1)) >= n:
                        table[i][k] = table[i-1][k]
                        continue
                    if self.__lcp[table[i-1][k]] <= self.__lcp[table[i-1][k+(1 << (i-1))]]:
                        table[i][k] = table[i-1][k]
                    else:
                        table[i][k] = table[i-1][k+(1 << (i-1))]
            self.__table = table

        def get_lcp(self, a, b):
            """
            a,b: int 0<=a,b<n
            return LCP length between s[a:] and s[b:]
            """
            if a == b:
                return self.__n-a
            l, r = self.__rank[a], self.__rank[b]
            l, r = min(l, r)+1, max(l, r)+1
            if r-l == 1:
                return self.__lcp[l]
            i = (r-l-1).bit_length()-1
            if self.__lcp[self.__table[i][l]] <= self.__lcp[self.__table[i][r-(1 << i)]]:
                return self.__lcp[self.__table[i][l]]
            else:
                return self.__lcp[self.__table[i][r-(1 << i)]]
    n = int(input())
    s = input()
    sa = SuffixArray(s)
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            ans = max(ans, min(sa.get_lcp(i, j), j-i))
    print(ans)



resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#dp-%E5%AE%9F%E8%A3%85%E3%81%AE%E9%A0%86%E5%BA%8F
    
    
    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく
    
    N = int(input())
    S=input()
    # dpテーブル dp[i][j]:= ...
    dp = [[0]*N for _ in range(N)]
    
    # 初期条件
    dp[0][0] = 0
    for i in range(N-1):
        if S[i]==S[N-1]:
            dp[N-1][i]=1


    # ループ
    for i in reversed(range(N-1)):
        for j in reversed(range(N-1)):
            if i>j:
                if S[i]!=S[j]:
                    dp[i][j]=0
                else:
                    dp[i][j]=min(i-j,dp[i+1][j+1]+1)
    
    ans=0
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if i>j:
                ans=max(ans,dp[i][j])
    print(ans)

    
    
resolve()

Submission status: Accepted

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

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j
        
        if j == 0:
            i += 1
            continue
            
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
            
        i += k
        j -= k
        
    return res

ans = 0
for i in range(N):
    lcp = z_algorithm(S[i:])
    tmp = max(min(lcp[j], j) for j in range(N - i))
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

ans=0

for slide in range(1,N):
    pos=slide
    bpos=0
    while pos<N:
        clen=0
        while pos<N and clen<slide and S[pos]==S[bpos]:
            pos+=1
            bpos+=1
            clen+=1
        
        ans=max(ans,clen)

        if clen==0:
            pos+=1
            bpos+=1

print(ans)

Submission status: Accepted

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

MOD = 2 ** 61 - 1
root = 10000

rhs = [0]
for h in map(ord, S):
    rhs.append((root * rhs[-1] + h) % MOD)

pws = [1]
for i in range(N):
    pws.append(pws[-1] * root % MOD)

ok = 0
ng = N
while ng - ok > 1:
    mid = (ok + ng) // 2
    hashes = dict()
    flg = False
    for i in range(N - mid + 1):
        hashofsub = (rhs[i+mid] - rhs[i] * pws[mid]) % MOD
        if hashofsub in hashes:
            if i >= hashes[hashofsub] + mid:
                flg = True
                break
        else:
            hashes[hashofsub] = i
    
    if flg:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,heapq
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################

def solve():
    n = inp()
    s = insr()
    q = [[0 for x in range(n + 1)] for y in range(n + 1)] 
    w = 0
    qw = ""
    qq = 0
    for i in range(1,n + 1): 
        for j in range(i + 1,n + 1):
            if s[i - 1] == s[j - 1] and q[i - 1][j - 1] < j - i: 
                q[i][j] = q[i - 1][j - 1] + 1
                if q[i][j] > w: 
                    w = q[i][j] 
                    index = max(i,qq)
            else: 
                q[i][j] = 0
    if w > 0: 
        for i in range(qq - w + 1,qq + 1): 
            qw = qw + s[i - 1] 
    print(len(qw))
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1],1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)

def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))

def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


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

n = readint()
s = readstr()

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ABC141-E Who Says a Pun?
"""
ロリハ解
探索する文字列の長さを二分探索し、重複を探す。
計算量はO((n+m)*log(n//2)) ※mは探索する文字列の長さ
log部分は100には間違いなく収まるので、O(10^5)程度。十分に間に合う。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
s = readline().rstrip().decode('utf-8')

class RollingHash(): #衝突を防ぐため、res1とres2の基数の異なるハッシュによって判定する。
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)


def func(mid): #ここが関数部分
    dic1 = dict()

    for i in range(n-mid+1):
        res = roliha.get(i,i+mid)
        if res in dic1:
            #部分重複があってはならない。(2つの文字列は独立)
            if i-dic1[res] >= mid: #先頭文字がmidの幅以上あるならば
                return True
            else:
                continue #更新処理を飛ばさないといけない
        dic1[res] = i
    return False 


def binary_search(): #2分探索
    ok = 0
    ng = n//2+1
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if func(mid):
            ok = mid
        else:
            ng = mid

    return ok

roliha = RollingHash(s)

print(binary_search())

Submission status: Accepted

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

long=0
for i in range(N-1):
  for j in range(i+long+1,N):
    if not (S[i:j] in S[j:]):
      break
  long=max(long,j-i-1)
print(long)

Submission status: Accepted

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

tmp = 0
for i in range(n-1):
	for j in range(i+tmp+1, n):
		if not s[i:j] in s[j:]:
			break
	tmp = max(tmp, j-i-1)

"""
二重ループ型だが実際はO(ans N)でうごく.
"""

print(tmp)

Submission status: Accepted

Solution code:
def z_algorithm(s):
    res = [0 for _ in range(len(s))]
    res[0] = len(s)
    i, j = 1, 0
    while i < len(s):
        while i + j < len(s) and s[j] == s[i + j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k < j and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res

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

res = 0

for i in range(N):
    z = z_algorithm(S[i:])
    for j in range(N - i):
        res = max(res, min(j, z[j]))

print(res)

Submission status: Accepted

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

res = 0

for i in range(N - 1):
    for j in range(i + res, N):
        if S[i:j] not in S[j:]:
            break
    res = max(res, j - i - 1)

print(res)

Submission status: Accepted

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

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

for j in range(N):
    if S[j] == S[-1]:
        dp[-1][j] = 1

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

ans = 0
for i in range(N):
    for j in range(N):
        ans = max(ans, min(dp[i][j], abs(i - j)))

print(ans)