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:


class RollingHash:

    PS1 = 1009
    PS2 = 1007
    PL1 = 100000007
    PL2 = 100000009

    def __init__(self, s: str):
        self._n = len(s) + 1
        self._pow1, self._pow2, self._hash1, self._hash2 = self._initialize(s, self._n)

    def _initialize(self, s: str, n: int):
        pow1 = [1 for _ in range(n)]
        pow2 = [1 for _ in range(n)]
        hash1 = [0 for _ in range(n)]
        hash2 = [0 for _ in range(n)]

        idx = 1
        for c in s:
            pow1[idx] = pow1[idx - 1] * self.PS1 % self.PL1
            pow2[idx] = pow2[idx - 1] * self.PS2 % self.PL2
            hash1[idx] = (hash1[idx - 1] * self.PS1 + ord(c) - ord('a') + 1) % self.PL1
            hash2[idx] = (hash2[idx - 1] * self.PS2 + ord(c) - ord('a') + 1) % self.PL2
            idx += 1

        return pow1, pow2, hash1, hash2

    def get(self, l: int, r: int):
        p1 = ((self._hash1[r] - self._hash1[l] * self._pow1[r - l]) % self.PL1 + self.PL1) % self.PL1
        p2 = ((self._hash2[r] - self._hash2[l] * self._pow2[r - l]) % self.PL2 + self.PL2) % self.PL2
        return p1, p2


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

rh = RollingHash(S)

MAGIC_NUMBER = 261

ans = 0
end = False
for l in range((N + 1) // 2, 1, -1):
    d = {}
    for idx in range(N - l + 1):
        p1, p2 = rh.get(idx, idx + l)
        lv, rv = d.get((p1, p2), (N, 0))
        lv = min(lv, idx)
        rv = max(rv, idx)
        d[(p1, p2)] = (lv, rv)

    for _, (lv, rv) in d.items():
        if rv - lv >= l:
            print(l)
            end = True
            break

    if end:
        break

if not end:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(str, input().strip()))
seed = 131
mod1 = 10 ** 9 + 7
mod2 = 10 ** 9 + 7
lsd = [1] * 6000
lsd2 = [1] * 6000
hs = [1] * 6000
hs2 = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
hs2[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod1
    lsd2[i] = lsd2[i - 1] * seed % mod2
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod1
    hs2[i] = (hs2[i - 1] * seed + ord(s[i]) - ord('a')) % mod2


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod1
        else:
            t = hs[i + x - 1]
        # print(i,t)
        if not g[t]:
            g[t] = i + 1
        elif g[t] + x - 1 <= i:
            return True
    return False


l = 0
r = n
while l < r - 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m - 1

if check(r):
    print(r)
else:
    print(l)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(str, input().strip()))
seed = 131
mod1 = 10 ** 9 + 9
mod2 = 10 ** 9 + 7
lsd = [1] * 6000
lsd2 = [1] * 6000
hs = [1] * 6000
hs2 = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
hs2[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod1
    lsd2[i] = lsd2[i - 1] * seed % mod2
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod1
    hs2[i] = (hs2[i - 1] * seed + ord(s[i]) - ord('a')) % mod2


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod1
        else:
            t = hs[i + x - 1]
        # print(i,t)
        if not g[t]:
            g[t] = i + 1
        elif g[t] + x - 1 <= i:
            return True
    return False


l = 0
r = n
while l < r - 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m - 1

if check(r):
    print(r)
else:
    print(l)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from itertools import *
INF = 10**10

CHRtoINT = defaultdict(int)
atoz = [chr(i) for i in range(97,97+26)]
for i, c in enumerate(atoz):
    CHRtoINT[c] = i

N, S = int(input()), input()
b = 26
m = 67280421310721
l, r = 0, N//2+1
while l+1 < r:
    x = (l+r)//2
    OK = 0
    dic = defaultdict(int)
    B, hash, b_inv = pow(b, x-1, m), 0, pow(b, m-2, m)
    t = B
    for c in S[:x]:
        hash = (hash + CHRtoINT[c] * t) % m
        t = t * b_inv % m
    dic[hash] = 0
    B *= b
    for i, c in enumerate(S[:-x]):
        hash = (hash * b - CHRtoINT[c] * B + CHRtoINT[S[i+x]]) % m
        if hash in dic:
            if i+1-dic[hash] >= x:
                OK = 1
                break
        else:
            dic[hash] = i+1
    if OK:
        l = x
    else:
        r = x
print(l)

Submission status: Accepted

Solution code:
from collections import deque

base = 10007
mod1 = int(1e9 + 7)
mod2 = int(1e9 + 9)


class RollingHash:
    def __init__(self, s):
        self.s = s
        self.len = len(s)
        self.mod1_table = [pow(base, i, mod1) for i in range(self.len + 2)]
        self.mod2_table = [pow(base, i, mod2) for i in range(self.len + 2)]
        self.inv1_table = [pow(self.mod1_table[i], mod1 - 2, mod1) for i in range(self.len + 2)]
        self.inv2_table = [pow(self.mod2_table[i], mod2 - 2, mod2) for i in range(self.len + 2)]
        self.elm_1 = [0]
        self.elm_2 = [0]
        for i in range(self.len):
            val_1 = self.elm_1[-1] + self.mod1_table[len(self.elm_1)] * ord(s[i])
            val_2 = self.elm_2[-1] + self.mod2_table[len(self.elm_2)] * ord(s[i])
            self.elm_1.append(val_1 % mod1)
            self.elm_2.append(val_2 % mod2)
    
    def get(self, l, r):
        val_1 = (self.elm_1[r] - self.elm_1[l]) * self.inv1_table[l] % mod1
        val_2 = (self.elm_2[r] - self.elm_2[l]) * self.inv2_table[l] % mod2
        return val_1, val_2


def check(s, val):
    que = deque()
    se = set()
    for i in range(s.len - val + 1):
        res = s.get(i, i + val)
        if res in se:
            return True
        que.append(res)
        if len(que) == val:
            se.add(que.popleft())
    
    return False


def main():
    n = int(input())
    s = input()
    rh = RollingHash(s)
    
    
    ok = 0
    ng = n
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(rh, mid):
            ok = mid
        else:
            ng = mid
    
    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())
s = input()
ans = 0
for i in range(n):
    data = z_alg(s[i:])
    for j,x in enumerate(data[1:]):
        ans = max(ans,min(x,j+1))

print(ans)

Submission status: Accepted

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

l1 = l2 = length = 0

while l2 + length < n:
    #print("s[l1:l2]" , s[l1:l2])
    #print("s[l2:]" , s[l2:])
    if s[l1:l2] in s[l2:]:
        length = l2 - l1
        l2 += 1 
    else:
        l1 += 1
        l2 = l1 + length + 1
print(length)

Submission status: Accepted

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

    for i in range(N):
        s1 = S[index:i+1]
        s2 = S[i+1:]
        if s1 in s2:
            ans = len(s1)
        else:
            index += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

r = 0
answer = 0

for l in range(N):
  while True:
    if S.rfind(S[l:r+1]) >= r+1:
      r += 1
      answer = max(answer, r-l)
    else:
      break
  
print(answer)

Submission status: Accepted

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

l1 = l2 = length = 0

while l2 + length < N:
    if S[l1:l2] in S[l2:]:
        length = l2 - l1
        l2 += 1
    else:
        l1 += 1
        l2 = l1 + length + 1
        
print(length)