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:
# TLE
# n = int(input())
# s = input()
n = 5000
s = "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"


def arihon_SA(T):
    rank = [0] * (n + 1)
    SA = [0] * (n + 1)
    temp = [0] * (n + 1)

    def rank_calc(i):
        res1 = rank[i]
        res2 = -1
        if i + k <= n:
            res2 = rank[i + k]
        return (res1, res2)

    for i in range(n + 1):
        SA[i] = i
        if i < n:
            rank[i] = ord(T[i])
        else:
            rank[i] = -1
    k = 1

    while k <= n:
        SA.sort(key=rank_calc)
        temp[SA[0]] = 0
        for i in range(1, n + 1):
            temp[SA[i]] = temp[SA[i - 1]]
            if rank_calc(SA[i - 1]) < rank_calc(SA[i]):
                temp[SA[i]] += 1
        rank = temp[::]
        k *= 2

    return SA


# SAとsからSA[i+1],SA[i]の共通接頭辞LCP[i]を求めたい。
# len(s)=nならlen(SA)=n+1
# LCP[0]は必ず0
def arihon_LCP(s, SA):
    num = len(s)
    rank = [0] * (num + 1)
    LCP = [-1] * (num)
    for i in range(num + 1):
        rank[SA[i]] = i
    h = 0
    LCP[0] = 0
    for i in range(num):
        j = SA[rank[i] - 1]
        if h > 0:
            h -= 1
        while j + h < num and i + h < num:
            if s[j + h] != s[i + h]:
                break
            else:
                h += 1
        LCP[rank[i] - 1] = h
    return LCP


SA = arihon_SA(s)
LCP = arihon_LCP(s, SA)

# sparse table
num = n.bit_length()
ST = [[0] * (num + 1) for _ in range(n)]

for i in range(n):
    ST[i][0] = LCP[i]

for j in range(num):
    for i in range(n):
        ST[i][j + 1] = ST[i][j]
        delta = 1 << j
        if i + delta < n:
            ST[i][j + 1] = min(ST[i][j + 1], ST[i + delta][j])


def query(a, b):
    if a > b:
        a, b = b, a
    d = (b - a).bit_length() - 1
    delta = 1 << d
    res = min(ST[a][d], ST[b - delta][d])
    return res


ans = 0
for i in range(n):
    for j in range(i + 1, n + 1):
        a = SA[i]
        b = SA[j]
        temp = query(i, j)
        if abs(b - a) >= temp:
            ans = max(ans, temp)
print(ans)

Submission status: Wrong Answer

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


def arihon_SA(T):
    rank = [0] * (n + 1)
    SA = [0] * (n + 1)
    temp = [0] * (n + 1)

    def rank_calc(i):
        res1 = rank[i]
        res2 = -1
        if i + k <= n:
            res2 = rank[i + k]
        return (res1, res2)

    for i in range(n + 1):
        SA[i] = i
        if i < n:
            rank[i] = ord(T[i])
        else:
            rank[i] = -1
    k = 1

    while k <= n:
        SA.sort(key=rank_calc)
        temp[SA[0]] = 0
        for i in range(1, n + 1):
            temp[SA[i]] = temp[SA[i - 1]]
            if rank_calc(SA[i - 1]) < rank_calc(SA[i]):
                temp[SA[i]] += 1
        rank = temp[::]
        k *= 2

    return SA


# SAとsからSA[i+1],SA[i]の共通接頭辞LCP[i]を求めたい。
# len(s)=nならlen(SA)=n+1
# LCP[0]は必ず0
def arihon_LCP(s, SA):
    num = len(s)
    rank = [0] * (num + 1)
    LCP = [-1] * (num)
    for i in range(num + 1):
        rank[SA[i]] = i
    h = 0
    LCP[0] = 0
    for i in range(num):
        j = SA[rank[i] - 1]
        if h > 0:
            h -= 1
        while j + h < num and i + h < num:
            if s[j + h] != s[i + h]:
                break
            else:
                h += 1
        LCP[rank[i] - 1] = h
    return LCP


