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 random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=10**9+7):
        rh = 0
        for s in S:
            rh *= b
            rh %= m
            c = self._c(s)
            rh += c
            rh %= m
        size = len(S)
        self.S = S
        self.rh = rh
        self.rh_head = rh
        self.b = b
        self.bn = pow(b, size, m)
        self.binv = pow(b, m-2, m)
        self.m = m
        self.offset = 0
        self.size = size

    def _c(self, s):
        return ord(s) - ord("a") + 1

    def rotate(self):
        """右方向に1字ずらす"""
        if self.size <= 0:
            raise ValueError("No data left.")
        self.rh *= self.b
        self.rh %= self.m
        self.rh -= self._c(self.S[self.offset]) * self.bn
        self.rh %= self.m
        self.rh += self._c(self.S[(self.offset + self.size) % len(self.S)])
        self.rh %= self.m
        self.offset += 1
        self.offset %= len(self.S)
        return self

    def contract(self):
        """右端を1字削る"""
        if self.size <= 0:
            raise ValueError("No data left.")
        self.rh = self.rh_head
        self.rh -= self._c(self.S[self.size-1])
        self.rh %= self.m
        self.rh *= self.binv
        self.rh %= self.m
        self.offset = 0
        self.size -= 1
        self.bn = pow(self.b, self.size, self.m)
        self.rh_head = self.rh
        return self

    def get_hash(self):
        if self.size <= 0:
            raise ValueError("No data left.")
        return self.rh
    
    def __len__(self):
        return self.size

    def __eq__(self, other):
        return self.size == other.size and self.rh == other.rh


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    rh = RollingHash(S)
    ans = 0
    for n in range(N, N//2, -1):
        rh.contract()
    for n in range(N//2, 0, -1):
        hdict = defaultdict(list)
        for i in range(0, N - n + 1):
            # list all S[i:i+n]
            h = rh.get_hash()
            hdict[h].append(i)
            rh.rotate()
        for h in hdict.keys():
            if hdict[h][-1] - hdict[h][0] >= n:
                ans = max(ans, n)
        rh.contract()
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=10**9+7):
        rh = 0
        for s in S:
            rh *= b
            rh %= m
            c = self._c(s)
            rh += c
            rh %= m
        size = len(S)
        self.S = S
        self.rh = rh
        self.rh_head = rh
        self.b = b
        self.bn = pow(b, size, m)
        self.binv = pow(b, m-2, m)
        self.m = m
        self.offset = 0
        self.size = size

    def _c(self, s):
        return ord(s) - ord("a") + 1

    def rotate(self):
        """右方向に1字ずらす"""
        if self.size <= 0:
            raise ValueError("No data left.")
        self.rh *= self.b
        self.rh %= self.m
        self.rh -= self._c(self.S[self.offset]) * self.bn
        self.rh %= self.m
        self.rh += self._c(self.S[(self.offset + self.size) % len(self.S)])
        self.rh %= self.m
        self.offset += 1
        self.offset %= len(self.S)
        return self

    def contract(self):
        """右端を1字削る"""
        if self.size <= 0:
            raise ValueError("No data left.")
        self.rh = self.rh_head
        self.rh -= self._c(self.S[self.size-1])
        self.rh %= self.m
        self.rh *= self.binv
        self.rh %= self.m
        self.offset = 0
        self.size -= 1
        self.bn = pow(self.b, self.size, self.m)
        self.rh_head = self.rh
        return self

    def get_hash(self):
        if self.size <= 0:
            raise ValueError("No data left.")
        return self.rh
    
    def __len__(self):
        return self.size

    def __eq__(self, other):
        return self.size == other.size and self.rh == other.rh


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    rh = RollingHash(S)
    ans = 0
    for n in range(N, N//2, -1):
        rh.contract()
    for n in range(N//2, 0, -1):
        hdict = defaultdict(list)
        for i in range(0, N - n + 1):
            # list all S[i:i+n]
            h = rh.get_hash()
            hdict[h].append(i)
            rh.rotate()
        for h in hdict.keys():
            if hdict[h][-1] - hdict[h][0] > ans:
                ans = max(ans, n)
        rh.contract()
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
from random import randint


class RollingHash(object):
    mod = 1 << 61 - 1
    base = randint(2, mod - 2)

    def __init__(self, s):
        """
        sに関するローリングハッシュを構築する O(|s|)
        """
        self.s = s
        self.pw = pw = [1] * (len(s) + 1)

        l = len(s)
        self.h = h = [0] * (l + 1)

        v = 0
        for i in range(l):
            h[i + 1] = v = (v * self.base + ord(s[i])) % self.mod
        v = 1
        for i in range(l):
            pw[i + 1] = v = v * self.base % self.mod

    def hash(self, l, r):
        """ s[l:r] のhash (rはexclusive) O(1) """
        return (self.h[r] - self.h[l] * self.pw[r - l]) % self.mod

    def contains(self, t):
        """
        sがtを含むか O(|s|-|t|)
        tはRollingHashオブジェクト
        """
        slen, tlen = len(self.s), len(t.s)
        if slen < tlen:
            return False
        th = t.hash(0, tlen)
        for i in range(slen - tlen + 1):
            if th == self.hash(i, i + tlen):
                return True
        return False

    def count(self, t):
        """
        s中に含まれるtの数をカウントする O(|s|-|t|)
        tはRollingHashオブジェクト
        """
        slen, tlen = len(self.s), len(t.s)
        if slen < tlen:
            return 0
        cnt = 0
        th = t.hash(0, tlen)
        for i in range(slen - tlen + 1):
            if th == self.hash(i, i + tlen):
                cnt += 1
        return cnt

    def getLCP(self, a, b):
        l = min(len(self.s) + 1 - a, len(self.s) + 1 - b)
        low, high = 0, l
        while high - low > 1:
            mid = (low + high) >> 1
            if self.hash(a, a + mid) != self.hash(b, b + mid):
                high = mid
            else:
                low = mid
        return low


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

rh = RollingHash(S)
ans = 0
# for i in range(N):
#     for j in range(i + 1, N):
#         lcp = rh.getLCP(i, j)
#         lcp = min(lcp, j - i)
#         ans = max(ans, lcp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
m = n//2
for i in range(m,0,-1):
	a = []
	c = 0
	for j in range(n-i+1):
		#print (s[j:j+i],i,j)
		c += 1
		a.append(s[j:j+i])
	if c != len(set(a)):
		print (i)
		exit()
print(0)

Submission status: Wrong Answer

Solution code:
import math

def main():
    n = int(input())
    s = input()
    ans = solve(n, s)
    print(ans)


def solve(n, s):
    ans = 0
    for i in range(n - 1):
        tmp = Z(s[i:])
        tmp = tmp[math.ceil(len(tmp) / 2):]
        if len(tmp):
            ans = max(ans, max(tmp))
        #print(tmp)
    return ans

def Z(s):
    l = len(s)
    ans = [l for _ in range(l)]

    i, j = 1, 0
    while i < l:
        while i + j < l and s[j] == s[i + j] :
            j += 1
        ans[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ans[k] < j:
            ans[i + k] = ans[k]
            k += 1
        i += k
        j -= k
    return ans

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit
# getarr = lambda _f: list(map(_f, input().split()))

n = int(input())
s = input()

s += '_'

ans = 0
for i in range(1, n):
    tmp = 0
    print(s, s[i:])
    for j in range(i, n + 1):
        if s[j - i] == s[j]:
            tmp += 1
            if tmp >= i:
                ans = i
                break
        else:
            ans = max(ans, tmp)
            tmp = 0

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S, rand=True, num=1)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        import random
        import math
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S, rand=True, num=1)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        import random
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S, num=2)

    def f(m):
        if m == 0:
            return 1

        h2i = defaultdict(list)
        for i in range(N-m):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    b = Bisect(f)
    return b.bisect_right(0, 0, N//2)


def main():
    N = int(input())
    S = input()
    print(slv(N, S))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
j = 1
y = s[1:]
x = s[0]
result = [0]
end = n//2 + 1
for i in range(n):
    while (j < n-1) and (s[i:j] in s[:i]+s[j:]):
        j += 1
    result.append(j-i-1)
print(max(result))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
j = 1
y = s[1:]
x = s[0]
result = [0]
for i in range(n):
    while (j < n//2 + 1) and (x in y):
        x = x+s[j]
        y = s[:i]+s[j+1:]
        j += 1
    result.append(j-i-1)
    y = s[:i+1] + s[j+1:]
    x = x[1:]
print(max(result))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
j = 1
y = s[1:]
x = s[0]
result = [0]
for i in range(n):
    while (j < n) and (x in y):
        x = x+s[j]
        y = s[:i]+s[j+1:]
        j += 1
    result.append(j-i-1)
    y = s[:i+1] + s[j+1:]
    x = x[1:]
print(max(result))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
j = 1
y = s[1:]
x = s[0]
result = [0]
for i in range(n):
    while (j < n) and (x in y):
        x = x+s[j]
        y = s[:i]+s[j+1:]
        j += 1
    result.append(j-i-1)
    y = s[:i+1] + s[j+1:]
    x = s[i+1:j]
print(max(result))

Submission status: Wrong Answer

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


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = 0
    l0 = 0
    r0 = 1
    cache = [0 for i in range(N)]
    while l0 < N:
        for l1 in range(l0+1, N):
            # find and compare
            if S[l0] == S[l1]:
                if cache[l1] > 0:
                    k = cache[l1]
                    cache[l1] = 0
                else:
                    k = 1
                while l0 + k < l1 and l1+k < N and S[l0+k] == S[l1+k]:
                    k += 1
                ans = max(ans, k)
                # [l0, l0+k] と [l1, l1+k] が一致したという情報を保持しておく
                # l0を増やしたときに参照し、無駄なマッチングを省く
                if l1 + 1 < N:
                    cache[l1+1] = k-1
                l1 += k
        l0 += 1
    return ans

if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

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


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = 0
    l0 = 0
    r0 = 1
    cache = [0 for i in range(N)]
    while l0 < N:
        for l1 in range(l0+1, N):
            # find and compare
            if S[l0] == S[l1]:
                if cache[l1] > 0:
                    k = cache[l1]
                else:
                    k = 1
                while l0 + k < l1 and l1+k < N and S[l0+k] == S[l1+k]:
                    k += 1
                ans = max(ans, k)
                # [l0, l0+k] と [l1, l1+k] が一致したという情報を保持しておく
                # l0を増やしたときに参照し、無駄なマッチングを省く
                if l1 + 1 < N:
                    cache[l1+1] = k-1
                l1 += k
        l0 += 1
    return ans

if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
# 左の文字を決め打ちして、右の文字を試していく 右の文字の候補の位置はあらかじめdicで記録

from collections import defaultdict
pos = defaultdict(list)

import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

for i in range(N):
  pos[S[i]].append(i)

import bisect
def find_tar(s,i): # i + 1文字目以降からsを探す
#  print("pos[s]",pos[s],"から",i+1,"番目以降の最小値を探す")
  j = bisect.bisect_left(pos[s],i+1)
  if j == len(pos[s]):
    return None
  return pos[s][j:] # 全リストを返す

ans = 0
i = 0
while i < N:
  rest = find_tar(S[i],i)
  if rest is None:
    i += 1
    continue
  bestfit = 1
  #print(S[i],rest)
  for j in rest:
    # i,jに同じ文字がある状態
    fit = 1
    #print("i",i,S[i],"j",j,S[j],"からスタート")
    while i + fit < j and j + fit < N:
      if S[i + fit] == S[j + fit]:
        #print("fit",fit,"一致",S[i + fit])
        fit += 1
      else:
        break
    if bestfit < fit:
      bestfit = fit
    if bestfit > ans:
      ans = bestfit
  i += bestfit

print(ans)

Submission status: Wrong Answer

Solution code:
# 左の文字を決め打ちして、右の文字を試していく 右の文字の候補の位置はあらかじめdicで記録

from collections import defaultdict
pos = defaultdict(list)

import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

for i in range(N):
  pos[S[i]].append(i)

import bisect
def find_tar(s,i): # i + 1文字目以降からsを探す
#  print("pos[s]",pos[s],"から",i+1,"番目以降の最小値を探す")
  j = bisect.bisect_left(pos[s],i+1)
  if j == len(pos[s]):
    return -1
  return pos[s][j]

ans = 0
i = 0
while i < N:
  j = find_tar(S[i],i)
  if j == -1:
    i += 1
    continue
  # i,jに同じ文字がある状態
  fit = 1
#  print("i",i,S[i],"j",j,S[j],"からスタート")
  while i + fit < j and j + fit < N:
    if S[i + fit] == S[j + fit]:
#      print("fit",fit,"一致",S[i + fit])
      fit += 1
    else:
#      print("fit",fit,"一致しない",S[i + fit],S[j + fit])
      i = i + fit
      break
  else:
    i += 1
  if fit > ans:
    ans = fit

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

ans=0
i=0
j=i+1
cnt=0
j_start=None    #jの文字列一致のスタート位置
while i<N-1 and j<N:
    s=S[i]
    t=S[j]
    if s==t:    #文字が一致していれば
        if j_start is None: j_start=j #スタート位置を記録
        cnt+=1
        if i<j_start-1 and j<N-1: #文字をはみ出さないなら
            i+=1    #チェックする文字を1文字ずつ右にスライド
            j+=1    #チェックする文字を1文字ずつ右にスライド
        else:   #iかjが文字列をはみ出すようであれば
            ans=max(ans,cnt)
            cnt=0   #文字列一致数を0にリセット
            i+=1    #iを1進める
            j=i+1   #jはiと重ならないように1進める
            j_start=None    #jのスタート位置をリセット
    else:    #文字が一致しなくなったら
        ans=max(ans,cnt)
        cnt=0   #文字列一致数を0にリセット
        j_start=None    #jのスタート位置をリセット
        if j<N-1: #jが右端まで行きついていない場合は、jのみ進める
            j+=1   #jを1進める
        else: #jが右端まで行きついた場合は、iを1つ進め、jを1つ先にセットする
            i+=1    #iを1進める
            j=i+1   #jはiと重ならないように1進める

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

ans=0
i=0
j=i+1
cnt=0
j_start=None    #jの文字列一致のスタート位置
while i<N-1 and j<N:
    s=S[i]
    t=S[j]
    if s==t:    #文字が一致していれば
        if j_start is None: j_start=j #スタート位置を記録
        cnt+=1
        if i<j_start and j<N-1: #文字をはみ出さないなら
            i+=1    #チェックする文字を1文字ずつ右にスライド
            j+=1    #チェックする文字を1文字ずつ右にスライド
        else:   #iかjが文字列をはみ出すようであれば
            ans=max(ans,cnt)
            cnt=0   #文字列一致数を0にリセット
            i+=1    #iを1進める
            j=i+1   #jはiと重ならないように1進める
            j_start=None    #jのスタート位置をリセット
    else:    #文字が一致しなくなったら
        ans=max(ans,cnt)
        cnt=0   #文字列一致数を0にリセット
        j_start=None    #jのスタート位置をリセット
        if j<N-1: #jが右端まで行きついていない場合は、jのみ進める
            j+=1   #jを1進める
        else: #jが右端まで行きついた場合は、iを1つ進め、jを1つ先にセットする
            i+=1    #iを1進める
            j=i+1   #jはiと重ならないように1進める

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

ans=0
i=0
j=i+1
cnt=0
j_start=None    #jの文字列一致のスタート位置
while i<N and j<N:
    s=S[i]
    t=S[j]
    if s==t:    #文字が一致していれば
        if j_start is None: j_start=j #スタート位置を記録
        cnt+=1
        if i<j_start-1 and j<N-1: #文字をはみ出さないなら
            i+=1    #チェックする文字を1文字ずつ右にスライド
            j+=1    #チェックする文字を1文字ずつ右にスライド
        else:   #iかjが文字列をはみ出すようであれば
            ans=max(ans,cnt)
            cnt=0   #文字列一致数を0にリセット
            i+=1    #iを1進める
            j=i+1   #jはiと重ならないように1進める
            j_start=None    #jのスタート位置をリセット
    else:    #文字が一致しなくなったら
        ans=max(ans,cnt)
        cnt=0   #文字列一致数を0にリセット
        j_start=None    #jのスタート位置をリセット
        if j<N-1: #jが右端まで行きついていない場合は、jのみ進める
            j+=1   #jを1進める
        else: #jが右端まで行きついた場合は、iを1つ進め、jを1つ先にセットする
            i+=1    #iを1進める
            j=i+1   #jはiと重ならないように1進める

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

ans=0
i=0
j=i+1
cnt=0
j_start=None    #jの文字列一致のスタート位置
while i<N and j<N:
    s=S[i]
    t=S[j]
    if s==t:    #文字が一致していれば
        if j_start is None: j_start=j #スタート位置を記録
        cnt+=1
        if i<j_start-1 and j<N-1: #文字をはみ出さないなら
            i+=1    #チェックする文字を1文字ずつ右にスライド
            j+=1    #チェックする文字を1文字ずつ右にスライド
        else:   #iかjが文字列をはみ出すようであれば
            ans=max(ans,cnt)
            cnt=0   #文字列一致数を0にリセット
            i+=1    #iを1進める
            j=i+1   #jはiと重ならないように1進める
            j_start=None    #jのスタート位置をリセット
    else:    #文字が一致しなくなったら
        ans=max(ans,cnt)
        cnt=0   #文字列一致数を0にリセット
        if j<N-1: #jが右端まで行きついていない場合は、jのみ進める
            j+=1   #jを1進める
        else: #jが右端まで行きついた場合は、iを1つ進め、jを1つ先にセットする
            i+=1    #iを1進める
            j=i+1   #jはiと重ならないように1進める

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()
ans=0   #文字列一致が存在しない場合は0を返す

visited=set()
for i in range(N):
    s=S[i]
    if s in visited: continue #一度調べた文字はスキップ
    visited.add(s)
    for j in range(i+1,N):
        while j<N:  #jが文字列からはみ出さない間はループを回す
            t=S[j]
            if s==t:    #文字が一致したら、jを1つ進める
                current_j=j     #文字が一致したら現在のjの位置を記録しておく
                cnt=0
                while s==t:
                    cnt+=1
                    i+=1    #チェックする文字を1文字ずつ右にスライド
                    j+=1    #チェックする文字を1文字ずつ右にスライド
                    if i==current_j:    #iがjのスタート位置と重なったらbreak
                        break
                    elif i<N and j<N:    #i,jともに文字列内だったら
                        s=S[i]
                        t=S[j]
                    else:    #i or jが文字列の右側からはみ出したら
                        break
                ans=max(ans,cnt)
                j=current_j+1 #元のjの値を戻して、1つ進める
            else:    #文字が一致しなかったら、jを1つ進める
                j+=1

print ans

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def Z_algo(S):
    n = len(S)
    LCP = [0] * n
    c = 0  # 最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        # i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i + LCP[i - c] < c + LCP[c]:
            LCP[i] = LCP[i - c]
        else:
            j = max(0, c + LCP[c] - i)
            while i + j < n and S[j] == S[i + j]:
                j += 1
            LCP[i] = j
            c = i
    return LCP


n = int(readline()) // 2
s = read().rstrip().decode()
ans = 0
for i in range(n):
    m = Z_algo(s[i:])[n:]
    max_m = max(m)
    if max_m > n:
        max_m = max(m[1:])
    ans = max(ans, max_m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def Z_algo(S):
    n = len(S)
    LCP = [0] * n
    c = 0  # 最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        # i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i + LCP[i - c] < c + LCP[c]:
            LCP[i] = LCP[i - c]
        else:
            j = max(0, c + LCP[c] - i)
            while i + j < n and S[j] == S[i + j]:
                j += 1
            LCP[i] = j
            c = i
    return LCP


n = int(readline()) // 2
s = read().rstrip().decode()
ans = 0
for i in range(n):
    m = (Z_algo(s[i:]) + [0])[n - i:]
    max_m = max(m)
    if max_m > n:
        max_m = max(m[1:])
    ans = max(ans, max_m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def Z_algo(S):
    n = len(S)
    LCP = [0] * n
    c = 0  # 最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        # i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i + LCP[i - c] < c + LCP[c]:
            LCP[i] = LCP[i - c]
        else:
            j = max(0, c + LCP[c] - i)
            while i + j < n and S[j] == S[i + j]:
                j += 1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP


n = int(readline())
s = readline().rstrip().decode()
ans = 0
for i in range(n):
    m = Z_algo(s[i:])[1:] + [0]
    ans = max(ans, max(m[n // 2 - i:]))
print(ans)