Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Wrong Answer

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

def z_algorythm(s):
    n = len(s)
    LCP = [0]*n
    c = 0
    for i in range(1, n):
        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

ans = 0
for i in range(n):
    LCP = z_algorythm(s[i:])
    for j, l in enumerate(LCP):
        if j >= l:
            ans = max(ans, l)
print(ans)

Submission status: Wrong Answer

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

def z_algorythm(s):
    n = len(s)
    LCP = [0]*n
    c = 0
    for i in range(1, n):
        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

ans = 0
for i in range(n):
    LCP = z_algorythm(s[i:])
    for j, l in enumerate(LCP):
        tmp = min(j, l)
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
left = 0
right = n // 2 + 1
while right - left > 1:
    mid = (right + left) // 2
    len = mid
    for i in range(n):
        if i + len >= n - len:
            continue
        s1 = s[i:i+len]
        s2 = s[i+len:]
        if s1 in s2:
            left = mid
            break
    else:
        right = mid
print(left)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic  = defaultdict(int)
N = int(input())
S = input()
ans = 0

for i in range(N):
    for j in range(i, (N+i)//2):
        if dic[S[i:j+1]]!=0:
            continue
        dic[S[i:j+1]]+=1
print(dic)
for i in range(1, N):
    k = min(N, 2*i)
    for j in range(i, k):
        if dic[S[i:j+1]]==1:
            dic[S[i:j+1]]=2
            ans = max(ans, len(S[i:j+1]))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic  = defaultdict(int)
N = int(input())
S = input()
ans = 0
l = []
for i in range(N):
    for j in range(i, (N+i)//2):
        s = S[i:j+1]
        if dic[s]!=0:
            continue
        dic[s]+=1

for i in range(1, N):
    k = min(N, 2*i)
    for j in range(i, k):
        s = S[i:j+1]
        if dic[s]==1:
            dic[s]=2
            l.append(s)
            ans = max(ans, len(s))

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
  def __init__(self,s,base=37,mod=10**9+7):
    self.mod=mod
    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*base+ord(s[i]))%mod
    v=1
    for i in range(l):
      pw[i+1]=v=v*base%mod
  def get(self, l, r):
    return (self.h[r]-self.h[l]*self.pw[r-l])%self.mod
def isok(l):
  for i in range(n-l*2+1):
    for j in range(i+l,n-l+1):
      if rh.get(i,i+l)==rh.get(j,j+l):return 1
  return 0
def b_search():
  ng=n+1
  ok=0
  while abs(ng-ok)>1:
    mid=(ng+ok)//2
    if isok(mid):ok=mid
    else:ng=mid
  return ok
n=int(input())
s=input()
rh=RollingHash(s)
print(b_search())

Submission status: Wrong Answer

Solution code:
class RollingHash():
  def __init__(self,s,base=37,mod=10**9+7):
    self.mod=mod
    self.pw=pw=[1]*(len(s)+1)
    self.n=n=len(s)
    self.h=h=[0]*(n+1)
    v=0
    for i in range(n):
      h[i+1]=v=(v*base+ord(s[i]))%mod
    v=1
    for i in range(n):
      pw[i+1]=v=v*base%mod
  def get(self,l=0,r=-1):
    if r==-1:r=self.n
    return (self.h[r]-self.h[l]*self.pw[r-l])%self.mod

def isok(index):
  for i in range(n-index*2+1):
    for j in range(i+index+1,n-index+1):
      if rh.get(i,i+index)==rh.get(j,j+index):return 1
  return 0
def b_search():
  ng=n+1
  ok=0
  while abs(ng-ok)>1:
    mid=(ng+ok)//2
    if isok(mid):ok=mid
    else:ng=mid
  return ok
n=int(input())
s=input()
rh=RollingHash(s)
print(b_search())

Submission status: Wrong Answer

Solution code:
class RollingHash():
  def __init__(self,s,base=37,mod=10**9+7):
    self.mod=mod
    self.pw=pw=[1]*(len(s)+1)
    self.n=n=len(s)
    self.h=h=[0]*(n+1)
    v=0
    for i in range(n):
      h[i+1]=v=(v*base+ord(s[i]))%mod
    v=1
    for i in range(n):
      pw[i+1]=v=v*base%mod
  def get(self,l=0,r=-1):
    if r==-1:r=self.n
    return (self.h[r]-self.h[l]*self.pw[r-l])%self.mod

def isok(index):
  for i in range(n-index*2+1):
    for j in range(i+index+1,n-index+1):
      if rh.get(i,i+index)==rh.get(j,j+index):return 1
  return 0
def b_search():
  ng=n
  ok=0
  while abs(ng-ok)>1:
    mid=(ng+ok)//2
    if isok(mid):ok=mid
    else:ng=mid
  return ok
n=int(input())
s=input()
rh=RollingHash(s)
print(b_search())

Submission status: Wrong Answer

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


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



    ans =0
    for k in range(1,N//2+1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,min(count,k))
            else:
                count=0

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


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

    ok = 0
    ng = N // 2
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            if min(j - i, N - j) + 2 < ans:
                break
            for k in range(0, min(j - i, N - j)):
                if S[i + k] != S[j + k]:
                    ans = max(ans, k)
                    break
            else:
                ans = max(ans, k + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


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

    ok = 0
    ng = N // 2
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            if min(j - i, N - j) + 1 < ans:
                break
            for k in range(0, min(j - i, N - j)):
                if S[i + k] != S[j + k]:
                    ans = max(ans, k)
                    break
            else:
                ans = max(ans, k + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()

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

    ok =0
    ng =N//2
    ans =0
    for i in range(N-1):
        for j in range(i+1,N):
            if N-j <ans-1 or j-i <ans-1:
                break
            for k in range(0,min(j-i,N-j)):
                if S[i+k] != S[j+k]:
                    ans =max(ans,k)
                    break
            else:
                ans = max(ans,k+1)
    print(ans)







if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()

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

    ok =0
    ng =N//2
    ans =0
    for i in range(N-1):
        for j in range(i+1,N):
            if N-j <ans or j-i <ans:
                break
            for k in range(0,min(j-i,N-j)):
                if S[i+k] != S[j+k]:
                    ans =max(ans,k)
                    break
            else:
                ans = max(ans,k+1)
    print(ans)







if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
import sys
input = sys.stdin.readline
n = int(input())
s = tuple(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**32 - 1
b = [1] * (n//2 + 6)
for i in range(n//2 + 5):
    b[i+1] = b[i] * base
    b[i+1] %= mod

length = n//2

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    check = {}
    y = set([])
    for left in range(n - ans + 1):
        if left == 0:
            for i in range(ans):
                hash_ += s[i] * b[ans - i - 1] % mod
                hash_ %= mod
            check[hash_] = [left]
            y.add(hash_)
        else:
            hash_ = base * hash_ % mod - b[ans] * s[left - 1] % mod + s[left + ans - 1]
            hash_ %= mod
            if hash_ in y:
                tmp = bisect_right(check[hash_], left-ans)
                # print("tmp = ", tmp)
                if tmp == 0:
                    check[hash_].append(left)
                else:
                    print(ans)
                    # a = check[hash_][tmp-1]
                    # at = "".join(map(lambda x: chr(x + ord("a")), s[a:a+ans]))
                    # for j in range(ans):
                        # if s[a+j] != s[left+j]:
                            # print("Fail")
                            # exit()
                    # print("Success")
                    exit()
            else:
                check[hash_] = [left]
                y.add(hash_)
        # print(hash_, s[left:left+ans])
print(0)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
n = int(input())
s = list(map(lambda x: ord(x) - ord("a"), input()))
base = 1007
mod = 10**9 + 7
b = [1] * (n//2 + 6)
for i in range(n//2 + 5):
    b[i+1] = b[i] * base
    b[i+1] %= mod

length = n//2
check = {}

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    for left in range(n - ans + 1):
        if left == 0:
            for i in range(ans):
                hash_ += s[i] * b[ans - i - 1] % mod
                hash_ %= mod
            check[hash_] = [left]
        else:
            hash_ = base * hash_ % mod - b[ans] * s[left - 1] % mod + s[left + ans - 1]
            hash_ %= mod
            if hash_ in check.keys():
                tmp = bisect_right(check[hash_], left-ans)
                # print("tmp = ", tmp)
                if tmp == 0:
                    check[hash_].append(left)
                else:
                    print(ans)
                    exit()
            else:
                check[hash_] = [left]
        # print(hash_, s[left:left+ans])
print(0)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    dp = [0] * (N + 1)
    ans = 0

    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N):
            if S[i] == S[j]:
                dp[j] = dp[j + 1] + 1
            if ans < min(dp[j], j - i):
                ans = min(dp[j], j - i)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  for i in dp:
    print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  #print(dp)
  
  ans=0
  for i in range(n):
    for j in range(n):
      if i<j:
        t=min(j,dp[i][j])
        ans=max(ans,t)
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  #print(dp)
  
  ans=0
  for i in range(n):
    for j in range(n):
      if i<j:
        t=min(j-1,dp[i][j])
        ans=max(ans,t)
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
      if s[i]==s[j]:
        dp[i][j]+=dp[i+1][j+1]+1
  #print(dp)
  
  ans=0
  for i in range(n):
    for j in range(n):
      if i<j:
        t=min(j-1,dp[i][j])
        ans=max(ans,t)
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:

def main():
  n=int(input())
  s=input()
  ans=0
  for i in range(n):
    Z=[0]*n
    j=i+1
    while j<n:
      k=0
      while i+k<j and j+k<n and s[i+k]==s[j+k]:
        k+=1
        Z[j]=k
      if k>1:
        j+=k
      else:
        j+=1
      #j+=max(k,1)
    t=max(Z)
    if ans<t:
      ans=t
  print(ans)


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l = [[] for i in range(n+1)]
l[0] = ['0',0]
ans = 0
for i in range(1,n+1):
    l[i] = [s[i-1:],i]
l.sort()
for i in range(n):
    m = min(len(l[i][0]),len(l[i+1][0]))
    x = l[i][0]
    y = l[i+1][0]
    z = 0
    while z < m:
        if x[z] != y[z]:
            break
        z += 1
    if z >= l[i][1] - l[i+1][1]:
        z = l[i][1] - l[i+1][1]
    ans = max(z,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l = [[] for i in range(n+1)]
l[0] = ['0',0]
ans = 0
for i in range(1,n+1):
    l[i] = [s[i-1:],i]
l.sort()
for i in range(n):
    m = min(len(l[i][0]),len(l[i+1][0]))
    x = l[i][0]
    y = l[i+1][0]
    z = 0
    while z < m:
        if x[z] != y[z]:
            break
        z += 1
    if z > l[i][1] - l[i+1][1]:
        z = l[i][1] - l[i+1][1]
    ans = max(z,ans)
print(ans)

Submission status: Wrong Answer

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


def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table


def hoge_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret = 0
    while i < len(string):
        if (string[i] == pattern[j]) and (i-j >= j):
            i += 1
            j += 1
            if i-j >= j-1:
                ret = max(j, ret)
        elif j == 0:
            i += 1
        else:
            j = table[j]
    return ret

ans = 0
for i in range(N):
    res = hoge_search(S[i + 1:], S[i:])
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

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


def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table


def hoge_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret = 0
    while i < len(string):
        if string[i] == pattern[j]:
            i += 1
            j += 1
            if i-j >= j-1:
                ret = max(j, ret)
        elif j == 0:
            i += 1
        else:
            j = table[j]
    return ret

ans = 0
for i in range(N):
    res = hoge_search(S[i + 1:], S[i:])
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(int)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v]:
                if i >= d[v] + m:
                    return True
            else: d[v] = i
        return False

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

    print(left)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, pow(2, 61) - 1
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(int)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v] and i >= d[v] + m:
                    return True
            d[v] = i
        return False

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

    print(left)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(int)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v] and i >= d[v] + m:
                    return True
            d[v] = i
        return False

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

    print(left)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def cin():  return list(map(int,input().split()))

def alpha2num(alpha):
    num = 0
    for index, item in enumerate(list(alpha)):  num += pow(26, len(alpha) - index - 1) * (ord(item) - ord('a') + 1)
    return num

def rol_hash(l):

    b, h = 1007, 10 ** 9 + 9
    base = pow(b, l, h)
    hash_s = 0
    dic = {}
    for i in range(l):  hash_s = (hash_s * b + alpha2num(S[i])) % h
    dic[hash_s] = l - 1
    for i in range(N - l + 1):
        if i + l < N:
            hash_s = (hash_s * b - base * alpha2num(S[i]) + alpha2num(S[i + l])) % h
            if hash_s in dic:
                if dic[hash_s] < i:  return 1
            else:  dic[hash_s] = i + l - 1
    return 0

def is_ok(mid):
    return rol_hash(mid)

def binary_search(left, right):
    while (abs(right - left) > 1):
        mid = (left + right) // 2
        if is_ok(mid):  right = mid
        else:  left = mid
    return right

N = cin()[0]
S = input()

left = N + 1
right = -1
ret = binary_search(left, right)
if ret == right:  print(0)
else:  print(ret)

Submission status: Wrong Answer

Solution code:
def cin():  return list(map(int,input().split()))

def alpha2num(alpha):
    num = 0
    for index, item in enumerate(list(alpha)):
        num += pow(26, len(alpha) - index - 1) * (ord(item) - ord('a') + 1)
    return num

def rol_hash(l):

    b, h = 10 ** 6 + 7, 10 ** 9 + 7
    base = pow(b, l, h)
    hash_s = 0
    dic = {}
    for i in range(l):  hash_s = (hash_s * b + alpha2num(S[i])) % h
    dic[hash_s] = l - 1
    for i in range(N - l + 1):
        if i + l < N:
            hash_s = (hash_s * b - base * alpha2num(S[i]) + alpha2num(S[i + l])) % h
            if hash_s in dic:
                if dic[hash_s] < i:  return 1
            else:  dic[hash_s] = i + l - 1
    return 0

def is_ok(mid):
    return rol_hash(mid)

def binary_search(left, right):
    while (abs(right - left) > 1):
        mid = (left + right) // 2
        if is_ok(mid):  right = mid
        else:  left = mid
    return right

N = cin()[0]
S = input()

left = N + 1
right = -1
ret = binary_search(left, right)
if ret == right:  print(0)
else:  print(ret)

Submission status: Wrong Answer

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

dic = {}
#ここがTLEの原因になっている。
for i in range(N):
    for j in range(N):
        if S[i:j+1] not in dic:
            dic[S[i:j+1]] = []
        dic[S[i:j+1]].append((i,j))

Submission status: Wrong Answer

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

dic = {}
for i in range(N):
    for j in range(N):
        if S[i:j+1] not in dic:
            dic[S[i:j+1]] = []
        dic[S[i:j+1]].append((i,j))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque

class RollingHash():
    def __init__(self, s, base1=1007, base2=2009, mod1=10**9+7, mod2=10**9+9):
        self.mod1 = mod1
        self.mod2 = mod2
        self.s = s
        n = len(s)
        self.hash1 = [0]*(n+1)
        self.pow1 = [1]*(n+1)
        self.hash2 = [0]*(n+1)
        self.pow2 = [1]*(n+1)
        for i in range(n):
            self.hash1[i+1] = (self.hash1[i]*base1 + ord(s[i])) % self.mod1
            self.pow1[i+1] = (self.pow1[i]*base1) % self.mod1
            self.hash2[i+1] = (self.hash2[i]*base2 + ord(s[i])) % self.mod2
            self.pow2[i+1] = (self.pow2[i]*base2) % self.mod2

    def get(self, l, r):
        h1 = (self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod1
        h2 = (self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2
        return (h1,h2)


n = int(input())
s = input()
rh = RollingHash(s, base1=10007, base2=10009, mod1=2^61-1, mod2=2^61-1)

for len_ in range(n//2,0,-1):
    ql = [(-1,-1)]*(len_-1)
    wait_q = deque(ql)
    hset = set()
    # print(len_)
    for i in range(n-len_+1):
        # print(s[i:i+len_])
        hs = rh.get(i,i+len_)
        if hs in hset:
            print(len_)
            exit()
        else:
            wait_q.append(hs)
            hset.add(wait_q.popleft())
        # print(wait_q)
        # print(hset)

else:
    print(0)