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:
MOD = 10 ** 9 + 7


# 平衡二部探索
def bisect(l, r, f, discrete=True, left=True):
    """
        l,r: l<r int if discrete else float
        f: function defined on [l,...,r] to {False,True}
        if discrete: f defined on Z; else: R
        if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
        else: iff i>=d then f(i) is True
        return d such as those above
    """
    assert r > l
    if discrete:
        assert isinstance(l, int) and isinstance(r, int)
    eps = 1 if discrete else 10 ** -12
    if (not left) ^ f(r):
        return r if left else r + 1
    elif left ^ f(l):
        return l - 1 if left else l
    while r - l > eps:
        h = (l + r) // 2 if discrete else (l + r) / 2
        if (not left) ^ f(h):
            l = h
        else:
            r = h
    return h if not discrete else l if left else r


class RollingHash(object):
    """
        construct: O(N)
        query:
            hash: O(1)
            lcp: O(logN)
            search: O(N)
    """
    __base1 = 1007;
    __mod1 = 10 ** 9
    __base2 = 1009;
    __mod2 = 10 ** 7

    def __init__(self, s):
        n = len(s)
        self.__s = s
        self.__n = n
        b1 = self.__base1;
        m1 = self.__mod1
        b2 = self.__base2;
        m2 = self.__mod2
        H1, H2 = [0] * (n + 1), [0] * (n + 1)
        P1, P2 = [1] * (n + 1), [1] * (n + 1)
        for i in range(n):
            H1[i + 1] = (H1[i] * b1 + ord(s[i])) % m1
            H2[i + 1] = (H2[i] * b2 + ord(s[i])) % m2
            P1[i + 1] = P1[i] * b1 % m1
            P2[i + 1] = P2[i] * b2 % m2
        self.__H1 = H1
        self.__H2 = H2
        self.__P1 = P1
        self.__P2 = P2

    @property
    def str(self):
        return self.__s

    @property
    def len(self):
        return self.__n

    def hash(self, l, r=None):
        """
            l,r: int (0<=l<=r<=n)
            return (hash1,hash2) of S[l:r]
        """
        m1 = self.__mod1
        m2 = self.__mod2
        if r is None: r = self.__n
        assert 0 <= l <= r <= self.__n
        hash1 = (self.__H1[r] - self.__P1[r - l] * self.__H1[l] % m1) % m1
        hash2 = (self.__H2[r] - self.__P2[r - l] * self.__H2[l] % m2) % m2
        return hash1, hash2

    @classmethod
    def lcp(cls, rh1, rh2, l1, l2, r1=None, r2=None):
        """
            rh1,rh2: RollingHash object
            l1,l2,r1,r2: int 0<=l1<=r1<=r1.len, 0<=l2<=r2<=rh2.len
            return lcp length between rh1[l1:r1] and rh2[l2:r2]
        """
        if r1 is None: r1 = rh1.__n
        if r2 is None: r2 = rh2.__n
        assert 0 <= l1 <= r1 <= rh1.__n and 0 <= l2 <= r2 <= rh2.__n
        L = 0
        R = min(r1 - l1, r2 - l2)
        if rh1.hash(l1, l1 + R) == rh2.hash(l2, l2 + R): return R
        while R - L > 1:
            H = (L + R) // 2
            if rh1.hash(l1, l1 + H) == rh2.hash(l2, l2 + H): L = H
        else:
            R = H
        return L

    @classmethod
    def search(cls, pattern, text):
        """
        pattern,text: RollingHash object
        return list of index i's satisfying text[i:] starts with pattern
        """
        n = text.__n;
        m = pattern.__n
        res = []
        for i in range(n - m + 1):
            if text.hash(i, i + m) == pattern.hash(0, m):
                res.append(i)
        return res

