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:
# Z-Algorithm
#############################################################
def z_algo(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n and k + z[k] < j:
            z[i + k] = z[k]
            k += 1
        i += k
        j -= k
    return z
#############################################################

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

ans = 0
for i in range(N):
    z = z_algo(S[i:])
    # j = 0,1,...,N-i-1
    # zのindexは0,1,...,N-i-1
    for j in range(N - i):
        # z[j]>jの時、部分文字列が重なってしまう
        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()

    dp = [0] * (N + 1)
    ans = 0

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

    print(ans)
    return


if __name__ == '__main__':
    main()

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()

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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

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()

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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

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()

    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):
            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 + 1, N):
            if ans < min(dp[i][j], j - i):
                ans = min(dp[i][j], j - i)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ord を hash にすると、ハックされにくくなるが、1/MODくらいの確率で0を引く。
class RollingHash:

    __slots__ = ["root", "mod", "hs", "pw"]

    def __init__(self, string, root, mod):
        self.root = root
        self.mod = mod
        self.hs = [0] * (len(string) + 1)
        self.pw = [1] * (len(string) + 1)
        for i in range(len(string)):
            self.hs[i + 1] = (self.hs[i] * self.root + ord(string[i])) % self.mod
            self.pw[i + 1] = self.pw[i] * self.root % self.mod

    def get_hash(self, l, r):
        "get the hash of s[l:r] (0 <= l <= r <= len(s))"
        return (self.hs[r] - self.hs[l] * self.pw[r - l]) % self.mod

    def __getitem__(self, index):
        "RH[l:r] is equivalent to RH.get_hash(l, r)"
        if isinstance(index, slice):
            return self.get_hash(index.start, index.stop)
        else:
            return 0


# 正直、RollingHashと速度はあまり変わらない。なんで？
RHMOD = (1 << 61) - 1
class RollingHashMOD61:
    """
    MOD == 2 ** 61 - 1
    参考: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
    """

    __slots__ = ["root", "hs", "pw"]

    def __init__(self, string, root):
        self.root = root
        self.hs = [0] * (len(string) + 1)
        self.pw = [1] * (len(string) + 1)
        for i in range(len(string)):
            tmp = self.hs[i] * self.root + ord(string[i])
            self.hs[i + 1] = (tmp >> 61) + (tmp & RHMOD)
            tmp = self.pw[i] * self.root
            self.pw[i + 1] = (tmp >> 61) + (tmp & RHMOD)

    def get_hash(self, l, r):
        "get the hash of s[l:r] (0 <= l <= r <= len(s))"
        return (self.hs[r] - self.hs[l] * self.pw[r - l]) % RHMOD

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.get_hash(index.start, index.stop)
        else:
            return 0
        
def whosaysapun():
    import random 
    N = int(input())
    S = input()

    MOD = 2 ** 61 - 1
    root = random.randint(1000, 2000)

    rh = RollingHashMOD61(S, root)

    ok = 0
    ng = N
    while ng - ok > 1:
        mid = (ok + ng) // 2
        hashes = dict()
        flg = False
        for i in range(N - mid + 1):
            hashofsub = rh[i:i+mid]
            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)

# mods = [
#     6435805146278881223, 
#     7427449777901196481, 
#     1638624619723308673, 
#     2288514702228148349,
#     3583235820855855041
# ]

    

if __name__ == "__main__":
    whosaysapun()

Submission status: Accepted

