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: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1008
        self.mod1 = 10**9 + 7
        self.mod2 = 999999937 
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = ((self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod1 + self.mod1) % self.mod1
        t2 = ((self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2 + self.mod2) % self.mod2
        return (t1, t2)

t_tmp = input().rstrip()
s = input().rstrip()

# Same character goes to infinity
if t_tmp.count(t_tmp[0]) == len(t_tmp) and s.count(s[0]) == len(s) and s[0] == t_tmp[0]:
    print(-1)
    exit()

t = ""
while len(t) < len(s):
    t += t_tmp
max_ans = (len(t) * 2) // len(s)
t = t * 3
lent = len(t)
lens = len(s)

RHt = RollingHash(t)
RHs = RollingHash(s)
s_hash = RHs.get(0, lens)

match = [0] * (lent - lens + 1)
for i in range(lent - lens + 1):
    if RHt.get(i, i+lens) == s_hash:
        match[i] = 1
ans = max(match[:lens])
for i in range(len(match) - lens):
    if match[i+lens] != 0:
        match[i+lens] += match[i]
        ans = max(ans, match[i+lens])

if ans > max_ans:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1008
        self.mod1 = 10**9 + 7
        self.mod2 = 999999937 
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = ((self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod1 + self.mod1) % self.mod1
        t2 = ((self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2 + self.mod2) % self.mod2
        return (t1, t2)

t_tmp = input().rstrip()
s = input().rstrip()

t = ""
while len(t) < len(s):
    t += t_tmp
t = t * 2
max_ans = len(t) // len(s)
lent = len(t)
lens = len(s)

RHt = RollingHash(t)
RHs = RollingHash(s)
s_hash = RHs.get(0, lens)

match = [0] * (lent - lens + 1)
for i in range(lent - lens + 1):
    if RHt.get(i, i+lens) == s_hash:
        match[i] = 1
ans = max(match[:lens])
for i in range(len(match) - lens):
    if match[i+lens] != 0:
        match[i+lens] += match[i]
        ans = max(ans, match[i+lens])

if ans >= max_ans:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1013
        self.mod1 = 10**9 + 7
        self.mod2 = 999999937 
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = ((self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod1 + self.mod1) % self.mod1
        t2 = ((self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2 + self.mod2) % self.mod2
        return (t1, t2)

t_tmp = input().rstrip()
s = input().rstrip()

t = ""
while len(t) < len(s):
    t += t_tmp
t = t * 3
max_ans = len(t) // len(s)
lent = len(t)
lens = len(s)

RHt = RollingHash(t)
RHs = RollingHash(s)
s_hash = RHs.get(0, lens)

match = [0] * (lent - lens + 1)
for i in range(lent - lens + 1):
    if RHt.get(i, i+lens) == s_hash:
        match[i] = 1
ans = max(match[:lens])
for i in range(len(match) - lens):
    if match[i+lens] != 0:
        match[i+lens] += match[i]
        ans = max(ans, match[i+lens])

if ans >= max_ans:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1013
        self.mod1 = 10**9 + 7
        self.mod2 = 999999937 
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

    def get_weak(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        return t1
    
t_tmp = input().rstrip()
s = input().rstrip()

t = ""
while len(t) < len(s):
    t += t_tmp
max_ans = len(t) * 2 // len(s)
t = t * 3
lent = len(t)
lens = len(s)

RHt = RollingHash(t)
RHs = RollingHash(s)
s_hash = RHs.get_weak(0, lens)

match = [0] * (lent - lens + 1)
for i in range(lent - lens + 1):
    if RHt.get_weak(i, i+lens) == s_hash:
        match[i] = 1
ans = max(match[:lens])
for i in range(len(match) - lens):
    if match[i+lens] != 0:
        match[i+lens] += match[i]
        ans = max(ans, match[i+lens])

if ans >= max_ans:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1013
        self.mod1 = 10**9 + 7
        self.mod2 = 999999937 
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)
    
t_tmp = input().rstrip()
s = input().rstrip()

t = ""
while len(t) < len(s):
    t += t_tmp
max_ans = len(t) * 2 // len(s)
t = t * 3
lent = len(t)
lens = len(s)

RHt = RollingHash(t)
RHs = RollingHash(s)
s_hash = RHs.get(0, lens)

match = [0] * (lent - lens + 1)
for i in range(lent - lens + 1):
    if RHt.get(i, i+lens) == s_hash:
        match[i] = 1
ans = max(match[:lens])
for i in range(len(match) - lens):
    if match[i+lens] != 0:
        match[i+lens] += match[i]
        ans = max(ans, match[i+lens])

if ans > max_ans:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1013
        self.mod1 = 10**9 + 7
        self.mod2 = 999999937 
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)
    
t_tmp = input().rstrip()
s = input().rstrip()

t = ""
while len(t) < len(s):
    t += t_tmp
t = t * 3

RHt = RollingHash(t)
RHs = RollingHash(s)
w = len(s)
s_hash = RHs.get(0, w)

infinity = True
lent = len(t)
lens = len(s)
for i in range(max(len(t)+1, len(s)+1)):
    if t[i%lent] != s[i%lens]:
        infinity = False
        break
if infinity:
    print(-1)
    exit()

match = [0] * (len(t) - len(s) + 1)
# print(match, t, s)
for i in range(len(t) - len(s) + 1):
    if RHt.get(i, i+w) == s_hash:
        match[i] = 1
ans = max(match[:w])
for i in range(len(match) - w):
    if match[i+w] != 0:
        match[i+w] += match[i]
        ans = max(ans, match[i+w])
# print(match)

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1013
        self.mod1 = 10**9 + 7
        self.mod2 = 999999937 
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)
    
t_tmp = input().rstrip()
s = input().rstrip()

t = ""
while len(t) < len(s):
    t += t_tmp
t = t + t

RHt = RollingHash(t)
RHs = RollingHash(s)
w = len(s)
s_hash = RHs.get(0, w)

infinity = True
lent = len(t)
lens = len(s)
for i in range(max(len(t)+1, len(s)+1)):
    if t[i%lent] != s[i%lens]:
        infinity = False
        break
if infinity:
    print(-1)
    exit()

match = [0] * (len(t) - len(s) + 1)
# print(match, t, s)
for i in range(len(t) - len(s) + 1):
    if RHt.get(i, i+w) == s_hash:
        match[i] = 1
ans = max(match[:w])
for i in range(len(match) - w):
    if match[i+w] != 0:
        match[i+w] += match[i]
    ans = max(ans, match[i+w])

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)
    
t_tmp = input().rstrip()
s = input().rstrip()

t = ""
while len(t) < len(s):
    t += t_tmp
t = t + t

RHt = RollingHash(t)
RHs = RollingHash(s)
w = len(s)
s_hash = RHs.get(0, w)

infinity = True
lent = len(t)
lens = len(s)
for i in range(max(len(t)+1, len(s)+1)):
    if t[i%lent] != s[i%lens]:
        infinity = False
        break
if infinity:
    print(-1)
    exit()

match = [0] * (len(t) - len(s) + 1)
# print(match, t, s)
for i in range(len(t) - len(s) + 1):
    if RHt.get(i, i+w) == s_hash:
        match[i] = 1
ans = max(match[:w])
for i in range(len(match) - w):
    if match[i+w] != 0:
        match[i+w] += match[i]
    ans = max(ans, match[i+w])

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)
    
t_tmp = input().rstrip()
s = input().rstrip()

t = ""
while len(t) < len(s):
    t += t_tmp

RHt = RollingHash(t)
RHs = RollingHash(s)
w = len(s)
s_hash = RHs.get(0, w)

infinity = True
lent = len(t)
lens = len(s)
for i in range(max(len(t)+1, len(s)+1)):
    if t[i%lent] != s[i%lens]:
        infinity = False
        break
if infinity:
    print(-1)
    exit()

match = [0] * (len(t) - len(s) + 1)
for i in range(len(t) - len(s) + 1):
    if RHt.get(i, i+w) == s_hash:
        match[i] = 1
ans = max(match[:w])
for i in range(len(match) - w):
    if match[i+w] != 0:
        match[i+w] += match[i]
    ans = max(ans, match[i+w])

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)
    
t = input().rstrip()
t = t + t
RHt = RollingHash(t)

s = input().rstrip()
RHs = RollingHash(s)
w = len(s)
s_hash = RHs.get(0, w)

infinity = True
lent = len(t)
lens = len(s)
for i in range(max(len(t)+1, len(s)+1)):
    if t[i%lent] != s[i%lens]:
        infinity = False
        break
if infinity:
    print(-1)
    exit()

match = [0] * (len(t) - len(s) + 1)
for i in range(len(t) - len(s) + 1):
    if RHt.get(i, i+w) == s_hash:
        match[i] = 1
ans = 0
for i in range(len(match) - w):
    if match[i+w] != 0:
        match[i+w] += match[i]
    ans = max(ans, match[i+w])

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)
    
