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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    s += s
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 1000000009
    pm1 = [1]
    pm2 = [1]
    for i in range(2000000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    r = len(s)//n_+1
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[i%n_]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[i%n_]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[i%len(s)]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[i%len(s)]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,len(s)):
                hash1 = (hash1*pm1[1]-d[s[i-n]]*pm1[n]+d[s[i]])%mod1
                hash2 = (hash2*pm2[1]-d[s[i-n]]*pm2[n]+d[s[i]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    if l == len(s)//n_:
        print(-1)
    else:
        print(l)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    s += s
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 998343553
    pm1 = [1]
    pm2 = [1]
    for i in range(2000000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    r = len(s)//n_+1
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[i%n_]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[i%n_]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[i%len(s)]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[i%len(s)]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,len(s)):
                hash1 = (hash1*pm1[1]-d[s[i-n]]*pm1[n]+d[s[i]])%mod1
                hash2 = (hash2*pm2[1]-d[s[i-n]]*pm2[n]+d[s[i]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    if l == len(s)//n_:
        print(-1)
    else:
        print(l)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 998343553
    pm1 = [1]
    pm2 = [1]
    for i in range(1000000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    r = len(s)//n_+1
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[i%n_]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[i%n_]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[i%len(s)]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[i%len(s)]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,len(s)):
                hash1 = (hash1*pm1[1]-d[s[i-n]]*pm1[n]+d[s[i]])%mod1
                hash2 = (hash2*pm2[1]-d[s[i-n]]*pm2[n]+d[s[i]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    if l == len(s)//n_:
        print(-1)
    else:
        print(l)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
from math import ceil
s = input()
t = input()

s = s*ceil(len(t)/len(s))*4

ans = 0
ans_ = 0
j = 0
c = 0
for i in range(2*len(s)):
    if s[i%len(s)]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            if i < len(s):
                ans = max(ans,c)
            else:
                ans_ = max(ans_,c)
    else:
        j = 0
        c = 0

if ans_ > ans:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
s = input()
t = input()

s = s*ceil(len(t)/len(s))*3

ans = 0
ans_ = 0
j = 0
c = 0
for i in range(2*len(s)):
    if s[i%len(s)]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            if i < len(s):
                ans = max(ans,c)
            else:
                ans_ = max(ans_,c)
    else:
        j = 0
        c = 0

if ans_ > ans:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
s = input()
t = input()

s = s*ceil(len(t)/len(s))*2

ans = 0
ans_ = 0
j = 0
c = 0
for i in range(2*len(s)):
    if s[i%len(s)]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            if i < len(s):
                ans = max(ans,c)
            else:
                ans_ = max(ans_,c)
    else:
        j = 0
        c = 0

if ans_ > ans:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    s += s
    s += s
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 998343553
    pm1 = [1]
    pm2 = [1]
    for i in range(4000000):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    r = len(s)//n_+1
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[i%n_]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[i%n_]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[i%len(s)]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[i%len(s)]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,len(s)):
                hash1 = (hash1*pm1[1]-d[s[i-n]]*pm1[n]+d[s[i]])%mod1
                hash2 = (hash2*pm2[1]-d[s[i-n]]*pm2[n]+d[s[i]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    if l == len(s)//n_:
        print(-1)
    else:
        print(l)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

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

ls = len(s)
lt = len(t)
f = True
buf = 0
if lt >= ls:
    for i in range(1, lt + 1):
        if t[i - 1] == s[(i - 1) % ls]:
            pass
        else:
            print(0)
            exit()
    print(-1)
    exit()

else:
    table = [0] * (ls + 1)
    for i in range(1, ls + 1):
        if s[i - 1] == t[table[i - 1] % lt]:
            table[i] = table[i - 1] + 1
        elif f:
            buf = table[i - 1]
            f = False
    tm = max(table)
    print(max(tm, table[ls] + buf) // lt)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    k = I()
    x,y = LI()
    while abs(x)+abs(y) != k:
        if x < 0:
            x += k
        elif x > 0:
            x -= k
        else:
            if y < 0:
                y += k
            else:
                y -= k
        print(x,y)

    return

#F
def F():
    d = {}
    alp = "abcdefghijklmnopqrstuvwxyz"
    for i in range(len(alp)):
        d[alp[i]] = i+1
    m = len(alp)+1
    s = S()
    t = S()
    while len(s) < len(t):
        s += s
    s += s
    s += s
    l = 0
    r = 1
    mod1 = 1000000007
    mod2 = 998343553
    pm1 = [1]
    pm2 = [1]
    for i in range(5000002):
        pm1.append(pm1[-1]*m%mod1)
        pm2.append(pm2[-1]*m%mod2)
    n_ = len(t)
    r = len(s)//n_+1
    while r-l > 1:
        mid = (r+l)//2
        n = n_*mid
        h1 = 0
        h2 = 0
        for i in range(n):
            h1 += d[t[i%n_]]*pm1[n-1-i]%mod1
            h1 %= mod1
            h2 += d[t[i%n_]]*pm2[n-1-i]%mod2
            h2 %= mod2
        hash1 = 0
        hash2 = 0
        for i in range(n):
            hash1 += d[s[i%len(s)]]*pm1[n-1-i]%mod1
            hash1 %= mod1
            hash2 += d[s[i%len(s)]]*pm2[n-1-i]%mod2
            hash2 %= mod2
        if h1 == hash1 and h2 == hash2:
            l = mid
        else:
            for i in range(n,len(s)):
                hash1 = (hash1*pm1[1]-d[s[i-n]]*pm1[n]+d[s[i]])%mod1
                hash2 = (hash2*pm2[1]-d[s[i-n]]*pm2[n]+d[s[i]])%mod2
                if h1 == hash1 and h2 == hash2:
                    l = mid
                    break
            else:
                r = mid
    if l == len(s)//n_:
        print(-1)
    else:
        print(l)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from itertools import cycle
from collections import defaultdict
import re

s,t = input(),input()

def check_inf(s,t):
    g = gcd(len(s),len(t))
    s0 = s[:g]
    t0 = t[:g]
    i = (s0*2).startswith(t0)
    if i < 0:
        return False
    return s == s0*(len(s)//g) and t == t0*(len(t)//g)

if check_inf(s,t):
    print(-1)
    exit()

L = len(t)

indices = defaultdict(list)
for m in re.finditer('(?='+t+')', s*2):
    i = m.start()
    indices[i%L].append(i)
best = 0
for l in indices.values():
    run = 0
    prev = -L-1
    for i in l:
        if i == prev + L:
            run += 1
        else:
            best = max(best,run)
            run = 1
        prev = i
    best = max(best, run)

print(best)

Submission status: Wrong Answer

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

ls = len(s)
lt = len(t)
f = True
buf = 0
table = [0] * max((ls + 1), (lt + 1))
if lt > ls:
    for i in range(1, lt + 1):
        if t[i - 1] == s[table[i - 1] % ls]:
            table[i] = table[i - 1] + 1
        else:
            print(0)
            exit()
    print(-1)
    exit()

else:
    for i in range(1, ls + 1):
        if s[i - 1] == t[table[i - 1] % lt]:
            table[i] = table[i - 1] + 1
        elif f:
            buf = table[i - 1]
            f = False
    tm = max(table)
    print(max(tm, table[ls] + buf) // lt)

Submission status: Wrong Answer

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

ls = len(s)
lt = len(t)
f = True
buf = 0
table = [0] * max((ls + 1), (lt + 1))
if lt > ls:
    lt, ls = ls, lt
    s, t = t, s
    for i in range(1, lt + 1):
        if t[i - 1] == s[table[i - 1] % ls]:
            table[i] = table[i - 1] + 1
        else:
            print(0)
            exit()
    print(-1)
    exit()

else:
    for i in range(1, ls + 1):
        if s[i - 1] == t[table[i - 1] % lt]:
            table[i] = table[i - 1] + 1
        elif f:
            buf = table[i - 1]
            f = False
    tm = max(table)
    print(max(tm, table[ls] + buf) // lt)

Submission status: Wrong Answer

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

S = s
while len(S) < len(t):
    S = S + s

s = S+S

ans = 0
j = 0
c = 0
for i in range(len(s)):
    if s[i]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            ans = max(ans,c)
    else:
        j = 0
        c = 0


s = s+S
ans_ = 0
j = 0
c = 0
for i in range(len(s)):
    if s[i]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            ans_ = max(ans_,c)
    else:
        j = 0
        c = 0

if ans != ans_:
    ans = -1

print(ans)

Submission status: Wrong Answer

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

S = s
while len(S) < len(t):
    S = S + s

s = S+S

ans = 0
j = 0
c = 0
for i in range(len(s)):
    if s[i]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            ans = max(ans,c)
    else:
        j = 0
        c = 0


s = s+s
ans_ = 0
j = 0
c = 0
for i in range(len(s)):
    if s[i]==t[j]:
        j += 1
        if j == len(t):
            j = 0
            c += 1
            ans_ = max(ans_,c)
    else:
        j = 0
        c = 0

if ans != ans_:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
s*=(len(t)+len(s)-1)//len(s)
ans=0
S=s*3
now=0
i=0
while(i<len(S)):
    if S[i]==t[0] and S[i:i+len(t)]==t:
        now+=1
        i+=len(t)
    else:
        ans=max(ans,now)
        now=0
        i+=1
ans=max(ans,now)
ans1=0
S=s*4
now1=0
i=0
while(i<len(S)):
    if S[i]==t[0] and S[i:i+len(t)]==t:
        now1+=1
        i+=len(t)
    else:
        ans1=max(ans1,now1)
        now1=0
        i+=1
ans1=max(ans1,now1)
if ans1>ans:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

ls = len(s)
lt = len(t)
f = True
buf = 0
if ls > lt:
    lt, ls = ls, lt
    s, t = t, s
    table = [0] * (lt + 1)
    for i in range(1, lt + 1):
        if t[i - 1] == s[table[i - 1] % ls]:
            table[i] = table[i - 1] + 1
        elif f:
            print(0)
            exit()
    else:
        print(-1)
        exit()

else:
    table = [0] * (lt + 1)
    for i in range(1, lt + 1):
        if t[i - 1] == s[table[i - 1] % ls]:
            table[i] = table[i - 1] + 1
        elif f:
            buf = table[i - 1]
            f = False
    
    if table[lt] == lt:
        print(-1)
    else:
        tm = max(table)
        print(max(tm, table[lt] + buf) // ls)