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: Wrong Answer

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

lb=-1
rb=N+1
while rb-lb>1:
    mid=(lb+rb)//2
    f=0
    se=set()
    x=0
    for i,s in enumerate(S[:mid]):
        x+=pow(26,i)*(ord(s)-ord('a'))
    se.add(x)
    m=pow(26,mid-1)
    for i,s in enumerate(S[mid:]):
        x-=ord(S[i])
        x//=26
        x+=m*(ord(s)-ord('a'))
        if x in se:
            f=1
            break
        else:
            se.add(x)
    if f:
        lb=mid
    else:
        rb=mid
print(lb)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    from collections import defaultdict
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    P1 = 2**127-1
    P2 = 2**31-1
    base = 26
    N = II()
    S = list(map(ord,list(input())))
    pow1 = [1]*N
    pow2 = [1]*N
    for i in range(N-1):
        pow1[i+1] = pow1[i]*base%P1
        pow2[i+1] = pow2[i]*base%P2
    hash1 = [0]*(N+1)
    hash2 = [0]*(N+1)
    hash1[1] = hash2[1] = S[0]
    for i in range(2,N+1):
        hash1[i] = (hash1[i-1]*base + S[i-1]) % P1
        hash2[i] = (hash2[i-1]*base + S[i-1]) % P2
    
    def f(x):
        hashes = defaultdict(int)
        for i in range(N-x+1):
            #S[i:i+x]
            h1 = (hash1[i+x] - hash1[i] * pow1[x]) % P1
            h2 = (hash2[i+x] - hash2[i] * pow2[x]) % P2
            if hashes[(h1,h2)] == 0:
                hashes[(h1,h2)] = i
            elif hashes[(h1,h2)] + x <= i:
                return True
        # print(hashes)
        return False
    
    ok = 0
    ng = N//2+1
    while ng-ok > 1:
        
        m = (ok+ng)//2
        # print(m)
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    from collections import defaultdict
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    P1 = 10**9+7
    P2 = 2**31-1
    base = 26
    N = II()
    S = list(map(ord,list(input())))
    pow1 = [1]*N
    pow2 = [1]*N
    for i in range(N-1):
        pow1[i+1] = pow1[i]*base%P1
        pow2[i+1] = pow2[i]*base%P2
    hash1 = [0]*(N+1)
    hash2 = [0]*(N+1)
    hash1[1] = hash2[1] = S[0]
    for i in range(2,N+1):
        hash1[i] = (hash1[i-1]*base + S[i-1]) % P1
        hash2[i] = (hash2[i-1]*base + S[i-1]) % P2
    
    def f(x):
        hashes = defaultdict(int)
        for i in range(N-x+1):
            #S[i:i+x]
            h1 = (hash1[i+x] - hash1[i] * pow1[x]) % P1
            h2 = (hash2[i+x] - hash2[i] * pow2[x]) % P2
            if hashes[(h1,h2)] == 0:
                hashes[(h1,h2)] = i
            elif hashes[(h1,h2)] + x <= i:
                return True
        # print(hashes)
        return False
    
    ok = 0
    ng = N//2+1
    while ng-ok > 1:
        
        m = (ok+ng)//2
        # print(m)
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    from collections import defaultdict
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    P1 = 10**9+7
    P2 = 10**7-9
    base = 26
    N = II()
    S = list(map(ord,list(input())))
    pow1 = [1]*N
    pow2 = [1]*N
    for i in range(N-1):
        pow1[i+1] = pow1[i]*base%P1
        pow2[i+1] = pow2[i]*base%P2
    hash1 = [0]*(N+1)
    hash2 = [0]*(N+1)
    hash1[1] = hash2[1] = S[0]
    for i in range(2,N+1):
        hash1[i] = (hash1[i-1]*base + S[i-1]) % P1
        hash2[i] = (hash2[i-1]*base + S[i-1]) % P2
    
    def f(x):
        hashes = defaultdict(int)
        for i in range(N-x+1):
            #S[i:i+x]
            h1 = (hash1[i+x] - hash1[i] * pow1[x]) % P1
            h2 = (hash2[i+x] - hash2[i] * pow2[x]) % P2
            if hashes[(h1,h2)] == 0:
                hashes[(h1,h2)] = i
            elif hashes[(h1,h2)] + x <= i:
                return True
        # print(hashes)
        return False
    
    ok = 0
    ng = N//2+1
    while ng-ok > 1:
        
        m = (ok+ng)//2
        # print(m)
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
b = 27
mod = pow(2, 61) - 1
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
h0 = [0] * m
h0[0] = ord(s[0]) - 96
for i in range(1, m):
    h0[i] = h0[i - 1] * b + (ord(s[i]) - 96) % mod