if __name__ == '__main__':
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    n = 13
    S = "strangeorange"
    rh = RollingHash(S)
    def judge(d):
        J = {rh.hash(i, i+d): -1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h = rh.hash(i, i+d)
            if J[h] != -1:
                if i-J[h] >= d: return True
            else:
                J[h] = i
        return False
    print(bisect(0, n, judge))

Submission status: Wrong Answer

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

dp = [[0 for j in range(n+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(n):
        if s[i] == s[j] and i+dp[i][j]+1 <= j:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],dp[i][j]+1)
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
# O(N**2)
class SuffixArray(object):
    def __init__(self, s):
        self.__s = s
        self.__n = len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    def __suffix_array(self):
        s = self.__s
        n = self.__n
        sa = list(range(n))
        rank = [ord(s[i]) for i in range(n)]
        tmp = [0]*n
        k = 1
        cmp_key = lambda i: (rank[i], rank[i+k] if i+k < n else -1)
        while k <= n:
            sa.sort(key=cmp_key)
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i-1]] + (cmp_key(sa[i-1]) < cmp_key(sa[i]))
            rank = tmp[:]
            k<<=1
        self.__sa = sa
        self.__rank = rank

    def __lcp_array(self):
        s = self.__s
        n = self.__n
        sa = self.__sa
        rank = self.__rank
        lcp = [0]*n
        h = 0
        for i in range(n):
            j = sa[rank[i]-1]
            if h>0:
                h -= 1
            if rank[i]==0:
                continue
            while j+h<n and i+h<n and s[j+h]==s[i+h]:
                h += 1
            lcp[rank[i]] = h
        self.__lcp = lcp

    def __sparse_table(self):
        n = self.__n
        logn = max(0, (n-1).bit_length())
        table = [[0]*n for _ in range(logn)]
        table[0] = self.__lcp[:]
        # 直積（デカルト積）[a,b,c] [x,y,z] = (a,x),(a,y),(a,z),(b,),(c,)....
        from itertools import product
        for i, k in product(range(1, logn), range(n)):
            if k+(1<<(i-1)) >= n:
                table[i][k] = table[i-1][k]
            else:
                table[i][k] = min(table[i-1][k], table[i-1][k+(1<<(i-1))])
        self.__table = table

    def lcp(self, a, b):
        if a==b:
            return self.__n-a
        l, r = self.__rank[a], self.__rank[b]
        l = min(l, r)+1
        r = max(l, r)+1
        i = max(0, (r-l-1).bit_length()-1)
        table = self.__table
        return min(table[i][l], table[i][r-(1<<i)])

def main():
  N = int(input())
  S = input()
  sa = SuffixArray(S)
  ans = 0
  for i in range(N):
    for j in range(i+1, N):
      ans = max(min(j-i, sa.lcp(i,j)), ans)
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
# O(N**2)
class SuffixArray(object):
    def __init__(self, s):
        self.__s = s
        self.__n = len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    def __suffix_array(self):
        s = self.__s
        n = self.__n
        sa = list(range(n))
        rank = [ord(s[i]) for i in range(n)]
        tmp = [0]*n
        k = 1
        cmp_key = lambda i: (rank[i], rank[i+k] if i+k < n else -1)
        while k <= n:
            sa.sort(key=cmp_key)
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i-1]] + (cmp_key(sa[i-1]) < cmp_key(sa[i]))
            rank = tmp[:]
            k<<=1
        self.__sa = sa
        self.__rank = rank

    def __lcp_array(self):
        s = self.__s
        n = self.__n
        sa = self.__sa
        rank = self.__rank
        lcp = [0]*n
        h = 0
        for i in range(n):
            j = sa[rank[i]-1]
            if h>0:
                h -= 1
            if rank[i]==0:
                continue
            while j+h<n and i+h<n and s[j+h]==s[i+h]:
                h += 1
            lcp[rank[i]] = h
        self.__lcp = lcp

    def __sparse_table(self):
        n = self.__n
        logn = max(0, (n-1).bit_length())
        table = [[0]*n for _ in range(logn)]
        table[0] = self.__lcp[:]
        # 直積（デカルト積）[a,b,c] [x,y,z] = (a,x),(a,y),(a,z),(b,),(c,)....
        from itertools import product
        for i, k in product(range(1, logn), range(n)):
            if k+(1<<(i-1)) >= n:
                table[i][k] = table[i-1][k]
            else:
                table[i][k] = min(table[i-1][k], table[i-1][k+(1<<(i-1))])
        self.__table = table

    def lcp(self, a, b):
        if a==b:
            return self.__n-a
        l, r = self.__rank[a], self.__rank[b]
        l = min(l, r)+1
        r = max(l, r)+1
        i = max(0, (r-l-1).bit_length()-1)
        table = self.__table
        return min(table[i][l], table[i][r-(1<<i)])

