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:
def main():
    import sys
    input = sys.stdin.readline

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

    ns = len(S)
    nt = len(T)
    S = ''.join([S] * ((nt-1)//ns+1))
    S = ''.join([S, S, S, S])
    ns = len(S)

    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])
        h1 = ((h1 * b1) % mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 + s) % mod3

    idx = [-10**10]
    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(nt, ns):
        s = ord(S[i])
        s_prev = ord(S[i-nt])
        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:
            if i-nt+1 - idx[-1] >= nt:
                idx.append(i-nt+1)
    if len(idx) == 1:
        print(0)
        exit()
    tmp = 1
    ans = 1
    ans_ = 1
    ns_ = ns // 2
    for i in range(1, len(idx)):
        if idx[i] - idx[i-1] == nt:
            tmp += 1
            if idx[i] <= ns_-nt:
                ans = max(ans, tmp)
                ans_ = max(ans_, tmp)
            else:
                ans_ = max(ans_, tmp)
        else:
            tmp = 1
    if ans_ == ans:
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    ns = len(S)
    nt = len(T)
    S = ''.join([S] * ((nt-1)//ns+1))
    S = ''.join([S, S, S, S])
    ns = len(S)

    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])
        h1 = ((h1 * b1) % mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 + s) % mod3

    idx = [-10**10]
    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(nt, ns):
        s = ord(S[i])
        s_prev = ord(S[i-nt])
        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:
            if i-nt+1 - idx[-1] >= nt:
                idx.append(i-nt+1)
    if len(idx) == 1:
        print(0)
        exit()
    tmp = 1
    ans = 1
    ans_ = 1
    ns_ = ns // 2
    for i in range(1, len(idx)):
        if idx[i] - idx[i-1] == nt:
            tmp += 1
            if idx[i] < ns_-nt:
                ans = max(ans, tmp)
                ans_ = max(ans_, tmp)
            else:
                ans_ = max(ans_, tmp)
        else:
            tmp = 1
    if ans_ == ans:
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    ns = len(S)
    nt = len(T)
    S = ''.join([S] * ((nt-1)//ns+1))
    S = ''.join([S, S, S, S])
    ns = len(S)

    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])
        h1 = ((h1 * b1) % mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 + s) % mod2
        h3 = ((h3 * b3) % mod3 + s) % mod3

    idx = [-10**10]
    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(nt, ns):
        s = ord(S[i])
        s_prev = ord(S[i-nt])
        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:
            if i-nt+1 - idx[-1] >= nt:
                idx.append(i-nt+1)
    if len(idx) == 1:
        print(0)
        exit()
    tmp = 1
    ans = 1
    ans_ = 1
    ns_ = ns // 2
    for i in range(1, len(idx)):
        if idx[i] - idx[i-1] == nt:
            tmp += 1
            if idx[i] < ns_:
                ans = max(ans, tmp)
                ans_ = max(ans_, tmp)
            else:
                ans_ = max(ans_, tmp)
        else:
            tmp = 1
    if ans_ == ans:
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    ns = len(S)
    nt = len(T)
    S = ''.join([S] * ((nt-1)//ns+1))
    S = ''.join([S, S, S, S])
    ns = len(S)

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

    idx = [-10**10]
    if h1 == H1 and h2 == H2:
        idx.append(0)
    b1_nt = pow(b1, nt, mod1)
    b2_nt = pow(b2, nt, mod2)
    for i in range(nt, ns):
        s = ord(S[i])
        s_prev = ord(S[i-nt])
        h1 = ((h1 * b1) % mod1 - (b1_nt * s_prev)%mod1 + s) % mod1
        h2 = ((h2 * b2) % mod2 - (b2_nt * s_prev)%mod2 + s) % mod2
        if h1 == H1 and h2 == H2:
            if i-nt+1 - idx[-1] >= nt:
                idx.append(i-nt+1)
    if len(idx) == 1:
        print(0)
        exit()
    tmp = 1
    ans = 1
    ans_ = 1
    ns_ = ns // 2
    for i in range(1, len(idx)):
        if idx[i] - idx[i-1] == nt:
            tmp += 1
            if idx[i] < ns_:
                ans = max(ans, tmp)
                ans_ = max(ans_, tmp)
            else:
                ans_ = max(ans_, tmp)
        else:
            tmp = 1
    if ans_ == ans:
        print(ans)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [-1] * (self.N + 1)
        j = 0
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search_all(self, S):
        i = m = 0
        A = []
        while m + i < len(S):
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

    def search(self, S):
        i = m = 0
        while m + i < len(S):
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                return m
            m += i - self.T[i]
            i = max(0, self.T[i])
        return None

def main():
    S=list(map(ord,input()))
    T=list(map(ord,input()))
    N,M=len(S),len(T)
    I=KMP(T).search_all(S*(M//N+2))
    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]=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: Wrong Answer

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [-1] * (self.N + 1)
        j = 0
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search_all(self, S):
        i = m = 0
        A = []
        while m + i < len(S):
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

    def search(self, S):
        i = m = 0
        while m + i < len(S):
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                return m
            m += i - self.T[i]
            i = max(0, self.T[i])
        return None

def main():
    S=list(map(ord,input()))
    T=list(map(ord,input()))
    N,M=len(S),len(T)
    I=KMP(T).search_all(S*(M//N+2))
    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]:
                C[i]=C[j]+acc
                break
            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: Wrong Answer

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [-1] * (self.N + 1)
        j = 0
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search_all(self, S):
        i = m = 0
        A = []
        while m + i < len(S):
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

    def search(self, S):
        i = m = 0
        while m + i < len(S):
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                return m
            m += i - self.T[i]
            i = max(0, self.T[i])
        return None

def main():
    S=list(map(ord,input()))
    T=list(map(ord,input()))
    N,M=len(S),len(T)
    I=KMP(T).search_all(S*((M-1)//N+2))
    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]:
                C[i]=C[j]+acc
                break
            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: Wrong Answer

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [-1] * (self.N + 1)
        j = 0
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search_all(self, S):
        i = m = 0
        A = []
        while m + i < len(S):
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

    def search(self, S):
        i = m = 0
        while m + i < len(S):
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                return m
            m += i - self.T[i]
            i = max(0, self.T[i])
        return None

def main():
    S=list(map(ord,input()))
    T=list(map(ord,input()))
    N,M=len(S),len(T)
    I=KMP(T).search_all(S*(M//N+1))
    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]:
                C[i]=C[j]+acc
                break
            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: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class KMP:
    def __init__(self, needle):
        """
        https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
        :param typing.Sequence needle: 何を検索するか
        """
        self._needle = needle
        kmp = [0] * (len(needle) + 2)
        kmp[0] = -1
        kmp[1] = 0
        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                kmp[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = kmp[j]
            else:
                kmp[i] = 0
                i += 1
        self._kmp = kmp

    def index_of(self, haystack, m=0, i=0):
        """
        haystack の何番目に needle があるか。見つからなければ -1
        :param typing.Sequence haystack: 何から検索するか
        :param int m: The position of the current character in haystack
        :param int i: The position of the current character in needle
        :rtype: int
        """
        while m + i < len(haystack):
            if self._needle[i] == haystack[m + i]:
                i += 1
                if i == len(self._needle):
                    return m
            else:
                m += i - self._kmp[i]
                if i > 0:
                    i = self._kmp[i]
        return -1

    def search(self, haystack):
        """
        ret[i]: haystack[i:i+len(needle)] == needle
        :param typing.Sequence haystack: 何から検索するか
        :rtype: list of bool
        """
        ret = [False] * len(haystack)
        m = 0
        i = 0
        while m + i < len(haystack):
            m = self.index_of(haystack, m=m, i=i)
            if m < 0:
                break
            ret[m] = True
            m += len(self._needle) - self._kmp[len(self._needle) - 1] - 1
            i = max(0, self._kmp[len(self._needle) - 1])
        return ret


def test(t, s):
    ret = []
    for i in range(len(s)):
        ret.append(s[i:i + len(t)] == t)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

# kmp = KMP(T)
# print(kmp.search(S))

S *= 4
while len(S) < len(T) * 4:
    S *= 2

kmp = KMP(T)
idx = kmp.search(S)
ans = 0
for k in range(len(T)):
    i = k
    cnt = 0
    while i < len(idx):
        if idx[i]:
            cnt += 1
        else:
            ans = max(cnt, ans)
            cnt = 0
        i += len(T)
    ans = max(cnt, ans)
if len(T) * ans > len(S) // 4 * 3:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class KMP:
    def __init__(self, needle):
        """
        https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
        :param typing.Sequence needle: 何を検索するか
        """
        self._needle = needle
        kmp = [0] * (len(needle) + 2)
        kmp[0] = -1
        kmp[1] = 0
        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                kmp[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = kmp[j]
            else:
                kmp[i] = 0
                i += 1
        self._kmp = kmp

    def index_of(self, haystack, m=0, i=0):
        """
        haystack の何番目に needle があるか。見つからなければ -1
        :param typing.Sequence haystack: 何から検索するか
        :param int m: The position of the current character in haystack
        :param int i: The position of the current character in needle
        :rtype: int
        """
        while m + i < len(haystack):
            if self._needle[i] == haystack[m + i]:
                i += 1
                if i == len(self._needle):
                    return m
            else:
                m += i - self._kmp[i]
                if i > 0:
                    i = self._kmp[i]
        return -1

    def search(self, haystack):
        """
        ret[i]: haystack[i:i+len(needle)] == needle
        :param typing.Sequence haystack: 何から検索するか
        :rtype: list of bool
        """
        ret = [False] * len(haystack)
        m = 0
        i = 0
        while m + i < len(haystack):
            m = self.index_of(haystack, m=m, i=i)
            if m < 0:
                break
            ret[m] = True
            m += len(self._needle) - self._kmp[len(self._needle) - 1] - 1
            i = max(0, self._kmp[len(self._needle) - 1])
        return ret


def test(t, s):
    ret = []
    for i in range(len(s)):
        ret.append(s[i:i + len(t)] == t)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

# kmp = KMP(T)
# print(kmp.search(S))

while len(S) < len(T) * 4:
    S *= 2

kmp = KMP(T)
idx = kmp.search(S)
ans = 0
for k in range(len(T)):
    i = k
    cnt = 0
    while i < len(idx):
        if idx[i]:
            cnt += 1
        else:
            ans = max(cnt, ans)
            cnt = 0
        i += len(T)
    ans = max(cnt, ans)
if len(T) * ans > len(S) // 4 * 3:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class KMP:
    def __init__(self, needle):
        """
        https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
        :param typing.Sequence needle: 何を検索するか
        """
        self._needle = needle
        kmp = [0] * (len(needle) + 2)
        kmp[0] = -1
        kmp[1] = 0
        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                kmp[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = kmp[j]
            else:
                kmp[i] = 0
                i += 1
        self._kmp = kmp

    def index_of(self, haystack, m=0, i=0):
        """
        haystack の何番目に needle があるか。見つからなければ -1
        :param typing.Sequence haystack: 何から検索するか
        :param int m: The position of the current character in haystack
        :param int i: The position of the current character in needle
        :rtype: int
        """
        while m + i < len(haystack):
            if self._needle[i] == haystack[m + i]:
                i += 1
                if i == len(self._needle):
                    return m
            else:
                m += i - self._kmp[i]
                if i > 0:
                    i = self._kmp[i]
        return -1

    def search(self, haystack):
        """
        ret[i]: haystack[i:i+len(needle)] == needle
        :param typing.Sequence haystack: 何から検索するか
        :rtype: list of bool
        """
        ret = [False] * len(haystack)
        m = 0
        i = 0
        while m + i < len(haystack):
            m = self.index_of(haystack, m=m, i=i)
            if m < 0:
                break
            ret[m] = True
            m += len(self._needle) - self._kmp[len(self._needle) - 1] - 1
            i = max(0, self._kmp[len(self._needle) - 1])
        return ret


def test(t, s):
    ret = []
    for i in range(len(s)):
        ret.append(s[i:i + len(t)] == t)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

# kmp = KMP(T)
# print(kmp.search(S))

while len(S) < len(T) * 4:
    S *= 2

kmp = KMP(T)
idx = kmp.search(S)
ans = 0
for k in range(len(T)):
    i = k
    cnt = 0
    while i < len(idx):
        if idx[i]:
            cnt += 1
        else:
            ans = max(cnt, ans)
            cnt = 0
        i += len(T)
    ans = max(cnt, ans)
if len(T) * ans > len(S) // 2:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
from math import ceil
import sys

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

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

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

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
#print(s_concat)
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [[] for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i].append((i+nt)%ns)
		adj[(i+nt)%ns].append(i)

#print(adj)
visited = [False for _ in range(ns)]

def dfs(x):
	cnt = 0
	visited[x] = True
	stack = [x]
	while stack:
		l = stack.pop()
		for v in adj[l]:
			if not visited[v]:
				visited[v] = True
				cnt += 1
				stack.append(v)
	return cnt

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

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

Submission status: Wrong Answer

Solution code:
# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
from math import ceil

BASE, MOD = 109912812544744553, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

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

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)
while len(s_concat) < ns + nt - 1:
	s_concat += s
#print(s_concat)
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)

adj = [[] for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == rh_t.get(0, nt):
		adj[i].append((i+nt)%ns)
		adj[(i+nt)%ns].append(i)

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

def dfs(x):
	cnt = 0
	visited[x] = True
	stack = [x]
	while stack:
		l = stack.pop()
		for v in adj[l]:
			if not visited[v]:
				visited[v] = True
				cnt += 1
				stack.append(v)
	return cnt

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

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

Submission status: Wrong Answer

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

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

flag_inf = False
count = 0
for i in range(len(s) // len(t)):
    start = i * len(t)
    end = start + len(t)
    if s[start:end] == t:
        count += 1
    else:
        break
else:
    if len(s) % len(t) == 0:
        flag_inf = True
    if len(set(s)) == len(set(t)) == 1:
        flag_inf = True

s_inv = s[::-1]
t_inv = t[::-1]
count_inv = 0
for i in range(len(s) // len(t)):
    start = i * len(t)
    end = start + len(t)
    if s_inv[start:end] == t_inv:
        count_inv += 1
    else:
        break

if flag_inf:
    print(-1)
else:
    print(count + count_inv)

Submission status: Wrong Answer

Solution code:
# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
from math import ceil

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

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

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)
while len(s_concat) < ns + nt - 1:
	s_concat += s
#print(s_concat)
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)

adj = [[] for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == rh_t.get(0, nt):
		adj[i].append((i+nt)%ns)
		adj[(i+nt)%ns].append(i)

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

def dfs(x):
	cnt = 0
	visited[x] = True
	stack = [x]
	while stack:
		l = stack.pop()
		for v in adj[l]:
			if not visited[v]:
				visited[v] = True
				cnt += 1
				stack.append(v)
	return cnt

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

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

Submission status: Wrong Answer

Solution code:

S=input()
T=input()

  
S*=3;
l=0
r=len(S)//len(T)
while(l!=r):
  z=(l+r+1)//2
  if(T*z in S):
    l=z
  else:
    r=z-1
    
if(T*(l+1) in S*2):
   print(-1)
else:
  print(l)

Submission status: Wrong Answer

Solution code:

S=input()
T=input()

  
S6=S*6
S*=3;
l=0
r=len(S)//len(T)
while(l!=r):
  z=(l+r+1)//2
  if(T*z in S):
    l=z
  else:
    r=z-1
    
if(T*(l+1) in S6):
   print(-1)
else:
  print(l)

Submission status: Wrong Answer

Solution code:

S=input()
T=input()

  
S4=S*4
S*=3;
l=0
r=len(S)//len(T)
while(l!=r):
  z=(l+r+1)//2
  if(T*z in S):
    l=z
  else:
    r=z-1
    
if(T*(l+1) in S4):
   print(-1)
else:
  print(l)

Submission status: Wrong Answer

Solution code:

def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
S=input()
T=input()
g=gcd(len(S),len(T))

if(S[:g]*(len(S)//g)==S and T[:g]*(len(T)//g)==T and S[:gcd(len(S),len(T))]==T[:gcd(len(S),len(T))]):
  print(-1)
  exit()
  
  
S*=3;
l=0
r=len(S)//len(T)
while(l!=r):
  z=(l+r+1)//2
  if(T*z in S):
    l=z
  else:
    r=z-1
print(l)

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
S=input()
T=input()
g=gcd(len(S),len(T))

if(S[:g]*(len(S)//g)==S and T[:g]*(len(T)//g)==T and S[:gcd(len(S),len(T))]==T[:gcd(len(S),len(T))]):
  print(-1)
  exit()
  
  
S*=2;
l=0
r=len(S)//len(T)
while(l!=r):
  z=(l+r+1)//2
  if(T*z in S):
    l=z
  else:
    r=z-1
print(l)

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
S=input()
T=input()
if(S[:gcd(len(S),len(T))]==T[:gcd(len(S),len(T))]):
  print(-1)

Submission status: Wrong Answer

Solution code:

def search_rolling_hash(S, T):
    base = 123
    mod = 1007
    n, m = len(S), len(T)
    rolling_hash = [0]*(n-m+1)  
    rolling_hash[0] = ord(S[0])
    b_m = pow(base, m, mod)
    T_hash = ord(T[0])
    start_index = []
    for i in range(1, m):
        rolling_hash[0]*=base
        rolling_hash[0]+=ord(S[i])
        rolling_hash[0]%=mod
        T_hash = (T_hash*base+ord(T[i]))%mod
    if rolling_hash[0] == T_hash: start_index.append(0)
    for i in range(1, ls):
        rolling_hash[i] = (rolling_hash[i-1]*base-ord(S[i-1])*b_m+ord(S[i+m-1]))%mod
        if rolling_hash[i] == T_hash: start_index.append(i)
    return start_index
import sys
s = input()
t = input()
ls, lt = len(s), len(t)
S = s*(lt//ls+2)
index = search_rolling_hash(S, t)
flag = [False]*ls
for i in index:
    flag[i] = True
stack = []
inf = float('inf')
cnt = [inf]*ls
for i in range(ls):
    if flag[i] == False:
        stack.append(i)
        cnt[i] = 0
while stack:
    x = stack.pop()
    y = (x-lt)%ls
    if cnt[y] == inf:
        cnt[y] = cnt[x]+1
        stack.append(y)
ans = max(cnt)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
print(0)