for i in range(m, 0, -1):
    h = h0[i - 1]
    d = {}
    d[h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d:
            if (j - m + 1 - d[h]) >= i:
                print(i)
                exit()
        else:
            d[h] = j - m + 1
print(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    l = len(S)
    A[0] = l

    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 min(l-i, j-A[k]) > k:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

ans = 0
for i in range(N):
    s = S[i:]
    tmp = z_algo(s)
    
    for i in range(1, len(tmp)):
        if tmp[i] > i:
            tmp[i] = 0
    if len(tmp) >= 2:
        ans = max(ans, max(tmp))
print(ans)

Submission status: Wrong Answer

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

def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    l = len(S)
    A[0] = l

    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        if i <= j:
             A[i] = j
        else:
             A[i] = 0
        k = 1
        while min(l-i, j-A[k]) > k:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

ans = 0
for i in range(N):
    s = S[i:]
    tmp = z_algo(s)
    if len(tmp) >= 2:
        ans = max(ans, max(tmp[1:]))
print(ans)

Submission status: Wrong Answer

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

def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    l = len(S)
    A[0] = l

    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 min(l-i, j-A[k]) > k:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

ans = 0
for i in range(N):
    s = S[i:]
    tmp = z_algo(s)
    if len(tmp) >= 2:
        ans = max(ans, max(tmp[1:]))
print(min(ans, len(S)//2))

Submission status: Wrong Answer

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

def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    l = len(S)
    A[0] = l

    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 min(l-i, j-A[k]) > k:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

ans = 0
for i in range(N):
    s = S[i:]
    tmp = z_algo(s)
    if len(tmp) >= 2:
        ans = max(ans, max(tmp[1:]))
print(ans)

Submission status: Wrong Answer

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

for width in range(N, 0, -1):
    flg = False
    for l in range(N):
        r = l + width
        if r > N:
            break
        s = S[l:r]
        for i in range(l+1, N-width+1):
            if s == S[i:i+width]:
                print(width)
                exit()
print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
m = 0
for width in range(1, N):
    flg = False
    for l in range(N):
        r = l + width
        if r > N:
            break
        s = S[l:r]
        for i in range(l+1, N-width+1):
            if s == S[i:i+width]:
                m = width
                flg = True
                break
        if flg:
          break
print(m)

Submission status: Wrong Answer

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

def kAlgo(S, N):
    szS = N
    Z = [0]*szS
    Z[0] = szS
    i = 1 #current pos
    j = 0 #伸ばす幅
    while i < szS:
        while (i + j < szS) and (j < i and S[j] == S[i+j]): j += 1
        #set Z[i]
        Z[i] = j

        if j == 0:
            i += 1
            continue

        #optimize
        k = 1
        while (k < j) and (k + Z[k] < j):
            Z[i+k] = Z[k]
            k += 1

        i += k
        j -= k

    return max(Z[1:])

ans = 0
for i in range(N-1):
    lenz = kAlgo(S[i:], N-i)
    if ans < lenz:
        ans = lenz

print(ans)

Submission status: Wrong Answer

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

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

ma = 0

for i in range(1,n-1):
    li = z_algo(s[i:])
    max_li = max(li[1:])
    ma = max(ma,max_li)

print(ma)

Submission status: Wrong Answer

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
        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: Wrong Answer

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:
            return True
        dic1[res] = 1
    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: Wrong Answer

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

    vec = [S[i:] for i in range(1, N)]
    vec.sort()

    ans = 0
    for i in range(len(vec) - 1):
        s1, s2 = vec[i], vec[i + 1]
        l = 0
        for c1, c2 in zip(s1, s2):
            if c1 == c2:
                l += 1
            else:
                break
        if ans < l:
            ans = l

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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):
        if j + 1 <= (N - i + 1) // 2:
            continue
        res = max(res, z[j])

print(res)

Submission status: Wrong Answer

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):
        if j <= (N - i) // 2:
            continue
        res = max(res, z[j])

print(res)

Submission status: Wrong Answer

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:])
    print(z)
    for j in range(N - i):
        if j <= (N - i) // 2:
            continue
        res = max(res, z[j])