SA = arihon_SA(s)
LCP = arihon_LCP(s, SA)

# sparse table
num = n.bit_length()
ST = [[0] * (num + 1) for _ in range(n)]

for i in range(n):
    ST[i][0] = LCP[i]
for i in range(n):
    for j in range(num):
        ST[i][j + 1] = ST[i][j]
        delta = 1 << j
        if i + delta < n:
            ST[i][j + 1] = min(ST[i][j + 1], ST[i + delta][j])


def query(a, b):
    if a > b:
        a, b = b, a
    d = (b - a).bit_length() - 1
    delta = 1 << d
    res = min(ST[a][d], ST[b - delta][d])
    return res


ans = 0
for i in range(n):
    for j in range(i + 1, n + 1):
        a = SA[i]
        b = SA[j]
        temp = query(i, j)
        if abs(b - a) >= temp:
            ans = max(ans, temp)
print(ans)

Submission status: Wrong Answer

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


def arihon_SA(T):
    rank = [0] * (n + 1)
    SA = [0] * (n + 1)
    temp = [0] * (n + 1)

    def rank_calc(i):
        res1 = rank[i]
        res2 = -1
        if i + k <= n:
            res2 = rank[i + k]
        return (res1, res2)

    for i in range(n + 1):
        SA[i] = i
        if i < n:
            rank[i] = ord(T[i])
        else:
            rank[i] = -1
    k = 1

    while k <= n:
        SA.sort(key=rank_calc)
        temp[SA[0]] = 0
        for i in range(1, n + 1):
            temp[SA[i]] = temp[SA[i - 1]]
            if rank_calc(SA[i - 1]) < rank_calc(SA[i]):
                temp[SA[i]] += 1
        rank = temp[::]
        k *= 2

    return SA


def arihon_LCP(s, SA):
    num = len(s)
    rank = [0] * (num + 1)
    LCP = [-1] * (num)
    for i in range(num + 1):
        rank[SA[i]] = i
    h = 0
    LCP[0] = 0
    for i in range(num):
        j = SA[rank[i] - 1]
        if h > 0:
            h -= 1
        while j + h < num and i + h < num:
            if s[j + h] != s[i + h]:
                break
            else:
                h += 1
        LCP[rank[i] - 1] = h
    return LCP


class SegmentTree:
    ele = 10 ** 20
    func = min
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # maspy式。開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


SA = arihon_SA(s)
LCP = arihon_LCP(s, SA)
# ST = SegmentTree(n)
# ST.initialize(SA)
# ans = 0
# for i in range(n + 1):
#     for j in range(i + 1, n + 1):
#         temp = ST.query(i, j)
#         if j - i >= temp:
#             ans = max(ans, temp)
# print(ans)

Submission status: Wrong Answer

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


def arihon_SA(T):
    rank = [0] * (n + 1)
    SA = [0] * (n + 1)
    temp = [0] * (n + 1)

    def rank_calc(i):
        res1 = rank[i]
        res2 = -1
        if i + k <= n:
            res2 = rank[i + k]
        return (res1, res2)

    for i in range(n + 1):
        SA[i] = i
        if i < n:
            rank[i] = ord(T[i])
        else:
            rank[i] = -1
    k = 1

    while k <= n:
        SA.sort(key=rank_calc)
        temp[SA[0]] = 0
        for i in range(1, n + 1):
            temp[SA[i]] = temp[SA[i - 1]]
            if rank_calc(SA[i - 1]) < rank_calc(SA[i]):
                temp[SA[i]] += 1
        rank = temp[::]
        k *= 2

    return SA


