Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class RollingHash(object):
    def __init__(self, source: str, base=1000000007, mod=9007199254740997):
        self.source = source
        self.base = base
        self.mod = mod
        self.hash_from_zero_to = self._get_hash_from_zero_to()
        self.base_pow = self._get_base_pow()

    # 文字列sourceの区間 [0, right) のハッシュ値を前計算する
    def _get_hash_from_zero_to(self):
        hash_from_zero_to = [0]
        for si in self.source:
            hash_from_zero_to.append((hash_from_zero_to[-1] * self.base + ord(si)) % self.mod)

        return hash_from_zero_to

    # base値をi回掛けてmodをとった値を前計算する
    def _get_base_pow(self):
        base_pow = [1]
        for i in range(len(self.source)):
            base_pow.append(base_pow[-1] * self.base % self.mod)

        return base_pow

    # 文字列sourceの区間 [left, right) のハッシュを取得する
    def get_hash(self, left: int, right: int):
        return (self.hash_from_zero_to[right]
                - self.hash_from_zero_to[left] * self.base_pow[right - left]) % self.mod


# 題意を満たす文字列の最大長を二分探索する
def binsearch(func, rh: RollingHash, ok: int, ng: int):
    source_length = len(rh.source)
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if func(rh, mid, source_length):
            ok = mid
        else:
            ng = mid

    return ok


# 題意を満たす長さtarget_lengthの文字列があるか判定する
def judge(rh: RollingHash, target_length: int, source_length: int):
    memo = {}
    for start_idx in range(source_length - target_length + 1):
        cur_hash = rh.get_hash(start_idx, start_idx + target_length)
        if cur_hash in memo:
            if start_idx - memo[cur_hash] >= target_length:
                return True
        else:
            memo[cur_hash] = start_idx

    return False


n = ni()
s = ns()