t = input().rstrip()
t = t + t
RHt = RollingHash(t)

s = input().rstrip()
RHs = RollingHash(s)
w = len(s)
s_hash = RHs.get(0, w)

infinity = True
for t_char, s_char in zip(t + t[0], s + s[0]):
    if t_char != s_char:
        infinity = False
        break
if infinity:
    print(-1)
    exit()

match = [0] * (len(t) - len(s) + 1)
for i in range(len(t) - len(s) + 1):
    if RHt.get(i, i+w) == s_hash:
        match[i] = 1
ans = 0
for i in range(len(match) - w):
    if match[i+w] != 0:
        match[i+w] += match[i]
    ans = max(ans, match[i+w])

print(ans)

Submission status: Wrong Answer

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

def z_algorithm(s):
    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i or visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = ""
while True:
    new_s += s
    if len(new_s) > len(t):
        s = new_s
        break
print(1)
exit()

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)

Submission status: Wrong Answer

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

def z_algorithm(s):
    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i or visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = ""
while True:
    new_s += s
    if len(new_s) > len(t):
        s = new_s
        break

s = s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))
'''
s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)
'''
print(ans1)

Submission status: Wrong Answer

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

def z_algorithm(s):
    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i or visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = ""
while True:
    new_s += s
    if len(new_s) > len(t):
        s = new_s
        break

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))
'''
s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)
'''
print(ans1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)


