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:
import sys

input = sys.stdin.readline


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

        ans = 0
        for i in range(N - 1):
            ans = max((self.longest_common_subsequence(S[i:]), ans))

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_end, z_box_start = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲内
                if z[i - z_box_start] < z_box_end - i + 1:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    current_pos = z_box_end + 1
                    while current_pos < len(s) and current_pos - i < i and s[current_pos] == s[current_pos - i]:
                        current_pos += 1
                    z[i] = current_pos - i
                    # Z-Box の更新
                    z_box_start, z_box_end = i, current_pos

        # 最大長を返却
        return max(z[1:])


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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        ans = 0
        for i in range(N - 1):
            ans = max((self.longest_common_subsequence(S[i:]), ans))

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_end, z_box_start = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲内
                if z[i - z_box_start] < z_box_end - i + 1:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    current_pos = z_box_end + 1
                    while current_pos < len(s) and current_pos - i < i and s[current_pos] == s[current_pos - i]:
                        current_pos += 1
                    z[i] = current_pos - i
                    # Z-Box の更新
                    z_box_start, z_box_end = i, z_box_end + z[i]

        # 最大長を返却
        return max(z[1:])


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

Submission status: Wrong Answer

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

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

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

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, dp[i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        ans = 0
        for i in range(N - 1):
            ans = max((self.longest_common_subsequence(S[i:]), ans))

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_end, z_box_start = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲内
                if z[i - z_box_start] < z_box_end - i + 1:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    while z_box_end + 1 + z[i] < len(s) and z[i] < i and s[z_box_end + 1 + z[i]] == s[z_box_end + 1 + z[i] - i]:
                        z[i] += 1
                    # Z-Box の更新
                    z_box_start, z_box_end = i, z_box_end + z[i]

        # 最大長を返却
        return max(z[1:])


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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        ans = 0
        for i in range(N - 1):
            ans = max((self.longest_common_subsequence(S[i:]), ans))

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_end, z_box_start = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲内
                if z[i - z_box_start] < z_box_end - i + 1:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    while z_box_end + 1 + z[i] < len(s) and s[z_box_end + 1 + z[i]] == s[z_box_end + 1 + z[i] - i]:
                        z[i] += 1
                    # Z-Box の更新
                    z_box_start, z_box_end = i, z_box_end + z[i]

        # 最大長を返却
        return max(z[1:])


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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        ans = 0
        for i in range(N - 1):
            ans = max((self.longest_common_subsequence(S[i:]), self.longest_common_subsequence(S[::-1][i:]), ans))

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_end, z_box_start = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲内
                if z[i - z_box_start] < z_box_end - i + 1:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    z[i] = z_box_end + 1
                    while z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] - i]:
                        z[i] += 1
                    # Z-Box の更新
                    z_box_start, z_box_end = i, z[i] - 1

        # 最大長を返却
        return max(z[1:])


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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right] and right < top:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 左端＝右端だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
    return max(lcp)

def main():
    n = int(input())
    s = input()[:-1]
    ans = 0
    for i in range(n // 2):
        ans = max(ans, LcpByZ(s[i:]))
    print(ans)

main()

Submission status: Wrong Answer

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

dp = [[-1] * N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0
for i in range(N-1):
    if S[i] == S[N-1]:
        dp[i][N-1] = 1

d = [(-1,-1), (-1, 0), (0, -1)]

for i in range(N-1, -1, -1):
    for j in range(N-1, i-1, -1):
        for di, dj in d:
            ni = i + di
            nj = j + dj
            if not(0 <= ni < nj < N):
                continue
            if (di, dj) == (-1, -1) and S[ni] == S[nj] and ni + dp[i][j] < nj:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1)
            else:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j])

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, dp[i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        ans = 0
        for i in range(N - 1):
            ans = max(self.longest_common_subsequence(S[i:]), ans)

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_end, z_box_start = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲内
                if z[i - z_box_start] < z_box_end - i + 1:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    z[i] = z_box_end + 1
                    while z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] - i]:
                        z[i] += 1
                    # Z-Box の更新
                    z_box_start, z_box_end = i, z[i] - 1

        # 最大長を返却
        return max(z[1:])


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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = 0
        p = 1
        for i in range(1, len(t) + 1):
            h = hash_table[i] = (h * base + t[i - 1]) % hash_md
            p = pw[i] = p * base % hash_md

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

    n = int(input())
    s = input()[:-1]

    # 初期化
    base = 29
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0] * (len(t) + 1)
    pw = [1] * (len(t) + 1)
    hash_ini(t)

    # 長さを二分探索
    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        w = (ok + ng) // 2
        hashes = []
        for i in range(w):
            hashes.append(hash_ij(i, i + w))
        passed = set()
        for i in range(w, n - w + 1):
            passed.add(hashes[i - w])
            cur = hash_ij(i, i + w)
            if cur in passed:
                ok = w
                break
            hashes.append(cur)
        else:
            ng = w

    print(ok)