rh = RollingHash(s)
print(binsearch(judge, rh, 0, n//2 + 2))

Submission status: Accepted

Solution code:
n1 = int(input())
s1 = input()

r1 = 0
r2 = 0
for i1 in range (n1):
    if n1 - (r1 * 2) - i1 < 0:
        break
    for i2 in range(n1 - r1):
        t2 = r1 + i2 + 1
        if s1[i1:i1 + t2] in s1[i1 + t2:] and s1[i1:i1 + t2] != "":
            continue
        else:
            r1 = max(r1, r1 + i2)
            break


print(r1)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class RollingHash(object):
    def __init__(self, source: str, base=10**9+7, mod=(1<<64)-1):
        self.source = source
        self.base = base
        self.mod = mod
        self.hash_from_zero_to = self._get_hash_from_zero_to()
        self.base_pow = self._get_base_pow()

    # 文字列sourceの区間 [0, right) のハッシュ値を前計算する
    def _get_hash_from_zero_to(self):
        hash_from_zero_to = [0]
        for si in self.source:
            hash_from_zero_to.append((hash_from_zero_to[-1] * self.base + ord(si)) % self.mod)

        return hash_from_zero_to

    # base値をi回掛けてmodをとった値を前計算する
    def _get_base_pow(self):
        base_pow = [1]
        for i in range(len(self.source)):
            base_pow.append(base_pow[-1] * self.base % self.mod)

        return base_pow

    # 文字列sourceの区間 [left, right) のハッシュを取得する
    def get_hash(self, left: int, right: int):
        return (self.hash_from_zero_to[right]
                - self.hash_from_zero_to[left] * self.base_pow[right - left]) % self.mod


def binsearch(func, rh: RollingHash, ok: int, ng: int):
    source_length = len(rh.source)
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if func(rh, mid, source_length):
            ok = mid
        else:
            ng = mid

    return ok


# 題意を満たす長さtarget_lengthの文字列があるか判定
def judge(rh: RollingHash, target_length: int, source_length: int):
    memo = {}
    for start_idx in range(source_length - target_length + 1):
        cur_hash = rh.get_hash(start_idx, start_idx + target_length)
        if cur_hash in memo:
            if start_idx - memo[cur_hash] >= target_length:
                return True
        else:
            memo[cur_hash] = start_idx

    return False


n = ni()
s = ns()

rh = RollingHash(s)
print(binsearch(judge, rh, 0, n//2 + 2))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

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


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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input())
    s = input()[::-1]
    ans = 0
    l = 0
    r = 1
    for r in range(1,n):
        if s[l:r] in s[r:]:
            ans=r-l
        else:
            l += 1
    print(ans)

main()

Submission status: Accepted

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

dp = [[0 for i in range(5005)] for j in range(5005)]

for i in range(n - 1, -1, -1):
    for j in range(n - 1, -1, -1):
        dp[i][j] = 0 if s[i] != s[j] else dp[i + 1][j + 1] + 1

res = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        curr = min(dp[i][j], j - i)
        res = max(res, curr)

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
_max = 0
memo_ls = [[0 for i in range(n)] for j in range(n)]
memo_dict = {i : [0 for j in range(n)] for i in range(-1,n)}
for i in range(n):
    for j in range(min(i+1,n-1), n):
        if s[i] != s[j]:
            continue
        candidate = memo_dict[i-1][j-1] + 1
        if candidate > j - i:
            candidate = j - i
        memo_dict[i][j] = candidate
        if candidate > _max:
            _max = candidate
print(_max)

Submission status: Accepted

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

a=0
i=0
j=1
 
while j<n:
    if s[i:j] in s[j:]:
        a = max(a,len(s[i:j]))
        j+=1
    else:
        i+=1
        j+=1 
print(a)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
dp = [[0] * (N + 1) for _ in range(N + 1)]
res = 0

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

print(res)

Submission status: Accepted

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

res = 0
dp = [[0]*(n+1) for _ in range(n+1)]
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
        cres = min(j-i, dp[i][j])
        res = max(res, cres)

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
S = input()
mod1 = 10 ** 9 + 7
mod2 = 10 ** 9 + 9
base1 = 1007
base2 = 2009

ok = 0
ng = N // 2 + 1
mid = (ok + ng) // 2
while ng - ok > 1:
    seen1 = defaultdict(lambda: 10 ** 5)
    seen2 = defaultdict(lambda: 10 ** 5)
    rh1 = 0
    rh2 = 0
    for i in range(mid):
        rh1 += ord(S[i]) * pow(base1, mid - i - 1, mod1)
        rh2 += ord(S[i]) * pow(base2, mid - i - 1, mod2)
        rh1 %= mod1
        rh2 %= mod2
    seen1[rh1] = 0
    seen2[rh2] = 0
    flag = 0
    for i in range(1, N - mid + 1):
        if flag == 1:
            break
        rh1 = (rh1 * base1 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base1, mid, mod1)) % mod1
        rh2 = (rh2 * base2 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base2, mid, mod2)) % mod2
        if i - seen1[rh1] >= mid and i - seen2[rh2] >= mid:
            ok = mid
            mid = (ok + ng) // 2
            flag = 1
        else:
            if seen1[rh1] == 10 ** 5:
                seen1[rh1] = i
            if seen2[rh2] == 10 ** 5:
                seen2[rh2] = i
    if flag == 0:
        ng = mid
        mid = (ok + ng) // 2

print(ok)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input())
    s = input()[::-1]
    ans = 0
    l = 0
    r = 1
    while l < n:
        if s[l:r] in s[r:]:
            r += 1
            if r == n + 1: break
        else:
            l += 1
            ans = max(ans, r - l)
    ans = max(ans, r - l - 1)
    print(ans)

main()

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N = int(input())
S = input()
character_pos = [ set() for _ in range(26) ]
ans = 0
continue_list = dict()
for i in range(N):
    s = S[i]
    new_continue_list = dict()
    cpos = character_pos[ord(s)-ord('a')]
    for p in cpos:
        new_continue_list[p] = 1
    cpos.add(i)
    for k, v in continue_list.items():
        if s == S[k+1]  and v + 1 <= i - k - 1:
            new_continue_list[k+1] = v+1
        elif v > ans:
            ans = v
    continue_list = new_continue_list

if len(continue_list.values()) > 0:
    ans = max(ans, max(continue_list.values()))
print(ans)

Submission status: Accepted