def main():
  N = int(input())
  S = input()
  sa = SuffixArray(S)
  ans = 0
  for i in range(N):
    for j in range(i+1, N):
      ans = max(min(j-i, sa.lcp(i,j)), ans)
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

dp = [[0 for i in range(5005)] for j in range(5005)]

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

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)

print(ans)

Submission status: Wrong Answer

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

mod = 2**61-1
mx = n//2 + 1
mn = 0

while mx-mn>1:
    mid  = (mx+mn)//2
    keys = {}
    ky = 0
    for i in range(mid):
        ky += pow(335,mid-i-1,mod)*ord(s[i])###335
    ky%=mod
    keys[ky] = [0]
    now_ky = ky
    flag = False
    for i in range(mid,n):
        now_ky = (now_ky*335+ ord(s[i])-pow(335,mid,mod)*ord(s[i-mid]))%mod
        if now_ky in keys:
            #print("hit")
            if keys[now_ky][0]+mid-1<i:######
                mn = mid
                flag = True
                break
        else:
            keys[now_ky] = [i-mid+1]###
        if flag :
            break
    if not flag:
        mx = mid
    #print(flag, mx,mn)
print(mn)

Submission status: Wrong Answer

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

mod = 10**9+7###変えてみた
mx = n//2 + 1
mn = 0

while mx-mn>1:
    mid  = (mx+mn)//2
    keys = {}
    ky = 0
    for i in range(mid):
        ky += pow(335,mid-i-1,mod)*ord(s[i])###335
    ky%=mod
    keys[ky] = [0]
    now_ky = ky
    flag = False
    for i in range(mid,n):
        now_ky = (now_ky*335+ ord(s[i])-pow(335,mid,mod)*ord(s[i-mid]))%mod
        if now_ky in keys:
            #print("hit")
            if keys[now_ky][0]+mid<i:###
                mn = mid
                flag = True
                break
        else:
            keys[now_ky] = [i-mid+1]###
        if flag :
            break
    if not flag:
        mx = mid
    #print(flag, mx,mn)
print(mn)

Submission status: Wrong Answer

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

mod = 2**61-1
mx = n//2 + 1
mn = 0

while mx-mn>1:
    mid  = (mx+mn)//2
    keys = {}
    ky = 0
    for i in range(mid):
        ky += pow(335,mid-i-1,mod)*ord(s[i])###335
    ky%=mod
    keys[ky] = [0]
    now_ky = ky
    flag = False
    for i in range(mid,n):
        now_ky = (now_ky*335+ ord(s[i])-pow(335,mid,mod)*ord(s[i-mid]))%mod
        if now_ky in keys:
            #print("hit")
            if keys[now_ky][0]+mid<i:###
                mn = mid
                flag = True
                break
        else:
            keys[now_ky] = [i-mid+1]###
        if flag :
            break
    if not flag:
        mx = mid
    #print(flag, mx,mn)
print(mn)

Submission status: Wrong Answer

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

mod = 2**61-1
mx = n//2 + 1
mn = 0

while mx-mn>1:
    mid  = (mx+mn)//2
    keys = {}
    ky = 0
    for i in range(mid):
        ky += pow(7,mid-i-1,mod)*ord(s[i])
    ky%=mod
    keys[ky] = [0]
    now_ky = ky
    flag = False
    for i in range(mid,n):
        now_ky = (now_ky*7+ ord(s[i])-pow(7,mid,mod)*ord(s[i-mid]))%mod
        if now_ky in keys:
            #print("hit")
            if keys[now_ky][0]+mid-1<i:###
                mn = mid
                flag = True
                break
        else:
            keys[now_ky] = [i-mid+1]###
        if flag :
            break
    if not flag:
        mx = mid
    #print(flag, mx,mn)
