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()
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)
    """
    __base1=1007; __mod1=10**9
    __base2=1009; __mod2=10**7

    def __init__(self,S):
        """
        S: str
        """
        n=len(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,s in enumerate(S):
            H1[i+1]=(H1[i]*b1+ord(s))%m1
            H2[i+1]=(H2[i]*b2+ord(s))%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 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
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%m1)%m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%m2)%m2)

    @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

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # initialize
        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))
resolve()

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
            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(ans,min(sa.lcp(i,j),j-i))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
class RollingHash:
    def __init__(self, s: str, base: int=1007, mod: int=10**9+7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.hash_cum = [0] * (self.n + 1) # hash_cum[i] = (hash of s[:i])
        self.base_pow = [1] * (self.n + 1) # base_pow[i] = base ** i
        for i in range(self.n):
            self.hash_cum[i+1] = (self.hash_cum[i] * base + ord(s[i])) % mod
            self.base_pow[i+1] = (self.base_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        hash_val = self.hash_cum[r] - self.hash_cum[l] * self.base_pow[r-l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self, s: str, base_list: list=[1007, 2009], mod_list: list=[10**9+7, 10**9+9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.rh_list = [RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple( self.rh_list[i].get_hash(l, r) for i in range(self.n) )




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

rh = RollingHashMulti(s)

def check(x):
    hash_dict = dict()
    for i in range(n-x+1):
        hash_val = rh.get_hash(i, i+x)
        if hash_val in hash_dict:
            if i - hash_dict[hash_val] >= x:
                return True
        else:
            hash_dict[hash_val] = i
    return False


lb = 0
ub = n // 2 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

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:
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        get_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):
        n=self.__n; s=self.__s;
        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
            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 (LCPのminをとるindexを持つ)
    def __sparse_table(self):
        n=self.__n
        logn=max(0,(n-1).bit_length())
        table=[[0]*n for _ in range(logn)]
        table[0]=list(range(n))
        # construct
        for i in range(1,logn):
            for k in range(n):
                if k+(1<<(i-1))>=n:
                    table[i][k]=table[i-1][k]
                    continue
                if self.__lcp[table[i-1][k]]<=self.__lcp[table[i-1][k+(1<<(i-1))]]:
                    table[i][k]=table[i-1][k]
                else:
                    table[i][k]=table[i-1][k+(1<<(i-1))]
        self.__table=table

    def get_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
        if r-l==1: return self.__lcp[l]
        i=(r-l-1).bit_length()-1
        if self.__lcp[self.__table[i][l]]<=self.__lcp[self.__table[i][r-(1<<i)]]:
            return self.__lcp[self.__table[i][l]]
        else:
            return self.__lcp[self.__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(ans,min(sa.get_lcp(i,j),j-i))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
S = input()
 
dp = [[0] * 5005 for _ in range(5005)]
 
for i in range(N-1, -1, -1):
  for j in range(N-1, -1, -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:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SuffixArray:
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        get_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):
        n=self.__n; s=self.__s;
        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
            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 (LCPのminをとるindexを持つ)
    def __sparse_table(self):
        n=self.__n
        logn=max(0,(n-1).bit_length())
        table=[[0]*n for _ in range(logn)]
        table[0]=list(range(n))
        # construct
        for i in range(1,logn):
            for k in range(n):
                if k+(1<<(i-1))>=n:
                    table[i][k]=table[i-1][k]
                    continue
                if self.__lcp[table[i-1][k]]<=self.__lcp[table[i-1][k+(1<<(i-1))]]:
                    table[i][k]=table[i-1][k]
                else:
                    table[i][k]=table[i-1][k+(1<<(i-1))]
        self.__table=table

    def get_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
        if r-l==1: return self.__lcp[l]
        i=(r-l-1).bit_length()-1
        if self.__lcp[self.__table[i][l]]<=self.__lcp[self.__table[i][r-(1<<i)]]:
            return self.__lcp[self.__table[i][l]]
        else:
            return self.__lcp[self.__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(n):
            ans=max(ans,min(sa.get_lcp(i,j),j-i))
    print(ans)
resolve()

Submission status: Accepted

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

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

for i in range(1,n):
    for j in range(i+1,n+1):
        if s[n-i]==s[n-j]:
            dp[n-i][n-j]=min((n-i)-(n-j),dp[n-i+1][n-j+1]+1)
            ans=max(dp[n-i][n-j],ans)
        else:
            pass
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
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)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=1009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2

    @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]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2)

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # initialize
        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))
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 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)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=1009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2

    @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]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1,
        (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2)

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # initialize
        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))
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 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)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=1009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2

    @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]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1,(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2)

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # initialize
        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))
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 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)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=2009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2

    @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]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1,(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2)

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # S[0:d],...,S[n-d:n]に重複があり、かつd離れているか判定
        # initialize
        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))
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 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)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=2009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2
        self.__d=0
        while(m1):
            m1//=10
            self.__d+=1

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

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return hash of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return (self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1*(10**self.__d)+(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # S[0:d],...,S[n-d:n]に重複があり、かつd離れているか判定
        # initialize
        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))
resolve()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l = 0
k = 1
for i in range(N - 1):
   while True:
       if S[i : i + k] in S[i + k :]:
           k += 1
       else:
           break
   l = max(l, k - 1)
print(l)

Submission status: Accepted

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

dp = [ [0] * (n+1) for _ 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
        else:
            dp[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        tmp = min(dp[i][j], abs(i-j))
        if ans < tmp:
            ans = tmp
print(ans)

Submission status: Accepted

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

# Zアルゴリズムで解く

def z_algorithm(S):
    N=len(S)
    A = [N] + [0]*(N-1)
    
    left=1
    length=0
    
    while left < N:
        
        # prefixが同じ間length加算
        while left + length < N and S[length] == S[left+length]:
            length += 1
        
        # prefixの一致数保存
        A[left] = length
        
        # 一文字一致していなければ戻る
        if length == 0:
            left+=1
            continue
        
        # lengthの分だけleftとindexの間を埋めていく(はみ出ていないとこまで)
        k=1
        while k+left < N and k+A[k]<length:
            A[left+k] = A[k]
            k += 1
            
        left += k
        length -= k
    return A

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    A=z_algorithm(subS)
    for i,a in enumerate(A):
        if i>=a and max_num<a:
            max_num=a
print(max_num)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
right = 0
for left in range(N - 1):
    while right < N and (S[left : right] in S[right :]):
        right += 1
    if left == right:
        right += 1
    ans = max(ans, right - left - 1)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
k = 1
for i in range(N - 1):
    while i + k <= N and (S[i : i + k] in S[i + k :]):
        k += 1
print(k - 1)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
k = 1
for i in range(N - 1):
    while True:
        if S[i : i + k] in S[i + k :]:
            k += 1
        else:
            break
print(k - 1)