Solution code:
def Z_algo(s):
    n=len(s)
    a=[0]*n
    a[0]=n
    i,j=1,0
    while i<n:
        while i+j<n and s[j]==s[i+j]:
            j+=1
        a[i]=j
        if j==0:
            i+=1
            continue
        k=1
        while i+k<n and k+a[k]<j:
            a[i+k]=a[k]
            k+=1
        i+=k
        j-=k
    return a

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

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
dp = [[0] * (N + 1) for _ in range(N + 1)]
res = 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
        res = max(res, min(j - i, dp[i][j]))

print(res)

Submission status: Accepted

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

i = j = 0
ans = 0
while j < N-1:
    if S[i:j] in S[j:]:
        ans = max(ans, j-i)
        j += 1
    else:
        i += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
j = 1
ans = 0
for i in range(N):
  s = S[i:i + j]
  while S[i + j:].find(s) != -1:
    j += 1
    s = S[i:i + j]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
DP = [[0]*5005 for _ in range(5005)]

for i in range(N):
    for j in range(N):
        if S[i] == S[j]:
            DP[N-i][N-j] = DP[N-i+1][N-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)

Submission status: Accepted

Solution code:
# ABC141E - Who Says a Pun?
def main():
    N = int(input())
    S = input().rstrip()
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, checked = 0, set()
        for i in range(N - 2 * mid + 1):
            checked.add(S[i : i + mid])
            if S[i + mid : i + 2 * mid] in checked:
                flg = 1
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC141E - Who Says a Pun?
def main():
    N = int(input())
    S = input().rstrip()
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, checked = 0, set()
        for i in range(N - 2 * mid + 1):
            checked.add(hash(S[i : i + mid]))
            if hash(S[i + mid : i + 2 * mid]) in checked:
                flg = 1
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

def calc(m):
    A = {}
    for i in range(N-m+1):
        a = S[i:i+m]
        if a in A:
            # aが2回目以降に出現したindex
            j = A[a]
            # iとjがm以上離れているかどうか
            if i-j >= m:
                return True
        else:
            # aが最初に出現したindex
            A[a] = i
    return False

print(bisearch_max(0, N, calc))

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

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        # 各文字を数値に変換しておく
        S = [ord(s)-97 for s in S]

        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        # ハッシュの生成
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    # 区間[i,j)のハッシュ値を取得
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    A = {}
    for i in range(N-m+1):
        a_hash = rh.get(i, i+m)
        if a_hash in A:
            # a_hashが2回目以降に出現したindex
            j = A[a_hash]
            # iとjがm以上離れているかどうか
            if i-j >= m:
                return True
        else:
            # a_hashが最初に出現したindex
            A[a_hash] = i
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))

Submission status: Accepted

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

main()

Submission status: Accepted

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

yes = 0
no = n // 2 + 1
while abs(yes - no) > 1:
	center = (yes + no) // 2
	d = set()
	for i in range(n - 2 * center + 1):
		d.add(s[i:i+center])
		if (s[i+center:i+2*center] in d):
			yes = center
			#print(tempS)
			break
	if (yes != center):
		no = center
print(yes)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
def check(m):
    Se = set()
    for i in range(n-2*m+1):
        Se.add(S[i:i+m])
        if S[i+m:i+2*m] in Se:
            return True
    return False

while l<=r:
    m = (l + r) // 2
 #   print("m = ", m)
    if check(m):
        fl = True
        l = m+1
        ans = l-1
 #       print(l-1,"にて共通部分有")
    else:
        r = m-1
 #       print(r+1,"にて共通部分無")
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
def check(m):
    Se = set()
    for i in range(n-2*m+1):
        Se.add(S[i:i+m])
        if S[i+m:i+2*m] in Se:
            return True
    return False

while l<=r:
    m = (l + r) // 2
 #   print("m = ", m)
    if check(m):
        fl = True
        l = m+1
        ans = l-1
 #       print(l-1,"にて共通部分有")
    else:
        r = m-1
 #       print(r+1,"にて共通部分無")
print(ans)

Submission status: Accepted