print(mn)

Submission status: Wrong Answer

Solution code:
#ローリングハッシュ+2分探索
n = int(input())
s = input()

mod = 2**61-1
mx = n//2 + 1
mn = 0

while mx-mn>1:
    mid  = (mx+mn)//2
    keys = {}
    ky = 0
    for i in range(mid):
        ky += pow(7,mid-i-1,mod)*ord(s[i])
    ky%=mod
    keys[ky] = [0]
    now_ky = ky
    flag = False
    for i in range(mid,n):
        now_ky = (now_ky*7+ ord(s[i])-pow(7,mid,mod)*ord(s[i-mid]))%mod
        if now_ky in keys:
            #print("hit")
            if keys[now_ky][0]+mid-1<i:
                mn = mid
                flag = True
                break
        else:
            keys[now_ky] = [i-mid]
        if flag :
            break
    if not flag:
        mx = mid
    #print(flag, mx,mn)
print(mn)

Submission status: Wrong Answer

Solution code:
#ローリングハッシュ+2分探索
n = int(input())
s = input()

mod = 2**61-1
mx = n//2 + 1
mn = 0

while mx-mn>1:
    mid  = (mx+mn)//2
    keys = {}
    ky = 0
    for i in range(mid):
        ky += pow(7,mid-i-1,mod)*ord(s[i])
    ky%=mod
    keys[ky] = [0]
    now_ky = ky
    flag = False
    for i in range(mid,n):
        now_ky = (now_ky*7+ ord(s[i])-pow(7,mid,mod)*ord(s[i-mid]))%mod
        if now_ky in keys:
            #print("hit")
            if keys[now_ky][0]+mid<i:
                mn = mid
                flag = True
                break
        else:
            keys[now_ky] = [i-mid]
        if flag :
            break
    if not flag:
        mx = mid
    #print(flag, mx,mn)
print(mn)

Submission status: Wrong Answer

Solution code:
#z-algolithm

n = int(input())
s_ = input()
ans = 0
for i in range(n-1):
    l = 1 #1から
    r = 1
    s = s_[i:]
    z = [0]*(n-i)
    z[0] = n-i
    while l<n-i:
        while r<n-i and s[r] == s[r-l] : #r<n
            r += 1
        if r == l:
            r+=1;l+=1;continue
        z[l] = min(r-l,l)##z-algolithmからの変更点
        k = 1
        while l+k<r and z[k]<r-l-k:
            z[l+k] = min(z[k],k)##ここも変更
            k+=1
        l = l+k
    if z[1:]:
        ans = max(ans,max(z[1:]))
print(ans)

Submission status: Wrong Answer

Solution code:
#z-algolithm

n = int(input())
s_ = input()
ans = 0
for i in range(n-1):
    l = 1 #1から
    r = 1
    s = s_[i:]
    z = [0]*(n-i)
    z[0] = n-i
    while l<n-i:
        while r<n-i and s[r] == s[r-l] : #r<n
            r += 1
        if r == l:
            r+=1;l+=1;continue
        z[l] = min(r-l,l)##z-algolithmからの変更点
        k = 1
        while l+k<r and z[k]<r-l-k:
            z[l+k] = z[k]
            k+=1
        l = l+k
    if z[1:]:
        ans = max(ans,max(z[1:]))
print(ans)

Submission status: Wrong Answer

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

def z_naive(s):
    Z = [len(s)]
 
    for k in range(1, N):
        n = 0
        while n + k < len(s) and s[n] == s[n + k]:
            n += 1
        Z.append(n)
 
    return Z