print(res)

Submission status: Wrong Answer

Solution code:
def suffix_array(s):
    rank = [0 for _ in range(len(s) + 1)]
    res = [0 for _ in range(len(s) + 1)]
    tmp = [0 for _ in range(len(s) + 1)]
    for i in range(len(s) + 1):
        res[i] = i
        rank[i] = ord(s[i]) if i < len(s) else -1
    for k in range(len(s).bit_length()):
        p = 2**k
        res.sort(key=lambda x: (rank[x], rank[x + p]) if x + p <= len(s) else (rank[x], -1))
        tmp[res[0]] = 0
        for i in range(1, len(s) + 1):
            tmp[res[i]] = tmp[res[i - 1]]
            x = (rank[res[i - 1]], rank[res[i - 1] + p]) if res[i - 1] + p <= len(s) else (rank[res[i - 1]], -1)
            y = (rank[res[i]], rank[res[i] + p]) if res[i] + p <= len(s) else (rank[res[i]], -1)
            if x < y: tmp[res[i]] += 1
        for i in range(len(s) + 1):
            rank[i] = tmp[i]
    return res

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

sa = suffix_array(S)
res = 0

for i in range(1, N):
    tmp = 0
    lt = sa[i]
    rt = sa[i + 1]
    for j in range(N - max(lt, rt)):
        if S[lt + j] == S[rt + j]:
            tmp += 1
        else:
            break
    tmp = min(max(abs(rt - lt), (N - min(lt, rt))) // 2, tmp)
    res = max(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
def suffix_array(s):
    rank = [0 for _ in range(len(s) + 1)]
    res = [0 for _ in range(len(s) + 1)]
    tmp = [0 for _ in range(len(s) + 1)]
    for i in range(len(s) + 1):
        res[i] = i
        rank[i] = ord(s[i]) if i < len(s) else -1
    for k in range(len(s).bit_length()):
        p = 2**k
        res.sort(key=lambda x: (rank[x], rank[x + p]) if x + p <= len(s) else (rank[x], -1))
        tmp[res[0]] = 0
        for i in range(1, len(s) + 1):
            tmp[res[i]] = tmp[res[i - 1]]
            x = (rank[res[i - 1]], rank[res[i - 1] + p]) if res[i - 1] + p <= len(s) else (rank[res[i - 1]], -1)
            y = (rank[res[i]], rank[res[i] + p]) if res[i] + p <= len(s) else (rank[res[i]], -1)
            if x < y: tmp[res[i]] += 1
        for i in range(len(s) + 1):
            rank[i] = tmp[i]
    return res

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

sa = suffix_array(S)
res = 0

for i in range(1, N):
    tmp = 0
    lt = sa[i]
    rt = sa[i + 1]
    for j in range(N - max(lt, rt)):
        if S[lt + j] == S[rt + j]:
            tmp += 1
        else:
            break
    tmp = min((N - min(lt, rt)) // 2, tmp)
    res = max(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

def suffix_array(s):
    rank = [0 for _ in range(len(s) + 1)]
    res = [0 for _ in range(len(s) + 1)]
    tmp = [0 for _ in range(len(s) + 1)]
    for i in range(len(s) + 1):
        res[i] = i
        rank[i] = ord(s[i]) if i < len(s) else -1
    for k in range(len(s).bit_length()):
        p = 2**k
        res.sort(key=lambda x: (rank[x], rank[x + p]) if x + p <= len(s) else (rank[x], -1))
        tmp[res[0]] = 0
        for i in range(1, len(s) + 1):
            tmp[res[i]] = tmp[res[i - 1]]
            x = (rank[res[i - 1]], rank[res[i - 1] + p]) if res[i - 1] + p <= len(s) else (rank[res[i - 1]], -1)
            y = (rank[res[i]], rank[res[i] + p]) if res[i] + p <= len(s) else (rank[res[i]], -1)
            if x < y: tmp[res[i]] += 1
        for i in range(len(s) + 1):
            rank[i] = tmp[i]
    return res

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

sa = suffix_array(S)
res = 0

for key, group in groupby(S):
    res = max(res, len(list(group)) // 2)

for i in range(1, N):
    tmp = 0
    lt = sa[i]
    rt = sa[i + 1]
    for j in range(N - max(lt, rt)):
        if S[lt + j] == S[rt + j]:
            tmp += 1
        else:
            break
    tmp = min(abs(rt - lt), tmp)
    res = max(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
def suffix_array(s):
    rank = [0 for _ in range(len(s) + 1)]
    res = [0 for _ in range(len(s) + 1)]
    tmp = [0 for _ in range(len(s) + 1)]
    for i in range(len(s) + 1):
        res[i] = i
        rank[i] = ord(s[i]) if i < len(s) else -1
    for k in range(len(s).bit_length()):
        p = 2**k
        res.sort(key=lambda x: (rank[x], rank[x + p]) if x + p <= len(s) else (rank[x], -1))
        tmp[res[0]] = 0
        for i in range(1, len(s) + 1):
            tmp[res[i]] = tmp[res[i - 1]]
            x = (rank[res[i - 1]], rank[res[i - 1] + p]) if res[i - 1] + p <= len(s) else (rank[res[i - 1]], -1)
            y = (rank[res[i]], rank[res[i] + p]) if res[i] + p <= len(s) else (rank[res[i]], -1)
            if x < y: tmp[res[i]] += 1
        for i in range(len(s) + 1):
            rank[i] = tmp[i]
    return res

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

sa = suffix_array(S)
res = 0

for i in range(1, N):
    tmp = 0
    lt = sa[i]
    rt = sa[i + 1]
    for j in range(N - max(lt, rt)):
        if S[lt + j] == S[rt + j]:
            tmp += 1
        else:
            break
    tmp = min(abs(rt - lt), tmp)
    res = max(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
import random

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash

# 汎用的な二分探索のテンプレ
# check_func(x) = true となるxの最小値を探索する
# left : check_func(x) = falseとなるx
# right: check_func(x) = true となるx
# search_max: check_func(x) = true となるxの"最大値"を探索する場合はTrue
# check_func: answer <= x であればcheck_func(x) = true となるような関数
def binary_search(left: int, right: int, check_func, search_max:bool=False):
    # ok と ng のどちらが大きいかわからないことを考慮
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
            # print(left, right, mid, 't')
        else:
            left = mid
            # print(left, right, mid, 'f')

    return left if search_max else right

def main():
    N = int(input())
    S = input()
    MOD = 998244353
    BASE = random.randint(2, MOD-1)
    rs = RollingHash(S, MOD=MOD, BASE=BASE)

    D = [0] * N
    # 長さLの部分文字列同士が、範囲を重ねず同じ文字列となる場合はTrue,
    # そうでない場合はFalseを返す関数
    def isOK(L):
        if L == 0:
            return True
               
        for i in range(min(L, N - 2 * L + 1)):
            D[i] = rs.hash(i, i + L)
        hashes = set()
        for i in range(L, N - L + 1):
            # 自分より開始点がL以上前の文字列のハッシュを検索対象に追加
            hashes.add(D[i - L])
            D[i] = v = rs.hash(i, i + L)
            # ハッシュが衝突したら、範囲を重ねず同じ文字列となる文字列が存在することになる
            if v in hashes:
                return True
        return False

    # 範囲が重ならないことが条件にあるので、答えは最大でもN // 2（文字列の長さの半分）となる。
    # ただし、二分探索する上で絶対に答えとならない範囲を含めたいので、
    # 探索範囲としてはN // 2 + 1 と、+1しておく。
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n = int(input())
    s = input()

    for l in range(n//2, 0, -1):
        # print(f'------ l: {l} --------')
        s_set = set()
        que = deque([])
        for i in range(0, n-l+1):
            curr_s = s[i:i+l]
            # print(curr_s)
            if curr_s in s_set:
                print(l)
                return
            que.append(curr_s)
            if len(que) >= l-1:
                to_set_s = que.popleft()
                s_set.add(to_set_s)
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    n = int(input())
    s = input()

    for l in range(n//2, 0, -1):
        # print(f'------ l: {l} --------')
        s_set = set()
        que = deque([])
        for i in range(0, n-l+1):
            curr_s = s[i:i+l]
            # print(curr_s)
            if curr_s in s_set:
                print(l)
                return
            que.append(curr_s)
            if len(que) >= l-1:
                to_set_s = que.popleft()
                s_set.add(to_set_s)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input())
    s = input()

    for l in range(n//2, 0, -1):
        for offset in range(0,l):
            s_set = set()
            for i in range(0, n-l-offset+1):
                curr_s = s[offset+i : offset+i+l : l]
                if curr_s in s_set:
                    print(l)
                    return
                s_set.add(curr_s)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def z_algorithm(S):
    # 文字列が与えられた時、各 i について
    # 「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を
    #  O(|S|) で構築するアルゴリズム
    # S: aaabaaaab
    # A: 921034210
    # 例えば、A[5] = 4だが、これは、S[0:4] == S[5:5+4] 
    # (Sの0文字目からと5文字目からは、4文字一致している(aaab)) ことを意味する。

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    # i: 調査開始点
    # iを1文字目からlen(S)-1文字目まで左から順に動かしていく
    while i < lenS:
        # j: 何文字目まで一致するか(iからの距離)
        # 一致しなくなるまでjを左から右へ動かしていく
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        # 1文字も一致しない場合は調査開始点を一つ右にずらす
        if j == 0:
            i += 1
            continue

        A[i] = j

        # 例）S: momomosumomomomo
        # A[1] = 0, A[2] = 4 (A[0:4] == A[2:2+4] = "momo")

        # i=2の調査が終わった段階で、
        # S[3] = S[2 + 1] = S[1] = "o" 
        # で、A[3] = A[1] = 0（Sの1文字目からと3文字目からは一致しない）
        # のは明らかなので、i = 3の結果はi = 1の結果を流用して0とする。
        # つまり、A[3] = A[2 + 1] = A[1] = 0

        # 今回、i + j 文字目まで、一致するか調べたので、
        # A[i + 1] ~ A[i + j - 1] までの間で、計算結果を流用できるところは流用する
        # j <= k + A[k] となるようなkの場合、
        # j文字目以降は今回調べてないので一致するか本当に分からないので、流用をやめる
        # 今回の場合、
        # k = 1: 1 + A[1] = 1 + 0 = 1 < j = 4 なので、流用できる
        # k = 2: 2 + A[2] = 2 + 4 = 6 > j = 4 なので、流用できない
        # つなり、k=2となった瞬間、流用をせずにループを抜ける。
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        # 今回 1回 (=k-1回) 流用できた、つまり A[3] = A[2(=i) + 2(=k) - 1] まで確定したので、
        # 次は A[4] = A[i + k] から調べる
        i += k

        # また、k = 2 のとき、k + A[k] >= j となって流用を打ち切られたということは、
        # k + A[i + k] >= j  => A[i + k] >= j - k
        # A[4] は少なくとも j - k = 4 - 2 = 2 以上となることが確定する。
        # つまり、S[4:]とSは、少なくとも最初の2文字 (j-k文字) は一致する。
        # よって、A[4]を調べるときは、j=2から調査を開始すればよい。
        # （つまり、S[6]とS[4:][2]が一致しているか調べるところから始める）

        #             0123456
        # S         = momomosumomomomo
        # S[2:]     =   momosumomomomo   <- 5文字目が違う
        # S[2:][2:] =     mosumomomomo   <- 3文字目が違う
        # S[4:]     =     mosumomomomo   <- 3文字目が違う
        # S[4:][2:] =       sumomomomo   <- 1文字目が違う
        j -= k
    return A

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

    ans = 0

    # Z-algorithm で、最長共通接頭辞の長さを調べる。
    # Z-algorithm は、「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録するので、
    # S[1]以降の部分文字列同士の長さは、
    # S=S[i:]としてiをずらしながら最長共通接頭辞を調べることで分かる

    for i in range(N-1):
        A = z_algorithm(S[i:])
        # A[0] = len(S[i:]) となっている（S[i:] とS[i:][0:] は完全一致）
        # そのため、これ以外の中で最も一致するときの長さを求める
        ans = max(ans, max(A[1:]))

    print(ans)

if __name__ == '__main__':
    main()