Solution code:
def calc(N, S):
    ll = 1
    lr = N // 2 + 1
    l = (ll + lr) // 2
    while True:
        d = {}
        for i in range(0, N - l + 1):
            s = S[i: i + l]
            if s in d:
                d[s] += [i]
            else:
                d[s] = [i]
        f = True
        for s in d:
            if len(d[s]) > 1 and [e for e in d[s][1:] if e > d[s][0] + l - 1]:
                ll = l
                f = False
                break
        if f:
            if l == 1:
                return 0
            lr = l
            if ll == lr:
                return ll
        else:
            if ll == lr - 1:
                return ll
        l = (ll + lr) // 2
    return 0


N = int(input())
S = input()
print(calc(N, S))

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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

ans = 0
i = j= 0

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

Submission status: Accepted

Solution code:
import sys

def main():

	input = sys.stdin.readline
	N = int(input().strip())
	S = list(input().strip())

	maxlen = 0

	for i in range(N):
		SS = S[i:N]
		Z = [0]*len(SS)
		Z[0] = len(SS)
		ZA = [0]*len(SS)
		ZA[0] = min(0,Z[0])
		rt = 0
		lt = 0

		for k in range(1,len(SS)):
			if k>rt:
				n = 0
				while n+k<len(SS) and SS[n]==SS[n+k]:
					n += 1
				Z[k] = n
				ZA[k] = min(k,Z[k])
				if n>0:
					lt = k
					rt = k+n-1
			else:
				p = k-lt
				rlen = rt-k+1

				if Z[p]<rlen:
					Z[k] = Z[p]
					ZA[k] = min(k,Z[k])
				else:
					i = rt+1
					while i<len(SS) and SS[i]==SS[i-k]:
						i += 1
					Z[k] = i-k
					ZA[k] = min(k,Z[k])
					lt = k
					rt = i-1
		
		maxlen = max(maxlen,max(ZA))

	print(maxlen)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
len_s = 1
for i in range(N):
    tmp_s = S[i:i+len_s]
    while tmp_s in S[i+len_s:]:
        len_s += 1
        tmp_s = S[i:i+len_s]
        ans += 1
print(ans)

Submission status: Accepted

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

dp = [0]*N
j = 1

for i in range(N):
    while S[i:j] in S[j:N]:
        dp[i] = j-i
        j += 1
print(max(dp))

Submission status: Accepted

Solution code:

def main():
    N = int(input())
    S = input()
    ans = 0

    """
    他言語ならこれで行けるはずだが、pythonだとTLE
    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)
    """
    i = j = 0

    while  j <= N-1:
        # 頭から見ていき、部分文字列が、その後ろのどこかにあれば範囲を広げる。かぶってはいけないのでj-iが最大
        if S[i:j] in S[j:]:
            ans = max(ans, j-i)
            j += 1
        else:
            i += 1
        

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

def isOk(leng):
    strList = set()
    que = deque([])
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        if sub in strList:
            return True
        que.append(sub)
        if len(que) >= leng:
            strList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
from collections import deque

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

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
 
 
r = 1
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:
n = int(input())
s = input()
 
m = [[0] * n for _ in range(n)]
lcs = 0
 
for j in range(1, n):
    if s[j] == s[0]:
        m[0][j] = 1
        lcs = 1
 
for i in range(1, n-1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            m[i][j] = min(m[i-1][j-1] + 1, j - i)
            lcs = max(m[i][j], lcs)
        else:
            m[i][j] = 0
 
print(lcs)

Submission status: Accepted

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

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

# 最長共通接頭辞問題(Z-Algorithm)
# 文字列SとS[i:]の最長共通接頭辞を各iについて求める
# 参考：https://codeforces.com/blog/entry/3107
# 図がわかりやすい:https://snuke.hatenablog.com/entry/2014/12/03/214243


def Z_Algorithm(S):
    N = len(S)
    R = 0 # Rはi文字目まで読んだ時、接頭辞の右端のうち一番右側にくるようなもの
    L = 0 # Lはその範囲の左端
    Z = [0 for _ in range(N)] # 答えとなる最長接頭辞の長さ
    Z[0] = N

    for i in range(1, N):
        if i > R:
            # iが前のRより右側ならS[i:]とSのみで考える
            L = i
            R = i
            while (R < N and S[R-L] == S[R]):
                R += 1
            Z[i] = R - L
            R -= 1
        else:
            k = i - L
            if Z[k] < R - i + 1:
                # はみ出さないなら前のがそのまま使える。R,Lはそのまま
                Z[i] = Z[k]
            else:
                # はみ出したら伸ばしてく
                L = i
                while (R < N and S[R-L] == S[R]):
                    R += 1
                Z[i] = R - L
                R -= 1
    return Z


def main():
    ans = 0
    for i in range(N):
        Z = Z_Algorithm(S[i:])
        for j, z in enumerate(Z):
            ans = max(ans, min(z, j))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(str, input()))