main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        ans = 0
        for i in range(N - 1):
            ans = max(self.longest_common_subsequence(S[i:]), ans)

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_end, z_box_start = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲内
                if z[i - z_box_start] < z_box_end - i + 1:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    z[i] = z_box_end + 1
                    while z[i] < len(s) and s[z[i]] == s[z[i] - i]:
                        z[i] += 1
                    # Z-Box の更新
                    z_box_start, z_box_end = i, z[i] - 1

        # 最大長を返却
        return max(z[1:])


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

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N)[::-1]:
    for j in range(N)[::-1]:
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

max(max(min(dp[a][b], a-b) for a in range(b, N)) for b in range(N))

Submission status: Wrong Answer

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

def z_algorithm(str):
    len_str = len(str)
    p = [0] * len_str
    j = 0
    for i in range(1, len_str):
        if i + p[i-j] < j + p[j]:
            p[i] = p[i-j]
        else:
            k = max(0, j+p[j]-i)
            while i + k < len_str and str[k] == str[i+k] and k < i:
                k += 1
            p[i] = k
            j = i
    p[0] = 0
    return max(p)

ans = 0
for x in range(n):
    ans = max(ans, z_algorithm(s[x:]))

print(ans)

Submission status: Wrong Answer

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

def z_algorithm(str):
    len_str = len(str)
    p = [0] * len_str
    j = 0
    for i in range(1, len_str):
        if i + p[i-j] < j + p[j]:
            p[i] = p[i-j]
        else:
            k = max(0, j+p[j]-i)
            while i + k < len_str and str[k] == str[i+k] and k < i:
                k += 1
            p[i] = k
            j = i
    p[0] = 0
    return max(p)

ans = 0
for x in range(n-1):
    ans = max(ans, z_algorithm(s[x:]))

print(ans)

Submission status: Wrong Answer

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

def z_algorithm(str):
    len_str = len(str)
    p = [0] * len_str
    j = 0
    for i in range(1, len_str):
        if i + p[i-j] < j + p[j]:
            p[i] = p[i-j]
        else:
            k = max(0, j+p[j]-i)
            while i + k < len_str and str[k] == str[i+k] and k < i:
                k += 1
            p[i] = k
            j = i
    p[0] = 0
    return max(p)

ans = 0
for i in range(n-1):
    ans = max(ans, z_algorithm(s[i:]))

print(ans)

Submission status: Wrong Answer

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

length = 0 

for i in range(N):
    l1 = i
    l2 = i + length
    _word = S[l1:l2]
    _S = S[l2:]
    while _word in _S and l1 + len(_word) < l2:
        l2 += 1
        _word = S[l1:l2]
        _S = S[l2:]
    length = max(len(_word)-1, length)

print(length)

Submission status: Wrong Answer

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

L = []

for i in range(n):
    L.append([s[i:], i])

L.sort()
ans = 0

for i in range(len(L)-1):
    temp = 0
    a = L[i][0]
    b = L[i+1][0]
    for j in range(min(len(a), len(b), abs(L[i][1] - L[i+1][1]))):
        if a[j] == b[j]:
            temp += 1
        else:
            break
    ans = max(temp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table.append(h)
        p = 1
        for i in range(1, len(t)):
            h = hash_table[i] = (h * base + t[i]) % hash_md
            p = pw[i] = p * base % hash_md

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

    n = int(input())
    s = input()[:-1]

    # 初期化
    base = 29
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0] * len(t)
    pw = [1] * len(t)
    hash_ini(t)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()

Submission status: Wrong Answer

Solution code:
def z_algorithm(s):

    Z = [0] * len(s)
    Z[0] = len(s)
    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            n = 0      
            while n + k < len(s) and s[n] == s[n + k]:
                n += 1
            Z[k] = n
        if n > 0:
                lt = k
                rt = k + n - 1
        else:
            p = k - lt
            right_part_len = rt - k + 1
            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k
                lt = k
                rt = i - 1              
    return Z
  
N = int(input())
S = input()

maxlen = 0
for i in range(0, N - 1):
    maxlen_tmp = max(z_algorithm(S[i:N])[1:])
    l_1 = i + 1
    l_2 = N - maxlen_tmp + 1
    if maxlen < maxlen_tmp and l_1 + maxlen_tmp <= l_2:
        maxlen = maxlen_tmp
print(maxlen)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right] and right < top:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 左端＝右端だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
    return max(lcp)

def main():
    n = int(input())
    s = input()[:-1]
    ans = 0
    for i in range(n):
        ans = max(ans, LcpByZ(s[i:]))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right] and right < top:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 左端＝右端だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
    return max(lcp)

def main():
    n = int(input())
    s = input()[::-1]
    ans = 0
    for i in range(n):
        ans = max(ans, LcpByZ(s[i:]))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right] and right < top:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 左端＝右端だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
    return max(lcp)