print(z_naive(s))

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    mt = 0
    for i in range(n):
        zs = s[i:]
        zln = len(zs)
        zl = [0] * zln
        zi = 1
        zj = 0
        while zi < zln:
            while zi + zj < zln and zs[zj] == zs[zi+zj]:
                zj += 1
            zl[zi] = zj
            if zj == 0:
                zi += 1
                continue
            k = 1
            while zi + k < zln and k + zl[k] < zj:
                zl[zi+k] = zl[k]
                k += 1
            zi += k
            zj -= k
        tzl = zl[(len(zl) + 1) // 2:]
        if len(tzl) != 0:
            mt = max(mt, max(tzl))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def z_algo(s):
    N = len(s)
    A = [0]*N
    i = 1; j = 0
    l = len(s)
    A[0] = l
    B = [0]*N
    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
        # 自身は含まない
        if A[i]>=k:
            B[i]=k
        #
        i += k; j -= k

    for i in range(N):
        A[i] = min(A[i],B[i])
#    print(B)
#    A[0] = 0
    return A

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()
S = str(input())
cur = int(0)
ans = int(0)
lenC = []

for i in range(N):
#    print(z_algo(S[i:]))
    lenC.append(max(z_algo(S[i:])))

#print(lenC)
ans = min(max(lenC),N//2)
print(ans)

Submission status: Wrong Answer

Solution code:
def z_algo(s):
    N = len(s)
    A = [0]*N
    i = 1; j = 0
    l = len(s)
    A[0] = l
    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
        # 自身は含まない
    A[0] = 0
        #
    return A

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()
S = str(input())
cur = int(0)
ans = int(0)
lenC = []

for i in range(N):
#    print(z_algo(S[i:]))
    lenC.append(max(z_algo(S[i:])))

#print(lenC)
ans = min(max(lenC),N//2)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = input()
A = [ord(s)-ord("a") for s in S]
#print(A)
D ={}
for i,a in enumerate(A):
  if a in D:
    #print("i:{} a:{} D[a]:{}".format(i,a,D[a])) 
    D[a].append(i)
  else:
    D[a] = [i]
#print(D)
ans = 0
for d in D:
  L = D[d]
  i = 1
  while len(L)>1:
    #print(L)
    memo = [[] for r in range(26)]
    for l in L:
      if l+i <n:
        c = A[l+i]
        memo[c].append(l)
    #print(memo)
    L=[]
    for m in memo:
      if len(m)>1:
        L.extend(m)
    i+=1
    if len(L)>1 and not(len(L)==2 and L[1]-L[0]<i):
      ans = i if i>ans else ans
print(ans)
    
#print(D)

Submission status: Wrong Answer

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

n_list = sorted([(S[i:], i) for i in range(N)], key=lambda x: x[0])

def check_lcp(str_1, str_2):
    cnt = 0
    for s1, s2 in zip(str_1, str_2):
        if s1 != s2:
            break
        cnt += 1
    return cnt


table = [(n_list[0][1], n_list[0][0], 0)]
for (str_1, i), (str_2, j) in zip(n_list[:-1], n_list[1:]):
    lcp = check_lcp(str_1, str_2)
    table.append((j, str_2, lcp))


min_values = [min(table[i+1][2], table[i][0] - table[i+1][0]) for i in range(N-1)]
min_values.append(0)
print(max(min_values))

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]

    ret = 0
    for l in range(n-2):
        for r in range(l+1, n-1):
            if r-l < ret:
                break

            if s[l:r] in s[r:]:
                ret = max(ret, r-l)

    return str(ret)


if __name__ == "__main__":
    print(solve(*[input() for _ in range(2)]))

Submission status: Wrong Answer

Solution code:
class RollingHash:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


n = int(input())
s = input().rstrip()
rh = RollingHash(s, base=10**4 + 7, mod=10**9 + 9)


def check(diff):
    d = {}
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        if h in d.keys():
            if abs(d[h] - i) >= diff:
                return True
        else:
            d[h] = i
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
whole = []
for i in range(n):
  whole.append([s[i:],i])
#print(whole)
whole.sort()
#print(whole)
can = []
for i in range(n-1):
  one = whole[i][0]
  two = whole[i+1][0]
  diff = abs(whole[i][1] - whole[i+1][1])
  l = min(diff,n-whole[i][1],n-whole[i+1][1])
  tmp = 0
  for j in range(l):
    if one[j] == two[j]:
      tmp += 1
    else:
      break
  can.append(tmp)
  #print(tmp,l)
print(max(can))
#print(can)

Submission status: Wrong Answer

Solution code:

def solve():
  n = int(input())
  s = input()
  ans = 0
  for i in range(n//2,n):
    if s[0:i].find(s[i:]) >= 0:
      #print(s[i:],s[0:i],s[0:i].find(s[i:]))
      ans = max(ans,len(s[i:]))
    
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:

def solve():
  n = int(input())
  s = input()
  ans = 0
  for i in range(n//2,n):
    if s[0:i].find(s[i:]) >= 1:
      #print(s[i:],s[0:i],s[0:i].find(s[i:]))
      ans = max(ans,len(s[i:]))
    
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
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
def solve():
  n = int(input())
  s = input()
  ans = 0
  for i in range(n):
    a = z_algo(s[i:])
    for j in range(len(a)):
      if j > 0:
        if a[j] >= a[0]/2:
          ans = max(ans,a[0]//2)
        else:
          ans = max(ans,a[j])
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
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
def solve():
  n = int(input())
  s = input()
  ans = 0
  for i in range(n):
    a = z_algo(s[i:])
    for i in range(len(a)):
      if i > 0:
        if a[i] >= a[0]/2:
          ans = max(ans,a[0]//2)
        else:
          ans = max(ans,a[i])
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
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
def solve():
  n = int(input())
  s = input()
  ans = 0
  for i in range(n):
    a = z_algo(s[i:])
    for i in range(len(a)):
      if i > 0:
        if a[i] >= a[0]/2:
          ans = max(ans,a[0]//2)
        else:
          ans = max(ans,a[i])
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
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
def solve():
  n = int(input())
  s = input()
  ans = 0
  for i in range(n):
    a = z_algo(s[i:])
    for i in range(len(a)):
      if i > 0 and a[i] <= a[0]/2:
        ans = max(ans,a[i])
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    s = input()
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    
    for i in range(n-1,-1,-1):#後ろから
        for j in range(i-1,-1,-1):
            if s[i]!=s[j]:
              	dp[i][j] = 0#continueではない
        	    
            else:
              	dp[i][j] = dp[i+1][j+1] +1
              	"""
              	これでは結局ループしている
                cnt = 0
                for k in range(min(n-j,j-i)):
                    if s[i+k] ==s[j+k]:
                        cnt += 1
                    else:
                        break
                dp[i][j] = cnt
             	"""
    mx = 0
    #print(dp)
    for i in range(n):
        mx = max(mx,max(dp[i]))
    print(mx)

if __name__ =='__main__':main()

Submission status: Wrong Answer

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


def z_algorithm(s):
    n = len(s)
    lcpls = [0] * n  # Longest common prefix lengths
    lcpls[0] = n

    l = r = 1
    while l < n:
        while (r < n) and (s[r - l] == s[r]):
            r += 1

        if l == r:
            l += 1
            r += 1
            continue

        lcpls[l] = r - l

        k = 1
        while (l + k < r) and (lcpls[k] < r - l - k):
            lcpls[l + k] = lcpls[k]
            k += 1
        l += k

    return lcpls


ans = 0
for i in range(N):
    ns = S[i:]
    z_array = z_algorithm(ns)

    ns_length = len(ns)
    v_array = [min(z, ns_length - z) for z in z_array]
    ans = max(ans, max(v_array))

print(ans)

Submission status: Wrong Answer

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


def z_algorithm(s):
    n = len(s)
    lcpls = [0] * n  # Longest common prefix lengths
    lcpls[0] = n

    l = r = 1
    while l < n:
        while (r < n) and (s[r - l] == s[r]):
            r += 1

        if l == r:
            l += 1
            r += 1
            continue

        lcpls[l] = r - l

        k = 1
        while (l + k < r) and (lcpls[k] < r - l - k):
            lcpls[l + k] = lcpls[k]
            k += 1
        l += k

    return lcpls


ans = 0
for i in range(N - 1):
    ns = S[i:]
    z_array = z_algorithm(ns)

    ns_length = len(ns)
    v_array = [min(z, ns_length - z) for z in z_array]
    ans = max(ans, max(v_array))

print(ans)

Submission status: Wrong Answer

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


def z_algorithm(s):
    n = len(s)
    lcpls = [0] * n  # Longest common prefix lengths
    lcpls[0] = n

    l = r = 1
    while l < n:
        while (r < n) and (s[r - l] == s[r]):
            r += 1

        if l == r:
            l += 1
            r += 1
            continue

        lcpls[l] = r - l

        k = 1
        while (l + k < r) and (lcpls[k] < r - l - k):
            lcpls[l + k] = lcpls[k]
            k += 1
        l += k

    return lcpls


ans = 0
for i in range(N - 1):
    ns = S[i:]
    z_array = z_algorithm(ns)

    ns_length = len(ns)
    v_array = [min(z, ns_length - z) for z in z_array[1:]]
    ans = max(ans, max(v_array))


print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
N=input()
s=raw_input()

str="abcdefghijklmnopqrstuvwxyz"
D={}
for i,str in enumerate(str):
	D[str]=i+1

base=27
mod=2**61-1
hash=[]

for i,x in enumerate(s):
	if i==0: hash.append(D[x]%mod)
	else: hash.append( (hash[-1]*base+D[x])%mod )

def get(l,r):
	if l==0: return hash[r-1]%mod
	else: return ( hash[r-1]-hash[l-1]*pow(base,(r-l),mod) )%mod

# 長さmを固定し、区間 [i, i + m) のハッシュ値を求めて、長さmの共通文字列があるかを判定
def check(m):
	C={}
	for i in range(N):
		if i+m<=N:
			hash_value=get(i,i+m)
			if hash_value in C:
				if m<=i-C[hash_value]:
					return True
				else:
					return False
			else:
				C[hash_value]=i
	else:
		return False

l=0
h=N

while 1<(h-l):
	m=(l+h)/2
	if check(m):
		l=m
	else:
		h=m

print l

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
N=input()
s=raw_input()

str="abcdefghijklmnopqrstuvwxyz"
D={}
for i,str in enumerate(str):
	D[str]=i+1

base=27
mod=2**61-1
hash=[]

for i,x in enumerate(s):
	if i==0: hash.append(D[x]%mod)
	else: hash.append( (hash[-1]*base+D[x])%mod )

def get(l,r):
	if l==0: return hash[r-1]%mod
	else: return ( hash[r-1]-hash[l-1]*pow(base,(r-l),mod) )%mod


C=defaultdict(lambda: 0) 
ans=0
for l in range(N+1):
	for r in range(l+1,N+1):
		if C[get(l,r)]==1:
			ans=max(ans,r-l)
		C[get(l,r)]=1

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
N=input()
s=raw_input()

str="abcdefghijklmnopqrstuvwxyz"
D={}
for i,str in enumerate(str):
	D[str]=i+1

base=27
mod=2**61-1
hash=[]

for i,x in enumerate(s):
	if i==0: hash.append((D[x]))
	else: hash.append(hash[-1]*base+D[x])

def get(l,r):
	if l==0: return hash[r-1]
	else: return hash[r-1]-hash[l-1]*base**(r-l)


C=defaultdict(lambda: 0) 
ans=0
for l in range(N+1):
	for r in range(l+1,N+1):
		if C[get(l,r)]==1:
			ans=max(ans,r-l)
		C[get(l,r)]=1

print ans

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
S_list = list(S)
front = ""
back = ""
ans = 0
for s in S_list:
  front += s
  if S.count(front) > 1:
    ans = max(len(front), ans)
for s in reversed(S_list):
  back = s + back
  if S.count(back) > 1:
    ans = max(len(back), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    i = 1; j = 0
    A[0] = length
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = 0
    for a in A:
        if a <= length//2:
            ans = max(ans, a)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)

Submission status: Wrong Answer

Solution code:
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
n = int(input())
s = input()
m = 0
for i in range(len(s)//2):
    z = z_algo(s[i:])
    t = z[n//2:]
    m = max(m, max(t))
print(m)