def arihon_LCP(s, SA):
    num = len(s)
    rank = [0] * (num + 1)
    LCP = [-1] * (num)
    for i in range(num + 1):
        rank[SA[i]] = i
    h = 0
    LCP[0] = 0
    for i in range(num):
        j = SA[rank[i] - 1]
        if h > 0:
            h -= 1
        while j + h < num and i + h < num:
            if s[j + h] != s[i + h]:
                break
            else:
                h += 1
        LCP[rank[i] - 1] = h
    return LCP


class SegmentTree:
    ele = 10 ** 20
    func = min
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # maspy式。開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


SA = arihon_SA(s)
# LCP = arihon_LCP(s, SA)
# ST = SegmentTree(n)
# ST.initialize(SA)
# ans = 0
# for i in range(n + 1):
#     for j in range(i + 1, n + 1):
#         temp = ST.query(i, j)
#         if j - i >= temp:
#             ans = max(ans, temp)
# print(ans)

Submission status: Wrong Answer

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


def arihon_SA(T):
    rank = [0] * (n + 1)
    SA = [0] * (n + 1)
    temp = [0] * (n + 1)

    def rank_calc(i):
        res1 = rank[i]
        res2 = -1
        if i + k <= n:
            res2 = rank[i + k]
        return (res1, res2)

    for i in range(n + 1):
        SA[i] = i
        if i < n:
            rank[i] = ord(T[i])
        else:
            rank[i] = -1
    k = 1

    while k <= n:
        SA.sort(key=rank_calc)
        temp[SA[0]] = 0
        for i in range(1, n + 1):
            temp[SA[i]] = temp[SA[i - 1]]
            if rank_calc(SA[i - 1]) < rank_calc(SA[i]):
                temp[SA[i]] += 1
        rank = temp[::]
        k *= 2

    return SA


def arihon_LCP(s, SA):
    num = len(s)
    rank = [0] * (num + 1)
    LCP = [-1] * (num)
    for i in range(num + 1):
        rank[SA[i]] = i
    h = 0
    LCP[0] = 0
    for i in range(num):
        j = SA[rank[i] - 1]
        if h > 0:
            h -= 1
        while j + h < num and i + h < num:
            if s[j + h] != s[i + h]:
                break
            else:
                h += 1
        LCP[rank[i] - 1] = h
    return LCP


class SegmentTree:
    ele = 10 ** 20
    func = min
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # maspy式。開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