def main():
    n = int(input())
    s = input()[::-1]
    ans = 0
    for i in range(n // 2):
        ans = max(ans, LcpByZ(s[i:]))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
 
stringCount = int(input())
targetString = input()
 
maxCount = stringCount // 2
 
for exclusionCount in range(maxCount):
    count = maxCount - exclusionCount
 
    for i in range(maxCount):
        if (i + count * 2) > stringCount:
            break
 
        word = targetString[i:count]
        end = stringCount - len(word)
        if (targetString.count(word, 0, end) > 1):
            print('{}'.format(count))
            sys.exit()
 
print('0')

Submission status: Wrong Answer

Solution code:
# ABC141E - Who Says a Pun?
class RollingHash:
    def __init__(self, source: str, base=1000000007, mod=9007199254740997):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self):  # compute hash of interval [0, right)
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self):  # computer mod of power of base
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, l: int, r: int):  # compute hash of interval [left, right)
        return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.mod


def main():
    N = int(input())
    S = input().rstrip()
    rh, ok, ng = RollingHash(S, 27, 2053), 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, memo = 0, set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = 1
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
S=str(input())
rg = len(S)//2
maxlen=0
for i in range(int(np.log2(len(S))+1)):
  flg=0
  for j in range(0, len(S)-2*rg+1):
    if S[j:j+rg] in S[j+rg:]:
      maxlen=rg
      flg=1
      break
  if flg==1:
    rg += len(S)//(2**(i+2))
    if i == int(np.log2(len(S))-1):
      rg += 1
  else:
    rg -= len(S)//(2**(i+2))
    if i == int(np.log2(len(S))-1):
      rg -= 1
print(maxlen)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    l1 = length = 0
    l2 = 1
    temp = 0

    while (l2 + length < N):
        print("s[l1:l2]" , S[l1:l2])
        print("s[l2:]" , S[l2:])
        if S[l1:l2] in S[l2:]:
            temp = l2 - l1
            length = l2 - l1
            l2 += 1
            print("length = ", length)
        else:
            l1 += max(1, temp)
            l2 = l1 + length + 1
            temp = 0
    print(length)

main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    l1 = length = 0
    l2 = 1
    temp = 0

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

main()

Submission status: Wrong Answer

Solution code:
import re
N = int(input())
S = input()
ans = re.search(r"(.+).*\1", S)
if ans:
    print(len(ans.group(1)))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
input= sys.stdin.readline
n = int(input())
s = input()
cnt = 0
flag = False
for i in range(n//2):
    for j in range(n-i-1):
        for k in range(n-j-2*i-1):
            if s[j:j+i+1]==s[j+i+k+1:j+2*i+k+2]:
                flag = True
                cnt = i+1
                break
        if flag:
            flag = False
            break

Submission status: Wrong Answer

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

def search(n):
    if n == 0:
        return False
    for i in range(N-n):
            if S.rfind(S[i:i+n]) > i:
                return True
    return False

l = 1
r = N//2+1

while l<r:
    mid = (l+r)//2
    if search(mid):
        l = mid+1
    else:
        r = mid

print(l-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
String=input()
max=0

for f in range(len(String)):
    S=String[f:]
    A = [0] * len(S)
    A[0] = len(S)
    i, j = 1, 0
    #print(S)
    while(i<len(S)):
        #print(A)
        #print("i= " + str(i) + "j= " + str(j))
        while(i+j<len(S) and S[j]==S[i+j]):
            #print("i= "+str(i)+"j= "+str(j))
            j+=1
        A[i]=j
        if(j>max):
            max=j
        if(j==0):
            i+=1
            continue
        k=1
        while(k+i<len(S) and k+A[k]<j):
            A[i+k]=A[k]
            k+=1
        i+=k
        j=0


#print(A)
print(max)

Submission status: Wrong Answer

Solution code:
def z_advanced(s): # The most part of this function is cited from: https://ivanyu.me/blog/2013/10/15/z-algorithm/
    """An advanced computation of Z-values of a string."""
 
    Z = [0] * len(s)
    Z[0] = 0
 
    rt = 0
    lt = 0
 
    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            
            if n >= k+1:
                Z[k] = k
            else:
                Z[k] = n

            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.
 
            p = k - lt  # Pair index.
            right_part_len = rt - k + 1
 
            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                  
                if i-k >= k+1:
                    Z[k] = k
                else:
                    Z[k] = i - k
 
                lt = k
                rt = i - 1
    return Z
  
n = int(input())
s = input()

z_scores = []
for i in range(len(s)):
    z_scores.append(max(z_advanced(s[i:])))

print(max(z_scores))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(map(str, input().strip()))
seed = 13331
mod = 10 ** 9 + 9

lsd = [1] * 6000
hs = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod


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]) % mod
        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)