Solution code:
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = list(getS())
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

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

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  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[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  #for i in dp:
  #  print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def z_algo(s):
    """Z-algorithm O(|S|)

    Args:
        s (str): 対象文字列
    
    Returns:
        list: lcp配列 (z[i]: sとs[i:]の最長共通接尾辞の長さ)
    """
    n = len(s)
    z = [0] * n
    z[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        z[i] = j

        if j == 0:
            i += 1
            continue

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

        i += k
        j -= k

    return z


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

res = 0
for i in range(n-1):
    z = z_algo(s[i:])
    for j in range(n-i):
        if z[j] <= j and res < z[j]:
            res = z[j]

print(res)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
dp = [0 for i in range(n + 1)]
for i in range(n):
    if s[i - dp[i]:i + 1] in s[:i - dp[i]]:
        dp[i + 1] = dp[i] + 1
    else:
        dp[i + 1] = dp[i]
print(dp[n])

Submission status: Accepted

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


def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table


def hoge_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret = 0
    while i < len(string):
        if (string[i] == pattern[j]) and (i-j >= j):
            i += 1
            j += 1
            if i-j >= j-1:
                ret = max(j, ret)
        elif j == 0:
            i += 1
        else:
            j = table[j]  # ここのループがダメな時がある?
    return ret

def z_algorithm(S):
    N = len(S)
    Z_arr = [0] * N
    Z_arr[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        Z_arr[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_arr[k] < j:
            Z_arr[i+k] = Z_arr[k]
            k += 1
        i += k
        j -= k
    return Z_arr

ans = 0
for i in range(N):
    res = z_algorithm(S[i:])
    for j, z in enumerate(res):
        if j  >= z:
            ans = max(ans, z)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class DoubleRollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base, self.mod = 1007, pow(2, 61) - 1
        self.f = f # set numerizing function
        self.hash, self.power = [0]*(self.n+1), [1]*(self.n+1)
        for i, e in enumerate(seq):
            self.hash[i+1] = (self.hash[i] * self.base + self.f(e)) % self.mod
            self.power[i+1] = (self.power[i] * self.base) % self.mod

    # get hash value of seq[left:right]
    def get(self, l, r): return (self.hash[r] - self.hash[l] * self.power[r-l]) % self.mod

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(lambda: -1)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v] != -1:
                if i >= d[v] + m:
                    return True
            else:
                d[v] = i
        return False

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

    print(left)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class ZAlgo:
    def __init__(self, seq):
        self.n = len(seq)
        # seq 自身と seq[i:] とが、先頭から最大で何文字一致しているか
        self.lcp = [0] * self.n
        self.lcp[0] = self.n
        i, j = 1, 0
        while i < self.n:
            while i + j < self.n and seq[j] == seq[i+j]:
                j += 1
            self.lcp[i] = j
            if j == 0:
                i += 1
                continue

            k = 1
            while i + k < self.n and k + self.lcp[k] < j:
                self.lcp[i + k] = self.lcp[k]
                k += 1
            i += k
            j -= k

    # seq[0:]とseq[i:]のLCP
    def getLCP(self, i): return self.lcp[i]

def main():
    N = I()
    S = SL()

    ans = 0

    for i in range(N):
        z = ZAlgo(S[i:])
        for j in range(N-i):
            ans = max(ans, min(z.getLCP(j), j))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class DoubleRollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base, self.mod = 1007, MOD
        self.f = f # set numerizing function
        self.hash, self.power = [0]*(self.n+1), [1]*(self.n+1)
        for i, e in enumerate(seq):
            self.hash[i+1] = (self.hash[i] * self.base + self.f(e)) % self.mod
            self.power[i+1] = (self.power[i] * self.base) % self.mod

    # get hash value of seq[left:right]
    def get(self, l, r): return (self.hash[r] - self.hash[l] * self.power[r-l]) % self.mod

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(lambda: -1)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v] != -1:
                if i >= d[v] + m:
                    return True
            else:
                d[v] = i
        return False

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

    print(left)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(lambda: -1)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v] != -1:
                if i >= d[v] + m:
                    return True
            else:
                d[v] = i
        return False

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

    print(left)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def Z_alg(S):
    
    length = len(S)
    Z = [0] * (length + 1)
    Z[0] = length
    i, j = 1, 0
    ret = 0

    while i < length:
        while i + j < length and S[j] == S[i + j]:  j += 1
        Z[i] = j
        if i - Z[i] >= 0:  ret = max(ret, Z[i])
        if(j == 0):
            i += 1
            continue
        k = 1
        while k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
            if (i + k) - Z[i + k] >= 0:  ret = max(ret, Z[i + k])
        i += k
        j -= k
        
    return ret

N = int(input())
S = input()
ans = 0
s = deque(S)
while s:
    ans = max(ans, Z_alg(s))
    s.popleft()  
print(ans)

Submission status: Accepted

Solution code:
"""
X文字が条件にあてはまるとき、X-1文字も条件に当てはまる。したがって、二分探索を使うのがよい。
一回の探索に、O(N**2)かかる。
探索はO(logN)回行うため、全体でO(N**2logN)で、ギリ間に合う。
"""
N = int(input())
S = input()

def is_ok(X):
    dic = {}
    for i in range(N+1-X):
        sub = S[i:i+X]
        if sub not in dic:
            dic[sub] = (i,i+X-1)
        else:
            if dic[sub][1] < i:
                return True
    return False

def bisearch(high,low):
    while high - low > 1:
        mid = (high+low)//2
        if is_ok(mid):
            low = mid
        else:
            high = mid
    return low
print(bisearch(N,0))

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

def alpha2num(alpha):
    num = 0
    for index, item in enumerate(list(alpha)):  num += pow(26, len(alpha) - index - 1) * (ord(item) - ord('a') + 1)
    return num

def rol_hash(l):

    b, h = 1007, 10 ** 9 + 9
    base = pow(b, l, h)
    hash_s = 0
    dic = {}
    for i in range(l):  hash_s = (hash_s * b + alpha2num(S[i])) % h
    dic[hash_s] = l - 1
    for i in range(1, N - l + 1):
        hash_s = (hash_s * b - base * alpha2num(S[i - 1]) + alpha2num(S[i + l - 1])) % h
        if hash_s in dic:
            if S[dic[hash_s] - l + 1:dic[hash_s] + 1] == S[i:i + l] and dic[hash_s] < i:  return 1
        else:  dic[hash_s] = i + l - 1
    return 0

def is_ok(mid):  return rol_hash(mid)

def binary_search(left, right):
    while (abs(right - left) > 1):
        mid = (left + right) // 2
        if is_ok(mid):  right = mid
        else:  left = mid
    return right

N = cin()[0]
S = input()

left = N + 1
right = -1
ret = binary_search(left, right)
if ret == right:  print(0)
else:  print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def Z_algorithm(s):
    n = len(s)
    Z = [0] * n  # z[i] = sum(s[0::n - i], s[i::n])
    Z[0] = n
    i, j = 1, 0
    while i < n:
        # 共通部分を見つけるパート
        while i + j < n and s[j] == s[i + j]:
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue
        # 計算の再利用パート
        # k + Z[k] < j なら再利用できる
        k = 1
        while k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        # k個先まで見たのでk個先にバトンを渡す
        i += k
        j -= k
    return Z


def solve(k):
    a = Z_algorithm(s[k:])
    ans = 0
    for i in range(n - k):
        ans = max(ans, min(i, a[i]))
    return ans


n, s = int(input()), input()
print(max(solve(i) for i in range(n)))

Submission status: Accepted

Solution code:

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

def resolve():
    N = int(input())
    S = input()

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    N = int(input())
    S = input()

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

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


if __name__ == "__main__":
    resolve()