dp = [[0 for _ in range(N)] for _ in range(N)]
edge_r = N - 1
edge_d = N - 1
for i in reversed(range(N)):
	for j in reversed(range(N)):
		if i == edge_d or j == edge_r:
			if S[i] == S[j]:
				dp[i][j] = 1
			else:
				dp[i][j] = 0
		else:
			if S[i] == S[j]:
				dp[i][j] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
	for j in range(N):
		if i >= j:
			continue
		# ij間の距離よりもdp[i][j]が大きいならば、それはかぶってる
		tmp = min(dp[i][j], j - i)
		ans = max(tmp, ans)
		
print(ans)

Submission status: Accepted

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

dp = [[0 for _ in range(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):
    if i >= j:
      continue
    now = min(dp[i][j], j - i)
    ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[49]:


#import numpy as np
N = int(input())
S = input()
"""
5
ababa
2

13
strangeorange
5
"""


# In[54]:


i = 0
j = 1
max_cont = 0

while j < N:
    if S[i:j] in S[j:]:
        max_cont = max(max_cont, len(S[i:j]))
        j += 1
    else:
        i += 1
    if i == j:
        i += 1
        j += 2


# In[55]:


print(max_cont)


# In[ ]:

Submission status: Accepted

Solution code:
n = int(input())
s = input()
i = 0
j = 0
r = 0
while i < n:
    if s[i:j] in s[j:]:
        r = max(r, j - i)
        j += 1
    else:
        i += 1
print(r)

Submission status: Accepted

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

    l, r, ans = 0, 0, 0

    while r < N:
        if S[l:r] in S[r:N]:
            ans = max(ans, r - l)
            r += 1
        else:
            l += 1

    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
D = [[0] * n for i in range(n)]
 
for i in range(n):
    D[0][i] = int(s[0]==s[i])
    D[i][0] = int(s[0]==s[i])
D[0][0] = 0

for i in range(1,n):
    for j in range(i+1,n):
        mae = D[i-1][j-1]
        if s[i] == s[j]:
            if j-i <= mae:
                D[i][j] = mae
            else:
                D[i][j] = mae + 1

print(max([max(D[i]) for i in range(n)]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    def Z(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        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
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    # input
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) # k=n-i
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve(n, s):
    l, r = 0, n // 2 + 1
    while l < r:
        m = (l + r + 1) // 2
        if search(m, s):
            l = m
        else:
            r = m - 1
    return l


def search(w, s):
    w2 = w * 2
    appeared = [hash(s[i - w:i]) for i in range(w, w2)]
    comparing = set()

    for i in range(w2, n + 1):
        t = hash(s[i - w:i])
        comparing.add(appeared[i - w2])
        if t in comparing:
            return True
        appeared.append(t)

    return False


n = int(input())
s = input()
print(solve(n, s))

Submission status: Accepted

Solution code:
def solve(n, s):
    l, r = 0, n // 2 + 1
    while l < r:
        m = (l + r + 1) // 2
        if search(m, s):
            l = m
        else:
            r = m - 1
    return l


def search(w, s):
    appeared = []
    comparing = set()
    w2 = w * 2

    for i in range(w, n + 1):
        t = hash(s[i - w:i])
        if i >= w2:
            comparing.add(appeared[i - w2])
            if t in comparing:
                return True
        appeared.append(t)

    return False


n = int(input())
s = input()
print(solve(n, s))