Problem:


Score : 600 points

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if the number of non-negative integers i satisfying the following condition is finite, and find the maximum value of such i if the number is finite.

There exists a non-negative integer j such that the concatenation of i copies of t is a substring of the concatenation of j copies of s.

Notes

A string a is a substring of another string b if and only if there exists an integer x (0 \leq x \leq |b| - |a|) such that, for any y (1 \leq y \leq |a|), a_y = b_{x+y} holds.

We assume that the concatenation of zero copies of any string is the empty string. From the definition above, the empty string is a substring of any string. Thus, for any two strings s and t, i = 0 satisfies the condition in the problem statement.

Constraints

1 \leq |s| \leq 5 \times 10^5

1 \leq |t| \leq 5 \times 10^5

s and t consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
t

Output

If the number of non-negative integers i satisfying the following condition is finite, print the maximum value of such i; if the number is infinite, print -1.

Sample Input 1

abcabab
ab

Sample Output 1

3

The concatenation of three copies of t, ababab, is a substring of the concatenation of two copies of s, abcabababcabab, so i = 3 satisfies the condition.

On the other hand, the concatenation of four copies of t, abababab, is not a substring of the concatenation of any number of copies of s, so i = 4 does not satisfy the condition.

Similarly, any integer greater than 4 does not satisfy the condition, either. Thus, the number of non-negative integers i satisfying the condition is finite, and the maximum value of such i is 3.

Sample Input 2

aa
aaaaaaa

Sample Output 2

-1

For any non-negative integer i, the concatenation of i copies of t is a substring of the concatenation of 4i copies of s. Thus, there are infinitely many non-negative integers i that satisfy the condition.

Sample Input 3

aba
baaab

Sample Output 3

0

As stated in Notes, i = 0 always satisfies the condition.



Sample input:
abcabab
ab


Sample output:
3

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
s=list(input())
t=list(input())

tsr=list(t)+list(s)
while len(tsr)<2*len(t)+len(s):
  tsr+=s
#print(tsr)

#Z[i]: 文字列Sと各S[i:]の最長共通接頭辞の長さ
def z_alg(S):
  NN=len(S)
  Z=[NN]+[0]*(NN-1)
  i,j=1,0
  while i<NN:
    while i+j<NN and S[j]==S[i+j]:
      j+=1
    if not j:
      i+=1
      continue
    Z[i]=j
    k=1
    while NN-i>k and k<j-Z[k]:
      Z[i+k]=Z[k]
      k+=1
    i+=k
    j-=k
  return Z

zlist=z_alg(tsr)
#print(zlist)

match_list=[]
for i in range(len(s)):
  match_list.append(zlist[i+len(t)]>=len(t))
#print(match_list)

path=[-1]*len(s)
for i in range(len(s)):
  if match_list[i]:
    path[i]=(i+len(t))%len(s)
#print(path)

dist=[-1]*len(s)
for i in range(len(s)):
  if dist[i]!=-1:
    continue
    
  d=0
  offset=0
  stack=[i]
  ii=i
  while path[ii]!=-1:
    if d>len(s):
      print(-1)
      sys.exit(0)
    elif dist[ii]!=-1:
      offset=dist[ii]
      break    
    ii=path[ii]
    stack.append(ii)
    d+=1
  
  cnt=0
  while stack:
    p=stack.pop()
    dist[p]=offset+cnt
    cnt+=1
    
#print(dist)
print(max(dist))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60

class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

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

    @staticmethod
    def gen(a, b, num):
        import random
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



