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: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SuffixArray(object):
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        lcp: O(1)
    """
    def __init__(self,s):
        """
        s: str
        """
        self.__s=s
        self.__n=len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()
 
    # suffix array
    def __suffix_array(self):
        s=self.__s; n=self.__n
        # initialize
        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)
        # iterate
        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
 
    # LCP array
    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
 
    # sparse table
    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[:]
        # construct
        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):
        """
        a,b: int 0<=a,b<n
        return LCP length between s[a:] and s[b:]
        """
        if a==b: return self.__n-a
        l,r=self.__rank[a],self.__rank[b]
        l,r=min(l,r)+1,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 resolve():
    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)
resolve()

Submission status: Accepted

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
            zk = 1
            while zi + zk < zln and zk + zl[zk] < zj:
                zl[zi+zk] = zl[zk]
                zk += 1
            zi += zk
            zj -= zk

        for j in range(len(zl)):
            if zl[j] <= j:
                mt = max(mt, zl[j])
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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[j]:
            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: Accepted

Solution code:
#z-algolithm

n = int(input())
s_ = input()
ans = 0
for i in range(n-2):
    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] = r-l
        k = 1
        while l+k<r and z[k]<r-l-k:
            z[l+k] = z[k]
            k+=1
        l = l+k
    for i in range(n-i):###ここで処理
        z[i] = min(z[i],i)
    ans = max(ans,max(z))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a=i=j=0
while j<n:
  t=s[i:j]
  if t in s[j:]:
    a=max(a,j-i)
    j+=1
  else:
    i+=1
print(a)

Submission status: Accepted

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
            zk = 1
            while zi + zk < zln and zk + zl[zk] < zj:
                zl[zi+zk] = zl[zk]
                zk += 1
            zi += zk
            zj -= zk
        for j, v in enumerate(zl):
            if v < j + 1:
                mt = max(mt, v)
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def z_algo(s):
    N = len(s)
    A = [0]*N
    i = 1; j = 0
    A[0] = N
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k

    # 自身は含まない
    for i in range(N):
        A[i] = min(A[i],i)
    #
    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')

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 = max(lenC)
print(ans)

Submission status: Accepted

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

    # 自身は含まない
    for i in range(N):
        A[i] = min(A[i],i)
    #
    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 = max(lenC)
print(ans)

Submission status: Accepted

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
        i += k; j -= k

    # 自身は含まない
    for i in range(N):
        B[i] = i
    #
    for i in range(N):
        A[i] = min(A[i],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: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisection(l,r,f,left=True,discrete=True):
    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 (l+r)/2 if not discrete else l if left else r

class RollingHash(object):
    from random import randint
    __MASK30=(1<<30)-1
    __MASK31=(1<<31)-1
    __MOD=(1<<61)-1
    __base=randint(129,__MASK31)

    def __init__(self,s:str):
        n=len(s)
        H=[0]*(n+1); P=[1]*(n+1)
        for i in range(n):
            H[i+1]=self.__modulo(self.__multiple(H[i],self.__base)+ord(s[i]))
            P[i+1]=self.__modulo(self.__multiple(P[i],self.__base))
        self.__H=H; self.__P=P

    def __multiple(self,a,b):
        au=a>>31
        ad=a&self.__MASK31
        bu=b>>31
        bd=b&self.__MASK31
        m=ad*bu+au*bd
        mu=m>>30
        md=m&self.__MASK30
        return 2*au*bu+mu+(md<<31)+ad*bd

    def __modulo(self,x):
        x=(x&self.__MOD)+(x>>61)
        if(x>self.__MOD): x-=self.__MOD
        return x

    def hash(self,l,r):
        H=self.__H; P=self.__P
        res=H[r]+self.__MOD*3-self.__multiple(H[l],P[r-l])
        if(res<0): return res+self.__MOD
        else: return self.__modulo(res)

def resolve():
    n=int(input())
    s=input()
    rh=RollingHash(s)
    def check(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(bisection(0,n,check))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisection(l,r,f,left=True,discrete=True):
    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 (l+r)/2 if not discrete else l if left else r

class RollingHash(object):
    from random import randint
    __MASK30=(1<<30)-1
    __MASK31=(1<<31)-1
    __MOD=(1<<61)-1
    __base=randint(129,__MASK31)

    def __init__(self,s:str):
        n=len(s)
        b=self.__base
        H=[0]*(n+1); P=[1]*(n+1)
        for i in range(n):
            H[i+1]=self.__modulo(self.__multiple(H[i],b)+ord(s[i]))
            P[i+1]=self.__multiple(P[i],b)
        self.__H=H; self.__P=P

    def __multiple(self,a,b):
        au=a>>31
        ad=a&self.__MASK31
        bu=b>>31
        bd=b&self.__MASK31
        m=ad*bu+au*bd
        mu=m>>30
        md=m&self.__MASK30
        return self.__modulo(2*au*bu+mu+(md<<31)+ad*bd)

    def __modulo(self,x):
        x=(x&self.__MOD)+(x>>61)
        if(x>self.__MOD): x-=self.__MOD
        return x

    def hash(self,l,r):
        H=self.__H; P=self.__P
        return self.__modulo(H[r]+self.__MOD*3-self.__multiple(H[l],P[r-l]))

def resolve():
    n=int(input())
    s=input()
    rh=RollingHash(s)
    def check(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(bisection(0,n,check))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisection(l,r,f,left=True,discrete=True):
    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 (l+r)/2 if not discrete else l if left else r

class RollingHash(object):
    from random import randint
    __MASK30=(1<<30)-1
    __MASK31=(1<<31)-1
    __MOD=(1<<61)-1
    __base=randint(129,__MASK31)

    def __init__(self,s:str):
        n=len(s)
        b=self.__base
        H=[0]*(n+1); P=[1]*(n+1)
        for i in range(n):
            H[i+1]=self.__modulo(self.__multiple(H[i],self.__base)+ord(s[i]))
            P[i+1]=self.__multiple(P[i],self.__base)
        self.__H=H; self.__P=P

    def __multiple(self,a,b):
        au=a>>31
        ad=a&self.__MASK31
        bu=b>>31
        bd=b&self.__MASK31
        m=ad*bu+au*bd
        mu=m>>30
        md=m&self.__MASK30
        return self.__modulo(2*au*bu+mu+(md<<31)+ad*bd)

    def __modulo(self,x):
        x=(x&self.__MOD)+(x>>61)
        if(x>self.__MOD): x-=self.__MOD
        return x

    def hash(self,l,r):
        H=self.__H; P=self.__P
        return self.__modulo(H[r]+self.__MOD*3-self.__multiple(H[l],P[r-l]))

def resolve():
    n=int(input())
    s=input()
    rh=RollingHash(s)
    def check(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(bisection(0,n,check))
resolve()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a=i=j=0
while j<n:
  t=s[i:j]
  if t in s[j:]:
    a=max(a,j-i)
    j+=1
  else:
    i+=1
print(a)

Submission status: Accepted

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):
        r = l+ret+1
        while r < n-ret:
            if s[l:r] in s[r:]:
                ret = max(ret, r-l)
            else:
                break
            r += 1

    return str(ret)


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

Submission status: Accepted

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


def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    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: Accepted

Solution code:
import collections


class RollingHashSingle:
    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


class RollingHash:
    def __init__(self,
                 s,
                 base=(10**4 + 7, 10**4 + 9),
                 mod=(10**9 + 7, 10**9 + 9)):
        if isinstance(base, int):
            assert isinstance(mod, int)
            self.base = (base, )
            self.mod = (mod, )
        elif isinstance(base, tuple):
            assert isinstance(mod, tuple)
            assert len(base) == len(mod)
            self.base = base
            self.mod = mod
        else:
            raise ValueError()

        self._rh = [
            RollingHashSingle(s, base, mod)
            for base, mod in zip(self.base, self.mod)
        ]

    def get(self, left, right):
        return tuple(rh.get(left, right) for rh in self._rh)


n = int(input())
s = input().rstrip()
rh = RollingHash(s)


def check(diff):
    d = collections.defaultdict(list)
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        d[h].append(i)
    for l in d.values():
        if max(l) - min(l) >= diff:
            return True
    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: Accepted

Solution code:
import collections


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 + 7)


def check(diff):
    d = collections.defaultdict(list)
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        d[h].append(i)
    for l in d.values():
        if max(l) - min(l) >= diff:
            return True
    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: Accepted

Solution code:
import collections


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=26, mod=2**50 + 1)


def check(diff):
    d = collections.defaultdict(list)
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        d[h].append(i)
    for l in d.values():
        if max(l) - min(l) >= diff:
            return True
    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: Accepted

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(i,n):
        ans = max(ans, min(j-i, a[j-i]))
  print(ans)
solve()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    
    from itertools import product
    for i,j in product(reversed(range(n)),repeat=2):###for を置き換え
        if j>i:
            continue
        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):
      	for j in range(i):###
        	mx = max(mx,min(i-j,dp[i][j]))###i-jで抑える
    print(mx)

if __name__ =='__main__':main()

Submission status: Accepted

Solution code:
import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)

Submission status: Accepted

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)
    v_array = [min(i, z) for i, z in enumerate(z_array)]
    ans = max(ans, max(v_array))


print(ans)

Submission status: Accepted

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

res = 0
i,j = 0, 1
while j<n:
    if s[i:j] in s[j:]:
        res = max(res, j-i)
        j += 1
    else:
        i += 1
    if i==j:
        i += 1
        j += 2
print(res)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
 
l_cursor = 0
r_cursor = 1

max_l = 0
 
while l_cursor < N:
    if r_cursor - l_cursor > N - r_cursor:
        break

    serch_string = S[l_cursor:r_cursor]

    if serch_string in S[r_cursor:]:
        max_l = max(max_l, len(serch_string))
        r_cursor += 1
    else:
        l_cursor += 1
 
print(max_l)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# if x < y:
#     z = x
# elif True:
#     z = y
# else:
#     z = 100
import sys,os,math
from collections import Counter, defaultdict
import bisect
from sys import stdin, stdout
from itertools import repeat


# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())

def main():
    n = map(int, raw_input().split())[0]
    s = raw_input().strip()
    d = [[0 for i in range(n+5)] for i in range(n+5)]
    mx = 0
    for i in range(1, n+1):
        for j in range(i, n+1):
            if s[i-1] == s[j-1]:
                d[i][j] = min(d[i-1][j-1]+1, abs(j-i))
                # print d[i][j], i, j
                mx = max(mx, d[i][j])
            else:
                d[i][j] = 0
    print mx

main()

Submission status: Accepted

Solution code:
def z_algo(N, S):
    i = 0 # start 
    j = 1 # end
    ml = 0 # max length

    while i < N:
        if j-i > N-j:
            break
        
        sw = S[i:j]

        if sw in S[j:]:
            ml = max(ml, len(sw))
            j += 1
        else:
            i += 1

    return ml


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

print(z_algo(N, S))

Submission status: Accepted

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

dp=[ [0 for r in range(N+1)] for l in range(N+1)]


for r in range(N-1,-1,-1):
	for l in range(r-1,-1,-1):
		if s[l]==s[r]:
			dp[l][r]=min(abs(r-l),dp[l+1][r+1]+1)
		else:
			dp[l][r]=0

ans=0
for l in range(N):
	ans=max(ans,max(dp[l]))

print ans

Submission status: Accepted

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

D={}
def check(m):
	for i in range(N):
		if i+m<=N:
			str=s[i:i+m]
			if str in D:
				if i-D[str]>=m:
					return True
			else:
				D[str]=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: Accepted

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

D={}
def check(m):
	for i in range(N):
		if i+m<=N:
			str=s[i:i+m]
			if str in D:
				if i-D[str]>=m:
					return True
			else:
				D[str]=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: Accepted

Solution code:
# -*- coding: utf-8 -*-
# RollingHash
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=10**9+7
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:
				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: Accepted

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=10**9+7
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]*pow(base,(r-l))

# 長さ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:
				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: Accepted

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:
				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: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def two_pointers(N, S):
    end = 1
    start = 0
    max_length = 0

    while start < N:
        if end-start > N-end:
            break
        subword = S[start:end]
        if subword in S[end:]:
            max_length = max(max_length, len(subword))
            end += 1
        else:
            start += 1
            if start == end:
                end += 1
    return max_length


def solve(N: int, S: str):
    print(two_pointers(N, S))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def z_algo(N, S):
    end = 1
    start = 0
    max_length = 0

    while start < N:
        while end-start > N-end:
            break
        subword = S[start:end]
        if subword in S[end:]:
            max_length = max(max_length, len(subword))
            end += 1
        else:
            start += 1
            if start == end:
                end += 1
    return max_length


def solve(N: int, S: str):
    print(z_algo(N, S))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    d = {"Sunny":1 , "Cloudy":2, "Rainy":0}
    a = ["Sunny", "Cloudy", "Rainy"]
    print(a[d[input().rstrip()]])
    return

#B
def B():
    s = S()
    for i, si in enumerate(s):
        if i % 2:
            if si == "R":
                print("No")
                return
        else:
            if si == "L":
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n, k, q = LI()
    d = [0] * n
    for _ in range(q):
        a = II() - 1
        d[a] += 1
    for a in d:
        if k - (q - a) > 0:
            print("Yes")
        else:
            print("No")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for ai in a:
        heappush(q, -ai)
    for _ in range(m):
        heappush(q, heappop(q) / 2)
    ans = 0
    while q:
        ans += int(-heappop(q))
    print(ans)
    return

# E
# 解説AC
# ロリハやZアルゴリズムでもいける
# できないけどDPでできる
def E():
    n = II()
    s = S()
    dp = [[0] * (n + 1) for i in range(n + 1)]
    ans = 0
    for i in range(n - 1, -1, -1):
        for j in range(n - 1, i, -1):
            if s[i] == s[j]:
                dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1)
            ans = max(ans, min(dp[i][j], j - i))
    print(ans)

    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

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

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
        maxv = max(maxv, min(dp[i][j], j-i))
print(maxv)