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
sys.setrecursionlimit(10**9)


class RollingHash:

    def __init__(self,string):
        base1 = 1007
        mod1 = 10**9+7

        base2 = 2009
        mod2 = 10**9+9

        self.string = string
        n = len(string)
        hash1 = [0]*(n+1)
        power1 = [1]*(n+1)

        hash2 = [0]*(n+1)
        power2 = [1]*(n+1)
        for i,e in enumerate(string):
            hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
            power1[i+1] = (power1[i]*base1)%mod1
            hash2[i+1] = (hash2[i]*base2 + ord(e))%mod2
            power2[i+1] = (power2[i]*base2)%mod2

        self.hash1 = hash1
        self.power1 = power1
        self.hash2 = hash2
        self.power2 = power2
        self.base1 = base1
        self.mod1 = mod1
        self.base2 = base2
        self.mod2 = mod2

    def calc(self,i,j):
        ans = ((self.hash1[j]-self.hash1[i]*self.power1[j-i]%self.mod1)%self.mod1)*(10**10)
        ans += (self.hash2[j]-self.hash2[i]*self.power2[j-i]%self.mod2)%self.mod2
        return ans

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

    rh = RollingHash(S)


    ans = 0
    l = 0
    r = N

    def is_ok(p,newp):
        if not p[1] < newp[0]: return False
        return S[p[0]:p[1]+1] == S[newp[0]:newp[1]+1]


    while r-l > 1:
        mid = (l+r)//2
        seen = set()
        dic = {}
        found = False
        for i in range(N-mid+1):
            if not i < i+mid-1: continue

            hash = rh.calc(i,i+mid-1)
            # print(hash,i,i+mid-1,mid)
            if hash in seen and is_ok(dic[hash],(i,i+mid-1)):
                # print(dic[hash],i,S[i:i+mid])
                ans = max(ans,mid)
                found = True
                break
            seen.add(hash)
            dic[hash] = (i,i+mid-1)

        if found:
            l = mid
        else:
            r = mid

    print(ans)



if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)


class RollingHash:

    def __init__(self,string):
        base1 = 1007
        mod1 = 10**9+7

        base2 = 2009
        mod2 = 10**9+9

        self.string = string
        n = len(string)
        hash1 = [0]*(n+1)
        power1 = [1]*(n+1)

        hash2 = [0]*(n+1)
        power2 = [1]*(n+1)
        for i,e in enumerate(string):
            hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
            power1[i+1] = (power1[i]*base1)%mod1
            hash2[i+1] = (hash2[i]*base2 + ord(e))%mod2
            power2[i+1] = (power2[i]*base2)%mod2

        self.hash1 = hash1
        self.power1 = power1
        self.hash2 = hash2
        self.power2 = power2
        self.base1 = base1
        self.mod1 = mod1
        self.base2 = base2
        self.mod2 = mod2

    def calc(self,i,j):
        ans = ((self.hash1[j]-self.hash1[i]*self.power1[j-i]%self.mod1)%self.mod1)*(10**10)
        ans += (self.hash2[j]-self.hash2[i]*self.power2[j-i]%self.mod2)%self.mod2
        return ans

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

    rh = RollingHash(S)


    ans = 0
    l = 0
    r = N

    while r-l > 1:
        mid = (l+r)//2
        seen = set()
        dic = {}
        found = False
        for i in range(N-mid+1):
            if not i < i+mid-1: continue

            hash = rh.calc(i,i+mid-1)
            # print(hash,i,i+mid-1,mid)
            if hash in seen and dic[hash] < i:
                ans = max(ans,mid)
                found = True
                break
            seen.add(hash)
            dic[hash] = i+mid-1

        if found:
            l = mid
        else:
            r = mid

    print(ans)



if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
s = input()
for i in range(n):
    string = z_algo(s[i:])
    for j in range(1,len(string)):
        if j - i  + string[j] < n:
            ans = max(ans, string[j])