s = input()
t = input()

def z_algorithm(s):

    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

new_s = ""
while True:
    new_s += s
    if len(new_s) >= len(t):
        s = new_s
        break

def solve(i, li):
    ans = 0
    if i < 0 or len(li) <= i:
        return 0
    if visited[i]:
        return 0
    if li[i] >= len(t):
        visited[i] = True
        ans += 1 + solve(i+len(t), li)
    if li[i] < len(t):
        visited[i] = True
    return ans

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
s1 = s * max(2, (len(t) - 1) // len(s) + 1)

ans = 0
mult = 1
while True:
    if s1.count(t * mult) > 0:
        mult += 1
    else:
        ans = mult - 1
        break

s2 = s1 * 2
if s2.count(t * mult) > 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
sys.setrecursionlimit(10*6)
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


class Graph(object):
    # 無向グラフを仮定する。
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。

        self.E[始点]は、[終点, 重み]を要素としたリスト
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def tree_diameter(g):
    """木gの直径を求める
    """
    def visit(prev, v):
        """
        prev: 一つ手前の頂点
        v: 今の頂点
        """
        most_t, most_w = 0, 0   # 最も遠い頂点を控える
        for dst, weight in g.E[v]:  # 頂点vから伸びる枝の中で
            if dst == prev:        # 一つ手前のprevに伸びる枝を覗いて
                continue
            t, w = visit(v, dst)  # 再帰的に求める。返り値は最も遠い頂点とそこまでの距離
            w += weight           # 今の枝の距離を加えて
            if most_w < w:        # 遠さが更新されれば
                most_t, most_w = t, w  # 更新
        return most_t, most_w

    far_v, dist = visit(-1, 0)
    far_v, dist = visit(-1, far_v)
    return dist


def solve(s: str, t: str):
    S = len(s)
    T = len(t)

    # Sの方が長くなるように
    if T > S:
        s *= int(math.ceil(T/S))

    s2 = s+s
    match = zfindall(s2, t)

    if len(match) == 0:
        print(0)
        return

    print(-1)
    # g = Graph(S)
    # for m in match:
    #     g.add_edge([m % S, (m+T) % S])

    # d = tree_diameter(g)
    # print(d+1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S=list(input())
T=list(input())
len0=len(S)
while len(S)<len(T):
    S=S+S

S=S+S

p=26
mod=(1<<30)+1# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)

Submission status: Wrong Answer

Solution code:
S=list(input())
T=list(input())
len0=len(S)
while len(S)<len(T):
    S=S+S

S=S+S

p=26
mod=(1<<21)+1# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)

Submission status: Wrong Answer

Solution code:
S=list(input())
T=list(input())
len0=len(S)
while len(S)<len(T)*2:
    S=S+S

S=S+S

p=26
mod=(1<<20)+1# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)