SA = arihon_SA(s)
LCP = arihon_LCP(s, SA)
ST = SegmentTree(n)
ST.initialize(SA)
ans = 0
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        temp = ST.query(i, j)
        if j - i >= temp:
            ans = max(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
# 32bitのMod一つでRollingHashを行った場合、
# 10**5個程度のHashを生成するだけでも
# 半分以上の確率でどこかのHashが衝突していることが分かります


# 小文字アルファベットの時のbese
base = 27  # alphabet


def getnum(x):
    return ord(x) - ord("a") + 1


# rolling hash実装

# 必要な定数
# mod = 1<<61-1としたときの高速余り計算
m30 = (1 << 30) - 1
m31 = (1 << 31) - 1
m61 = (1 << 61) - 1
mod = m61
positive_delta = m61 * 4

# 高速化された計算
def mul(a, b):
    au = a >> 31
    ad = a & m31  # 余りを取ることが&演算でできる
    bu = b >> 31
    bd = b & m31
    mid = ad * bu + au * bd
    midu = mid >> 30
    midd = mid & m30
    return calcmod(au * bu * 2 + midu + (midd << 31) + ad * bd)


def calcmod(a):
    au = a >> 61
    ad = a & m61
    res = au + ad
    if res >= m61:
        res -= m61
    return res


# s:string
def rollinghash(s):
    num = len(s)
    res = [0] * (num + 1)
    pow_base = [1] * (num + 1)
    for i in range(num):
        res[i + 1] = calcmod(mul(res[i], base) + getnum(s[i]))
        pow_base[i + 1] = calcmod(mul(pow_base[i], base))
    return res, pow_base


def search(left, right, rh):
    return calcmod(rh[right] - rh[left] * pow_base[right - left] + positive_delta)


n = int(input())
s = input()
rh, pow_base = rollinghash(s)

ng = n
ok = 0


def hantei(x, rh):
    kumi = {}
    for i in range(n - x + 1):
        temp = search(i, i + x, rh)
        if temp in kumi:
            pre_idx = kumi[temp]
            if i - pre_idx >= x:
                # print("pair", i, pre_idx, "delta", x)
                return True
        else:
            kumi[temp] = i
    # print(x, kumi)
    return False


while ng - ok > 1:
    mid = (ng + ok) // 2
    if hantei(mid, rh):
        ok = mid
    else:
        ng = mid
    # print(ok, ng)

print(ok)

Submission status: Wrong Answer

Solution code:
import random
from collections import defaultdict


def atoi(s):
    return ord(s) - ord("a") + 1


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

mod = (1 << 61) - 1
b = random.randint(10000, mod - 1)


l = 0
r = (N + 1) // 2
while r - l > 1:
    d = (r + l) // 2
    memo = defaultdict(int)
    isok = False
    h = 0
    t = pow(b, d, mod)
    for i in range(d):
        h = (h * b + atoi(S[i])) % mod
    memo[h] = 0
    for i in range(1, N - d + 1):
        h = (h*b + atoi(S[i+d-1]) - t * atoi(S[i-1])) % mod
        if not memo[h]:
            memo[h] = i
        elif memo[h] and i - memo[h] >= d:
            isok = True
    if isok:
        l = d
    else:
        r = d

print(l)

Submission status: Wrong Answer

Solution code:
import random
from collections import defaultdict
N = int(input())
S = input()

mod = (1 << 61) - 1
b = random.randint(10000, mod - 1)


l = 0
r = (N + 1) // 2
while r - l > 1:
    d = (r + l) // 2
    memo = defaultdict(int)
    isok = False
    h = 0
    t = pow(b, d, mod)
    for i in range(d):
        h = (h * b + ord(S[i])) % mod
    memo[h] = 0
    for i in range(1, N - d + 1):
        h = (h*b + ord(S[i+d-1]) - t * ord(S[i-1])) % mod
        if not memo[h]:
            memo[h] = i
        elif memo[h] and i - memo[h] >= d:
            isok = True
    if isok:
        l = d
    else:
        r = d

print(l)

Submission status: Wrong Answer

Solution code:
import random
from collections import defaultdict
N = int(input())
S = input()

mod = (1 << 61) - 1
b = random.randint(100, mod - 1)


l = 0
r = (N + 1) // 2
while r - l > 1:
    d = (r + l) // 2
    memo = defaultdict(int)
    isok = False
    h = 0
    t = pow(b, d, mod)
    for i in range(d):
        h = (h * b + ord(S[i])) % mod
    memo[h] = 0
    for i in range(1, N - d + 1):
        h = (h*b + ord(S[i+d-1]) - t * ord(S[i-1])) % mod
        if not memo[h]:
            memo[h] = i
        elif memo[h] and i - memo[h] >= d:
            isok = True
    if isok:
        l = d
    else:
        r = d

print(l)

Submission status: Wrong Answer

Solution code:
class RollingHash:
    def __init__(self, s):
        B = 10**5+7
        self.MOD = 10**9+7

        size = len(s)
        self.hashtable = [0] * (size+1)
        self.power = [0] * (size+1)
        self.power[0] = 1

        for i in range(1, size+1):
            self.hashtable[i] = (self.hashtable[i-1] * B + ord(s[i-1]))%self.MOD
        for i in range(1, size+1):
            self.power[i] = (B * self.power[i-1])%self.MOD

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        return (self.hashtable[r]-self.hashtable[l]*self.power[r-l])%self.MOD

from collections import defaultdict

def solve1():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    ans = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1]!=S[j-1]:continue

            left = 1
            right = min(j-i, size-j+1)+1

            while right-left>1:
                m = (left+right)//2
                if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                    left = m
                else:
                    right = m
            ans = max(ans, left)

    print(ans)