print(ans)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = input()
    ma = 0
    for i in range(n):
        pf = z_algorithm(s[i::])
        if pf > ma:
            ma = pf
    print(ma)

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def Z_algo(S):
    N = len(S)
    result = 0
    c = 0
    Z = [0]*N
    for i in range(1, N):
        l = i - c
        if (i + Z[l] < c + Z[c]):
            Z[i] = Z[l]
        else:
            j = max(0, c + Z[c] - i)
            if i + j >= N:
                j = min(j, N-i-1)
            else:
                while(S[j] == S[i + j]):
                    j += 1
                    if i + j >= N:
                        break
            Z[i] = j
            c = i
        result = max(result, min(Z[i], i))
    return result

L = int(input())
P = list(input())
ans = 0

for k in range(L):
    ans = max(ans, Z_algo(P[k:]))

print(ans)

Submission status: Wrong Answer

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

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

  
ans = 0
for i in range(N):
  for j in range(N):
    l = N - j
    if i + l <= j:
      ans = max(ans, dp[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())
S = list(input())
dp = [[0]*(N) for _ in range(N)]
for i in range(N):
  if S[-1] == S[i]:
    dp[-1][i] = 1
    dp[i][-1] = 1
  
for i in range(N-2, -1, -1):
  for j in range(N-2, -1, -1):
    if S[i] == S[j]:
      dp[i][j] = dp[i+1][j+1] + 1
    else:
      dp[i][j] = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])
  
ans = 0
for i in range(N):
  for j in range(N):
    l = N - j
    if i + l <= j:
      ans = max(ans, dp[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:

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

for i in range(N-2, -1, -1):
  for j in range(N-2, -1, -1):
    if S[i] == S[j]:
      dp[i][j] = dp[i+1][j+1] + 1
    else:
      dp[i][j] = min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])
  