def slv(S, T):
    lt = len(T)
    ls = len(S)
    SS = S * (-(-lt // ls) * 2 + 1)
    srh = RollingHash(SS, num=2)
    th = RollingHash(T, num=2).calc(0, len(T))

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



def main():
    S = input()
    T = input()
    print(slv(S, T))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60

class RRH():
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

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

    @staticmethod
    def gen(a, b, num):
        import random
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RRH.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



def slv(S, T):
    lt = len(T)
    ls = len(S)
    SS = S * (-(-lt // ls) * 2 + 1)
    srh = RRH(SS)
    th = RRH(T).calc(0, len(T))

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



def main():
    S = input()
    T = input()
    print(slv(S, T))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60

class RRH():
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

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

    @staticmethod
    def gen(a, b, num):
        import random
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RRH.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [293, 389, 167]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



def slv(S, T):
    lt = len(T)
    ls = len(S)
    SS = S * (-(-lt // ls) * 2 + 1)
    srh = RRH(SS)
    th = RRH(T).calc(0, len(T))

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



def main():
    S = input()
    T = input()
    print(slv(S, T))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60


def gen(a, b, num):
    import random
    result = set()
    while 1:
        while 1:
            v = random.randint(a, b)//2*2+1
            if v not in result:
                break
        for x in range(3, int(math.sqrt(v))+1, 2):
            if v % x == 0:
                break
        else:
            result.add(v)
            if len(result) == num:
                break
    return result


class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            num = ord(s[i])
            tmp = (tmp*base + num) % mod
            h[i+1] = tmp

        self.pw = pw = [1]*(len(s)+1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod

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


class RRH():
    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = gen(2, 10**3, num)
        else:
            bases = {293, 389, 167}

        MOD = 10**9+7
        self.rhs = [RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



def slv(S, T):
    lt = len(T)
    ls = len(S)
    SS = S * (-(-lt // ls) * 2 + 1)
    srh = RRH(SS)
    th = RRH(T).calc(0, len(T))

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



def main():
    S = input()
    T = input()
    print(slv(S, T))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import random
s = input()
t = input()
sl = len(s)
tl = len(t)

l = 0
r = 1500000//tl + 1
r2 = r
s *= 1499999//sl + 1
n = len(s)

base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1

def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1


while r - l > 1:
    m = l + (r-l)//2
    lt = len(t)*m
    hash2 = [0]*(lt+1)
    power2 = [1]*(lt+1)
    for i,e in enumerate(t*m):
        hash2[i+1] = (hash2[i]*base1 + ord(e))%mod1
        power2[i+1] = (power2[i]*base1)%mod1
    r_hash = hash2[-1]%mod1

    lt = len(t)*m
    flag = 0
    for i in range(len(s)-lt+1):
        if r_hash == rolling_hash(i, i+lt):
            flag = 1
            break

    if flag == 1:
        l = m
    else:
        r = m

if l*tl >= 1000000:
    print(-1)
else:
    print(l)

Submission status: Accepted

Solution code:
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

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

import sys
from fractions import gcd

sys.setrecursionlimit(1500000)

s=input()
t=input()
n=len(s)
m=len(t)
if n!=m:
    s=(m//n+2)*s
    data=Z_algorithm(t+'?'+s)
    bool=[False for i in range(0,n)]
    for i in range(m+1,m+1+n):
        if data[i]==m:
            bool[i-m-1]=True

    g=gcd(n,m)
    for i in range(0,g):
        for j in range(0,n//g):
            if not bool[i+j*g]:
                break
        else:
            print(-1)
            exit()

    ans=[[] for i in range(0,g)]
    for i in range(0,g):
        ans[i].append(bool[i])
        x=(i+m)%n
        while x!=i:
            ans[i].append(bool[x])
            x=(x+m)%n

    from itertools import groupby
    answer=0
    for i in range(0,g):
        a=groupby(ans[i])
        d=[]
        for key,group in a:
            g=len(list(group))
            d.append([key,g])
        if d:
            if d[0][0] and d[-1][0]:
                d[-1][1]+=d[0][1]
        for j in range(len(d)):
            if d[j][0]:
                answer=max(answer,d[j][1])
    print(answer)


else:
    s=2*s
    data=Z_algorithm(t+'?'+s)
    for i in range(m+1,n+m+1):
        if data[i]==m:
            print(-1)
            break
    else:
        print(0)

Submission status: Accepted

Solution code:
s = input()
t = input()

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        # i番目以降の一致文字数
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        # 一文字も一致しない場合，次の文字へ
        if j == 0:
            i += 1
            continue

        # 一致したところまでを埋める
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 1)
else:
    ss = s * 2

z = z_algorithm(t + ss * 2)
ans = 0
for i in range(n):
    c = 0
    for v in z[n + i::n]:
        if v >= n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
s = input()
t = input()

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        # i番目以降の一致文字数
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        # 一文字も一致しない場合，次の文字へ
        if j == 0:
            i += 1
            continue

        # 一致したところまでを埋める
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 1)
else:
    ss = s * 2

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
s = input()
t = input()

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        # i番目以降の一致文字数
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        # 一文字も一致しない場合，次の文字へ
        if j == 0:
            i += 1
            continue

        # 一致したところまでを埋める
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 2)
else:
    ss = s * 2

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    S = input().rstrip('\n')
    T = input().rstrip('\n')

    ns = len(S)
    nt = len(T)

    mod1 = 1000000007
    mod2 = 1000000009
    mod3 = 998244353
    b1 = 1007
    b2 = 2009
    b3 = 2999
    H1 = 0
    H2 = 0
    H3 = 0
    for i, t in enumerate(T):
        t = ord(t)
        H1 = ((H1 * b1)%mod1 + t)%mod1
        H2 = ((H2 * b2)%mod2 + t)%mod2
        H3 = ((H3 * b3)%mod3 + t)%mod3
    h1 = 0
    h2 = 0
    h3 = 0
    for i in range(nt):
        s = ord(S[i%ns])
        h1 = ((h1 * b1) % mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 + s) % mod3

    idx = []
    if h1 == H1 and h2 == H2 and h3 == H3:
        idx.append(0)
    b1_nt = pow(b1, nt, mod1)
    b2_nt = pow(b2, nt, mod2)
    b3_nt = pow(b3, nt, mod3)
    for i in range(1, ns):
        s = ord(S[(i+nt-1)%ns])
        s_prev = ord(S[i-1])
        h1 = ((h1 * b1) % mod1 - (b1_nt * s_prev)%mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 - (b2_nt * s_prev)%mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 - (b3_nt * s_prev) % mod3 + s) % mod3
        if h1 == H1 and h2 == H2 and h3 == H3:
            idx.append(i%ns)
    if len(idx) == 0:
        print(0)
        exit()
    ans = 1
    dic = {}
    for i in range(len(idx)):
        if (idx[i] - nt)%ns in dic:
            tmp = dic[(idx[i]-nt)%ns] + 1
            dic[idx[i]] = tmp
            ans = max(ans, tmp)
        else:
            dic[idx[i]] = 1
    for i in range(len(idx)):
        if (idx[i] - nt)%ns in dic:
            tmp = dic[(idx[i]-nt)%ns] + 1
            dic[idx[i]] = tmp
            ans = max(ans, tmp)
        else:
            dic[idx[i]] = 1
    ans_ = ans
    for i in range(len(idx)):
        if (idx[i] - nt)%ns in dic:
            tmp = dic[(idx[i]-nt)%ns] + 1
            dic[idx[i]] = tmp
            ans = max(ans, tmp)
        else:
            dic[idx[i]] = 1
    if ans == ans_:
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class KMP:
    def partial(self, P):
        ret = [0]
        for i in range(1, len(P)):
            j = ret[i - 1]
            while j > 0 and P[j] != P[i]:
                j = ret[j - 1]
            ret.append(j + 1 if P[j] == P[i] else j)
        return ret

    def search(self, S, P):
        partial, ret, j = self.partial(P), [], 0        
        for i in range(len(S)):
            while j > 0 and S[i] != P[j]:
                j = partial[j - 1]
            if S[i] == P[j]: j += 1
            if j == len(P): 
                ret.append(i - (j - 1))
                j = partial[j - 1]
        return ret

def main():
    S=list(map(ord,input()))
    T=list(map(ord,input()))
    N,M=len(S),len(T)
    I=KMP().search(S*(M//N+2),T)
    A=[False]*N
    B=[False]*N
    C=[0]*N
    for i in I:
        A[i%N]=True
    for i in range(N):
        if B[i]: continue
        B[i]=True
        j=i
        acc=0
        while A[j]:
            j=(j+M)%N
            acc+=1
            if B[j] and A[j]:
                C[i]=C[j]+acc
                break
            C[j]=max(C[j],acc)
            B[j]=True
        if acc and i==j:
            print(-1)
            return
        C[i]=max(C[i],acc)
    print(max(C))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        l = len(s)
        self.pw = pw = [1]*(l+1)
        self.h = h = [0]*(l+1)
        for i in range(l):
            h[i+1] = (h[i] * base + ord(s[i])) % mod
            pw[i+1] = pw[i] * base % mod

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

def main():
  s = input()
  t = input()
  ls,lt = len(s), len(t)
  m = (ls+lt-1)//ls + 1
  s *= m
  s1 = RollingHash(s, 1007, 10**9+7)
  t1 = RollingHash(t, 1007, 10**9+7)
  w = t1.get(0,lt)
  g = [None]*ls
  for i in range(ls):
    if s1.get(i, i+lt) == w:
      g[i] = (i+lt)%ls
  
  f = [None]*ls
  for i in range(ls):
    if f[i] is None:
      f[i] = ls
      q = [i]
      while q:
        if g[q[-1]] is None:
          f[q[-1]] = 0
          q.pop()
        elif f[g[q[-1]]] is None:
          q.append(g[q[-1]])
        else:
          f[q[-1]] = f[g[q[-1]]] + 1
          q.pop()
  print(max(f) if max(f) < ls else -1)
  return
  
main()

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

def Z_algorithm(s):
	l = len(s)
	res = [-1 for _ in range(l)]
	res[0] = l
	i, j = 1, 0
	while i < l:
		while i+j < l and s[j] == s[i+j]:
			j += 1
		res[i] = j

		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while i+k < l and k + res[k] < j:
				res[i+k] = res[k]
				k += 1

			i += k
			j -= k

	return res

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
ts_concat = t + " " + s_concat
z = Z_algorithm(ts_concat)

adj = [-1 for _ in range(ns)]

for i in range(1, len(z)):
	if i-nt-1 >= ns:
		break
	if z[i] == nt:
		j = i-nt-1
		if j == (j+nt)%ns:
			print(-1)
			sys.exit()
		adj[j] = (j+nt)%ns

visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

class KMP():
	def __init__(self, sentence):
		self.sentence = sent = sentence
		self.l = l = len(sent)
		self.table = table = [0 for _ in range(l+1)]
		table[0] = -1
		j = -1
		for i in range(l):
			while j >= 0 and sent[i] != sent[j]:
				j = table[j]
			j += 1
			if i < l-1 and sent[i+1] == sent[j]:
				table[i+1] = table[j]
			else:
				table[i+1] = j

	def search(self, key):
		table = self.table
		sent = self.sentence
		l = self.l
		i = 0
		res = []
		for j in range(len(key)):
			while i > -1 and sent[i] != key[j]:
				i = table[i]
			i += 1
			if i >= l:
				res.append(j-i+1)
				i = table[i]
		return res


s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s

adj = [-1 for _ in range(ns)]

kmp = KMP(t)
matches = kmp.search(s_concat)

for i in matches:
	if i >= ns:
		break
	if i == (i+nt)%ns:
		print(-1)
		sys.exit()
	adj[i] = (i+nt)%ns


visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)