def solve2():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    def check(m):
        d = defaultdict(lambda :10**20)
        for i in range(1, size-m+2):
            h = hash_table.get_hash(i, m)
            d[h] = min(d[h], i)
            if (i-d[h])>=m:
                return True
        return False

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

    print(left)

if __name__ == "__main__":
    # solve1()
    solve2()

Submission status: Wrong Answer

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

def ZA(n,s):
    Z=[0 for i in range(n)]
    Z[0]=n
    i=1
    j=0
    cand=0
    while i<n:
        while i+j<n and s[j]==s[i+j]:
            j+=1
        Z[i]=j
        cand=max(cand,min(Z[i],i))
        if j==0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            cand=max(cand,min(Z[i],i))
            k+=1
        i+=k
        j-=k
    #print(Z)
    return cand


alp={c:True for c in list("abcdefghijklmnopqrstuvwxyz")}
ans=0
for i in range(n):
    if alp[s[i]]:
        alp[s[i]]=False
        ans=max(ans,ZA(n-i,s[i:]))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
b = 27
mod = pow(2, 31) - 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
d = [{} for _ in range(m + 1)]
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[i][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[i]:
            if (j - i + 1 - d[i][h]) >= i:
                print(i)
                exit()
        else:
            d[i][h] = j - i + 1
print(0)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n = int(input())
    s_s = input()
    lens_s = len(s_s)
    ans = 0
    for i in range(1, lens_s // 2 + 1):
        work_dict = {}
        for j in range(99999):
            if lens_s < i + j:
                break
            target = s_s[j:i + j]
            if work_dict.get(target, "") == "":
                work_dict[target] = i + j
            else:
                if work_dict[target] < i + j:
                    ans = len(target)
                    break

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
ababa"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2
xy"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """13
strangeorange"""
        output = """5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

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

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

        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1        
        else:
            dp[i][j] = dp[i+1][j+1]

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

Submission status: Wrong Answer

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

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i == n-1 or j == n-1:
            if s[i] == s[j]:
                dp[i][j] += 1
            continue

        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1        
        else:
            dp[i][j] = dp[i+1][j+1]

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        ans = max(ans, min(abs(j-i), dp[i][j]))
print(ans)

Submission status: Wrong Answer

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

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

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

ans = 0
for d in dp:
  ans = max(ans, max(d))

print(ans)

Submission status: Wrong Answer

Solution code:
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

def lsb(n):
    return (n&-n).bit_length()

def max2(x,y):
    return x if x > y else y

N = int(input())
S = input().rstrip()
P = [0]*26
res = 0

for i, s in enumerate(S):
    P[ord(s)-ord("a")] |= 1<<(N-i)

for i in range(N):
    temp = P[ord(S[i])-ord("a")]
    j = 1
    while popcnt(temp) >= 2 and i+j < N and j <= temp.bit_length()-lsb(temp):
        temp >>= 1
        temp &= P[ord(S[i+j])-ord("a")]
        j += 1
    j -= 1
    res = max2(res, j)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np



def main(N,dp):
    dp[0, 0] = min(N[0], 11 - N[0])
    dp[0, 1] = min(N[0] + 1, 10 - N[0])
    for i in range(1, len(N)):
        dp[i, 0] = min(dp[i - 1, 0] + N[i], dp[i - 1, 1] + 10 - N[i])
        dp[i, 1] = min(dp[i - 1, 0] + N[i] + 1, dp[i - 1, 1] + 9 - N[i])
    print(dp[-1][0])


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8,i8[:],)')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    #from my_module import main
    N = np.array([int(_) for _ in input()])
    dp = np.array([[0, 0] for _ in range(len(N))])
    main(N, dp)

Submission status: Wrong Answer

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

lb=0
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)