ans = 0
for i in range(N):
  for j in range(N):
    l = N - j
    if i + l <= j:
      ans = max(ans, dp[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n,s = int(raw_input()), raw_input()

def f(k, s):	
 	cc,q = collections.Counter(), collections.deque()
	for j in range(k - 1, len(s)):
		q.append(s[j - k + 1:j+1])
		if len(q) == k + 1: cc[q.popleft()] += 1
		if q[-1] in cc: return True	
	return False

lo,hi = 0, n/2
while(lo < hi):
	med = (lo + hi + 1) / 2
	if f(med, s):  lo = med
	else:hi = med - 1

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
m = [0] * n
ans = 0
for i in range(n - 1, -1, -1):
    k = 0
    for j in range(i):
        if i + k >= n:
            break
        if s[i + k] == s[j]:
            k += 1
        else:
            k = 0
        m[i] = max(m[i], k)
    ans = max(ans, m[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    d = defaultdict(int)
    q = deque([])
    
    for i in range(x):
        q.append(S[i])
        
    d[''.join(q)] = 0
    
    for i in range(x, N):
        q.append(S[i])
        q.popleft()
        k = ''.join(q)
        
        if k in d and i-x+1-d[k]>=x:
            return True
        
        d[k] = i-x+1
    
    return False

def binary_search():
    l, r = 0, N
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            l = m+1
        else:
            r = m-1
    
    return r

N = int(input())
S = input()[:-1]
print(binary_search())

Submission status: Wrong Answer

Solution code:
import collections

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

c = collections.Counter()

ans = 0

base = 37
mod = 10 ** 9 + 9
pw = None


def rolling_hash(s):
    l = len(s)
    h = [0] * (l + 1)
    v = 0
    for i in range(l):
        v = (v * base + ord(s[i])) % mod
        h[i + 1] = v
    return h


def setup_pw(l):
    global pw
    pw = [1] * (l + 1)
    v = 1
    for i in range(l):
        v = v * base % mod
        pw[i + 1] = v


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


HS = rolling_hash(S)
setup_pw(len(S))

for i in range(1, N + 1):
    for j in range(i, N + 1):
        c[get(HS, i, j)] += 1
        if c[get(HS, i, j)] == 2:
            ans = max(ans, j - i)


print(ans)

Submission status: Wrong Answer

Solution code:
import collections

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

c = collections.Counter()

for i in range(N):
    for j in range(i + 1, i + 1 + (N // 2)):
        c[S[i:j]] += 1

ans = 0

for k in c.keys():
    if c[k] >= 2:
        ans = max(ans, len(k))

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    s=readline().strip()

    ans=0
    for i in range(n):
        tmp=z_algorithm(s[i:])
        tmp[0]=0
        res=[0]*i
        res.extend(tmp)
        for j in range(n):
            ans=max(ans,min(res[j],j))

    print(ans)

def z_algorithm(s):
    n=len(s)
    z=[0]*n
    z[0]=n
    i=1
    j=0

    while i<n:
        while i+j<n and s[j]==s[i+j]:
            j+=1
        z[i]=j
        if j==0:
            i+=1
            continue
        k=1
        while i+k<n and k+z[k]<j:
            z[i+k]=z[k]
            k+=1
        i+=k
        j-=k
    return z

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
S = rs()

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
def zalgo(s):
  n = len(s)
  lcp = [0]*n
  lcp[0] = n
  i = 1
  j = 0
  while i < n:
    while i+j < n and s[j] == s[i+j]:
      j += 1
    lcp[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while k < j and lcp[k] < j:
      lcp[i+k] = lcp[k]
      k += 1
    i += k
    j -= k
  return lcp
ans = 0
for i in range(n):
  ss = s[i:]
  lcp = zalgo(ss)
  ans = max([ans]+[min(lcp[j],j) for j in range(n-i)])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
    st = s[:tgt]
    if st in dic.keys():
        return True
    for char in s[tgt:N-tgt]:
        st = st[1:]+char
        if st in dic.keys():
            return True
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import random
from collections import defaultdict


# CPythonの文字列検索アルゴリズム (BM法) を利用
# http://effbot.org/zone/stringlib.htm


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


def solve(N, S):
    low = 0
    high = len(S) // 2 + 1
    while high - low > 1:
        mid = (high + low) // 2
        is_match = False
        for i in range(0, N-2*mid):
            if S[i:i+mid] in S[i+mid:]:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


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=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


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


def solve(N, S):
    m = 10**9+7
    b = random.randint(10000, m-1)
    rh = RollingHash(S, b=b, m=m)
    low = 0
    high = (N+1) // 2 + 1
    dmax = defaultdict(int)
    dmin = defaultdict(int)
    while high - low > 1:
        dmax.clear()
        dmin.clear()
        mid = (high + low) // 2
        for i in range(0, N-mid+1):
            h = rh.get(i, i+mid)
            dmax[h] = max(dmax[h], i+1)
            dmin[h] = max(dmin[h], N+1-i)
        is_match = False
        for h in dmax.keys():
            if dmax[h] - (N+2 - dmin[h]) >= mid:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


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=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


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


def solve(N, S):
    m = 999999937
    b = random.randint(10000, m-1)
    rh = RollingHash(S, b=b, m=m)
    low = 0
    high = (N+1) // 2 + 1
    dmax = defaultdict(int)
    dmin = defaultdict(int)
    while high - low > 1:
        dmax.clear()
        dmin.clear()
        mid = (high + low) // 2
        for i in range(0, N-mid+1):
            h = rh.get(i, i+mid)
            dmax[h] = max(dmax[h], i+1)
            dmin[h] = max(dmin[h], N+1-i)
        is_match = False
        for h in dmax.keys():
            if dmax[h] - (N+2 - dmin[h]) >= mid:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


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

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
d = dict()
words = []
length = 0
word = ''
for i in range(N):
    s = S[i]
    d[s] = d.get(s, 0) + 1
    if d[s] >= 2:
        length += 1
        word = word + s
        words.append(word)
    else:
        length = 0
        word = ''
words.sort(key=lambda a: -len(a))

length = 0
for w in words:
    c = S.count(w)
    if c >= 2:
        length = len(w)
        break
print(length)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
d = dict()
words = []
length = 0
word = ''
for i in range(N):
    s = S[i]
    d[s] = d.get(s, 0) + 1
    if d[s] >= 2:
        length += 1
        word = word + s
        words.append(word)
    else:
        length = 0
        words.append(word)
        word = ''
words.sort(key=lambda a: -len(a))

length = 0
for w in words:
    i = S.find(w)
    j = S.find(w, i + len(w))
    if j > -1:
        length = len(w)
        break
    if not w:
        break
print(length)

Submission status: Wrong Answer

Solution code:
import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        rh = 0
        rh_head = []
        for s in S:
            rh *= b
            rh %= m
            c = self._c(s)
            rh += c
            rh %= m
            rh_head.append(rh)
        size = len(S)
        self.S = S
        self.rh = rh
        self.rh_head = rh_head
        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.rh * self.b - self._c(self.S[self.offset]) * self.bn + \
            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 set_window(self, n):
        """n文字のハッシュに切り替える"""
        if self.size <= 0:
            raise ValueError("No data left.")
        self.rh = self.rh_head[n-1]
        self.offset = 0
        self.size = n
        self.bn = pow(self.b, self.size, self.m)
        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)
    hdict = defaultdict(list)
    for n in range(N//2, 0, -1):
        rh.set_window(n)
        hdict.clear()
        for i in range(0, N - n + 1):
            if i > 0:
                rh.rotate()
            # list all S[i:i+n]
            h = rh.get_hash()
            hdict[h].append(i)
        for h in hdict.keys():
            if hdict[h][-1] - hdict[h][0] >= n:
                return n
    return 0


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
        rh_head = []
        for s in S:
            rh *= b
            rh %= m
            c = self._c(s)
            rh += c
            rh %= m
            rh_head.append(rh)
        size = len(S)
        self.S = S
        self.rh = rh
        self.rh_head = rh_head
        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.rh * self.b - self._c(self.S[self.offset]) * self.bn + \
            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 set_window(self, n):
        """n文字のハッシュに切り替える"""
        if self.size <= 0:
            raise ValueError("No data left.")
        self.rh = self.rh_head[n-1]
        self.offset = 0
        self.size = n
        self.bn = pow(self.b, self.size, self.m)
        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
    hdict = defaultdict(list)
    for n in range(N//2, 0, -1):
        rh.set_window(n)
        hdict.clear()
        for i in range(0, N - n + 1):
            if i > 0:
                rh.rotate()
            # list all S[i:i+n]
            h = rh.get_hash()
            hdict[h].append(i)
        for h in hdict.keys():
            if hdict[h][-1] - hdict[h][0] >= n:
                ans = max(ans, n)
    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
    hmin = defaultdict(int)
    hmax = defaultdict(int)
    for n in range(N, N//2, -1):
        rh.contract()
    for n in range(N//2, 0, -1):
        hmin.clear()
        hmax.clear()
        for i in range(0, N - n + 1):
            # list all S[i:i+n]
            h = rh.get_hash()
            hmin[h] = max(hmin[h], N-i)
            hmax[h] = max(hmax[h], i+1)
            rh.rotate()
        for h in hmax.keys():
            if hmax[h] - (N-hmin[h]) >= 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
    hmin = defaultdict(int)
    hmax = defaultdict(int)
    for n in range(N, N//2, -1):
        rh.contract()
    for n in range(N//2, 0, -1):
        hmin.clear()
        hmax.clear()
        for i in range(0, N - n + 1):
            # list all S[i:i+n]
            h = rh.get_hash()
            hmin[h] = min(hmin[h], i+1)
            hmax[h] = max(hmax[h], i+1)
            rh.rotate()
        for h in hmax.keys():
            if hmax[h] - hmin[h] >= 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))