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 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)
Next = [-1]*ls
is_in = [False]*ls
for i in index:
    Next[i] = (i+lt)%ls
    is_in[(i+lt)%ls] = True
cnt = [0]*ls
ans = 0
if all(is_in[i] for i in range(ls)) and any(Next[i]>=0 for i in range(ls)):
    print(-1)
    sys.exit()
for i in range(ls):
    if is_in[i]:
        continue
    j = i
    res = 0
    while Next[j]>=0:
        res+=1
        j = Next[j]
        if j == i:
            print(-1)
            sys.exit()
    ans = max(ans, res)
print(ans)

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)
Next = [-1]*ls
is_in = [False]*ls
for i in index:
    Next[i] = (i+lt)%ls
    is_in[(i+lt)%ls] = True
cnt = [0]*ls
ans = 0
if all(is_in[i] for i in range(ls)) and any(Next[i]>=0 for i in range(ls)):
    print(-1)
    sys.exit()
for i in range(ls):
    if is_in[i]:
        continue
    j = i
    res = 0
    while Next[j]>=0:
        res+=1
        j = Next[j]
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.size = [1 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y]+=self.size[x]
        else:
            self.parent[y] = x
            self.size[x]+=self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
      
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
U = UnionFind(ls)
flag = False
for i in range(ls):
    if is_same[i] and is_same[(i+k)%ls]:
        if U.same(i, (i+k)%ls):
            flag = True
            break
        U.unite(i, (i+k)%ls)
if flag:
    print(-1)
else:
    ans = 0
    for i in range(ls):
        if is_same[i]:
            ans = max(ans, U.get_size(i))
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.size = [1 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y]+=self.size[x]
        else:
            self.parent[y] = x
            self.size[x]+=self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
      
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
U = UnionFind(ls)
flag = False
for i in range(ls):
    if is_same[i] and is_same[(i+k)%ls]:
        if U.same(i, (i+k)%ls):
            flag = True
            break
        U.unite(i, (i+k)%ls)
if flag:
    print(-1)
else:
    ans = max(U.get_size(i) for i in range(ls))
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = 0
for i, ti in enumerate(t):
    thash+=ord(ti)*power[k-i-1]
    thash%=mod
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
ans = 0
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 10**9+7
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = (rolling_hash[i]*base+ord(s))%mod
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
memo = [-1]*ls
is_visited = [False]*ls
def rec(i):
    if memo[i]>=0:
        return memo[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        memo[i] = 0
        return 0
    res = rec((i+k)%ls)
    if res<0:
        return -1
    memo[i] = res+1
    return res+1
ans = 0
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s
N = ls
mod = 10**9+7
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 10**9+7
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
memo = [-1]*ls
is_visited = [False]*ls
def rec(i):
    if memo[i]>=0:
        return memo[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        memo[i] = 0
        return 0
    res = rec((i+k)%ls)
    if res<0:
        return -1
    memo[i] = res+1
    return res+1
ans = 0
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        n=len(s)
        self.__s=s
        self.__n=n
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(n+1),[0]*(n+1)
        P1,P2=[1]*(n+1),[1]*(n+1)
        for i in range(n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    def hash(self,l,r):
        m1=self.__mod1; m2=self.__mod2
        assert 0<=l<=r<=self.__n
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%m1)%m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%m2)%m2)

def resolve():
    from math import ceil
    s=input()
    t=input()
    n=len(s)
    m=len(t)
    s=s*ceil(4*m/n)

    ok=[0]*n
    uf=UnionFind(n)
    for i in range(n):
        if(s[i:i+m]==t):
            ok[i]=1
    for i in range(n):
        if(ok[i] and ok[(i+m)%n]):
            if(not uf.unite(i,(i+m)%m)):
                print(-1)
                return
    ans=0
    for i in range(n):
        if(ok[i]): ans=max(ans,uf.size(i))
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

S = np.array(list(readline().rstrip()),np.int64)
T = np.array(list(readline().rstrip()),np.int64)

LS = len(S); LT = len(T)
LSext = LS + LT
LSext += (-LSext) % LS
Sext = np.tile(S,LSext//LS)

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

U = 2*10**6
base = 1234
MOD = 10**9 + 9
x = np.full(U,base,dtype=np.int64); x[0] = 1
power = cumprod(x,MOD)
x = np.full(U,pow(base,MOD-2,MOD),dtype=np.int64); x[0] = 1
power_inv = cumprod(x,MOD)

def RollingHash(S):
    return (S * power[:len(S)] % MOD).cumsum() % MOD

Sext_hash = RollingHash(Sext)
T_hash = RollingHash(T)[-1]

# ある地点を開始位置として、長さLTの文字列のhash値
x = Sext_hash[LT-1:LS+LT-1]
x[1:] -= Sext_hash[:LS-1]
x *= power_inv[:LS]; x %= MOD

# ある場所から始めたとして、Tを繰り返せる回数
INF = LS+100
cnt = [INF] * LS
stack = np.where(x!=T_hash)[0].tolist()
for x in stack:
    cnt[x] = 0
while stack:
    x = stack.pop()
    y = (x-LT)%LS
    if cnt[y] == INF:
        cnt[y] = cnt[x] + 1
        stack.append(y)

answer = max(cnt)
if answer == INF:
    answer = -1
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

S = np.array(list(readline().rstrip()),np.int64)
T = np.array(list(readline().rstrip()),np.int64)

LS = len(S); LT = len(T)
LSext = LS + LT
LSext += (-LSext) % LS
Sext = np.tile(S,LSext//LS)

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

U = 2*10**6
base = 1234
MOD = 10**9 + 9
x = np.full(U,base,dtype=np.int64); x[0] = 1
power = cumprod(x,MOD)
x = np.full(U,pow(base,MOD-2,MOD),dtype=np.int64); x[0] = 1
power_inv = cumprod(x,MOD)

def RollingHash(S):
    return (S * power[:len(S)] % MOD).cumsum() % MOD

Sext_hash = RollingHash(Sext)
T_hash = RollingHash(T)[-1]

# ある地点を開始位置として、長さLTの文字列のhash値
x = Sext_hash[LT-1:LS+LT-1]
x[1:] -= Sext_hash[:LS-1]
x *= power_inv[:LS]; x %= MOD

Submission status: Wrong Answer

Solution code:
def kmp(s):
    n = len(s)
    kmp = [0] * (n+1)
    kmp[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and s[i] != s[j]:
            j = kmp[j]
        j += 1
        kmp[i+1] = j

    return kmp

from collections import deque
def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res

import sys

def main():
    input = sys.stdin.readline
    s = input().rstrip()
    t = input().rstrip()

    n0 = len(s)
    m = len(t)

    s = s * (m // n0 + 2)

    res = kmp(t + '*' + s)
    res = res[m+2:]

    graph = [set() for _ in range(n0)]
    for i in range(len(res)):
        if res[i] >= m:
            graph[(i-m+1)%n0].add( (i + 1) % n0 )
    for i in range(n0):
        graph[i] = list(graph[i])
    print(graph)

    ts = topological_sort(graph, n0)
    if len(ts) != n0:
        ans = -1
    else:
        # print(ts)
        ans = 0
        path = [0] * n0
        for i in range(n0):
            ans = max(ans, path[ts[i]])
            for j in graph[ts[i]]:
                path[j] = path[ts[i]] + 1

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    i = 1
    lcp = 0
    while i < n:
        while i+lcp < n and s[i+lcp] == s[lcp]:
            lcp += 1
        z[i] = lcp

        if lcp == 0:
            i += 1
            continue

        k = 1
        while i+k < n and k+z[k] < lcp:
            z[i+k] = z[k]
            k += 1
        i += k
        lcp -= k

    return z

from collections import deque
def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for c, v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for c, v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res

s = input()
t = input()

n0 = len(s)

s = s * max(2, (len(t)) // len(s) + 1)

idx = s.find(t)

if idx >= 0:
    z = z_algorithm(s[idx:])
    # print(z)

    graph = [[] for _ in range(n0)]
    for i in range(n0):
        if i >= idx and z[i-idx] >= len(t):
            # edge[i] = (i + len(t)) % n0
            graph[i].append( (1, (i + len(t)) % n0) )

    ts = topological_sort(graph, n0)
    if len(ts) != n0:
        ans = -1
    else:
        # print(ts)
        ans = 0
        path = [0] * n0
        for i in range(n0):
            ans = max(ans, path[ts[i]])
            for _, j in graph[ts[i]]:
                path[j] = path[ts[i]] + 1
else:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

# 適当な素数と原始根でrolling hash
MOD = 10 ** 9 + 993
base = 123450

S = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)
T = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)

# Sの方が長くする
LS = len(S)
LT = len(T)
n = (LT + (-LT) % LS) // LS
S = np.concatenate([S]*(n+1))
S = S[:LS+LT]

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2); arr = arr.reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

base_inv = pow(base,MOD-2,MOD)
x = np.full(LS+LT,base,dtype=np.int64)
x[0] = 1
power = cumprod(x)
x = np.full(LS+LT,base_inv,dtype=np.int64)
x[0] = 1
power_inv = cumprod(x)

def to_rolling_hash(S):
    return (S * power[:len(S)] % MOD).cumsum() % MOD

S_hash = to_rolling_hash(S)
T_hash = to_rolling_hash(T)[-1] # 文字列全体

S_hash_LT = S_hash[LT-1:]
S_hash_LT[1:] -= S_hash[:LS]
S_hash_LT %= MOD
S_hash_LT *= power_inv[:LS+1]
S_hash_LT %= MOD

INF = 10 ** 18
visited = [False] * LS
dist = [INF] * LS # 操作終了位置からの距離

q = np.where(S_hash_LT[:LS] != T_hash)[0].tolist()

d = 0
while q:
    qq = []
    for x in q:
        if dist[x] == INF:
            dist[x] = d
            qq.append((x-LT)%LS)
    d += 1
    q = qq

answer = max(dist)
if answer >= INF:
    answer = -1

print(answer)

Submission status: Wrong Answer

Solution code:
import re

s = input()
t = input()

N = len(s)
M = len(t)

start = 0
i = 0
count = 0
ans = 0
breaks = set()
while True:
    # print(i)
    matched = True
    for k in range(M):
        if s[(i + k) % N] != t[k]:
            matched = False
            break

    if matched:
        if count == 0:
            start = i
        elif i == start:
            print(-1)
            exit(0)

        count += 1
        i = (i + M) % N

    else:
        if i in breaks:
            break
        breaks.add(i)

        # print("Had", count, "matches from", start, "to", i)
        start = i + 1
        ans = max(ans, count)
        count = 0
        i = (i + 1) % N
ans = max(ans, count)
print(ans)

Submission status: Wrong Answer

Solution code:
import re

s = input()
t = input()

N = len(s)
M = len(t)

start = 0
i = 0
count = 0
ans = 0
breaks = set()
while True:
    # print(i)
    matched = True
    for k in range(M):
        if s[(i + k) % N] != t[k]:
            matched = False
            break

    if matched:
        if count == 0:
            start = i
        elif i == start:
            print(-1)
            exit(0)

        count += 1
        i = (i + M) % N

    else:
        if i in breaks:
            break
        breaks.add(i)

        # print("Had", count, "matches from", start, "to", i)
        start = i + 1
        ans = max(ans, count)
        count = 0
        i = (i + 1) % N

print(ans)

Submission status: Wrong Answer

Solution code:
import re

s = input()
t = input()

N = len(s)
M = len(t)

start = 0
i = 0
count = 0
ans = 0
breaks = set()
while True:
    matched = True
    for k in range(M):
        if s[(i + k) % N] != t[k]:
            matched = False

    if matched:
        if count == 0:
            start = i
        elif i == start:
            print(-1)
            exit(0)

        count += 1
        i = (i + M) % N

    else:
        if i in breaks:
            break
        breaks.add(i)

        # print("Had", count, "matches from", start, "to", i)
        start = i + 1
        ans = max(ans, count)
        count = 0
        i = (i + 1) % N

print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
from scipy import signal

def solve(s: str, t: str):
    # 使われているアルファベット集合
    alpha = np.unique(list(s+t))
    a2i = {alpha: i for i, alpha in enumerate(alpha)}

    # s の長さが t の2倍になるように繰り返す。
    rep = (2*len(t)) // len(s) + 1
    s2 = s*rep

    # 畳み込み用の二次元配列とする。
    s_ary = np.zeros((len(s2), len(alpha)))
    t_ary = np.zeros((len(t), len(alpha)))
    for n, char in enumerate(s2):
        s_ary[n, a2i[char]] = 1.0
    for n, char in enumerate(t):
        t_ary[n, a2i[char]] = 1.0

    # FFT で畳み込みを計算
    convs = [np.round(signal.fftconvolve(s_ary[:,i], t_ary[::-1,i], mode="full")) for i in range(len(alpha))]
    conv = np.sum(convs, axis=0)[len(t)-1:len(t)+len(s)-1]

    # 部分文字列が一致するかのフラグ配列
    inc = (conv > (len(t) - 0.5))

    # print(inc)

    # A = np.zeros(len(s), dtype=int)

    # rst = 0
    # for i in range(len(s)):
        # j = i
        # cnt = 0
        # Aval = 0
        # while inc[j]:
            # # すでに来たことがある場合
            # if A[j] > 0:
                # Aval = A[j]
                # break

            # cnt += 1
            # j = (j + len(t)) % len(s)

            # # 無限ループを検知
            # if i==j:
                # print(-1)
                # return

        # j = i
        # for k in range(cnt):
            # A[j] = Aval + cnt - k
            # j = (j + len(t)) % len(s)

        # rst = max(A)

    # print(rst)

        


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:
#!/usr/bin/env python3
import sys
import numpy as np
from scipy import signal

def solve(s: str, t: str):
    # 使われているアルファベット集合
    alpha = np.unique(list(s+t))
    a2i = {alpha: i for i, alpha in enumerate(alpha)}

    # s の長さが t の2倍になるように繰り返す。
    rep = (2*len(t)) // len(s) + 1
    s2 = s*rep

    # 畳み込み用の二次元配列とする。
    s_ary = np.zeros((len(s2), len(alpha)))
    t_ary = np.zeros((len(t), len(alpha)))
    for n, char in enumerate(s2):
        s_ary[n, a2i[char]] = 1.0
    for n, char in enumerate(t):
        t_ary[n, a2i[char]] = 1.0

    # FFT で畳み込みを計算
    convs = [np.round(signal.fftconvolve(s_ary[:,i], t_ary[::-1,i], mode="full")) for i in range(len(alpha))]
    conv = np.sum(convs, axis=0)[len(t)-1:len(t)+len(s)-1]

    # 部分文字列が一致するかのフラグ配列
    inc = (conv > (len(t) - 0.5))

    # print(inc)

    A = np.zeros(len(s))

    rst = 0
    for i in range(len(s)):
        j = i
        cnt = 0
        while inc[j]:
            cnt += 1
            j = (j + len(t)) % len(s)

            # 無限ループを検知
            if i==j:
                print(-1)
                return

        rst = max([cnt, rst])

    print(rst)

        


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:
import sys

sys.setrecursionlimit(10 ** 7)

s = input()
t = input()

target_s = s + s


def get_match_count(s_strrr, t_str):
    result = [0]
    result_counter = 0
    t_index = 0
    for s_str in list(s_strrr):
        if t_index == len(t_str):
            t_index = 0
            result_counter += 1
        if s_str == t_str[t_index]:
            t_index += 1
        else:
            result.append(result_counter)
            result_counter = 0
    if t_index == len(t_str):
        result_counter += 1
    result.append(result_counter)
    return max(result)


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

if t not in target_s:
    print('0')
else:
    result = get_match_count(target_s, t)

    if result == len(target_s) // len(t):
        print(-1)
    elif result * len(t) + len(t) == len(target_s):
        print(-1)
    else:
        print(result)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

s = input()
t = input()

target_s = s + s


def get_match_count(s_strrr, t_str):
    result = [0]
    result_counter = 0
    t_index = 0
    for s_str in list(s_strrr):
        if t_index == len(t_str):
            t_index = 0
            result_counter += 1
        if s_str == t_str[t_index]:
            t_index += 1
        else:
            result.append(result_counter)
            result_counter = 0
    if t_index == len(t_str):
        result_counter += 1
    result.append(result_counter)
    return max(result)


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

if t not in target_s:
    print('0')
else:
    result = get_match_count(target_s, t)

    if result == len(target_s) // len(t):
        print(-1)
    if result * len(t) + len(t) == len(target_s):
        print(-1)
    else:
        print(result)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

s = input()
t = input()

target_s = s + s

result = [0]
result_counter = 0

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

if t not in target_s:
    print('0')
else:
    #print(target_s, t)
    t_index = 0
    for s_str in list(target_s):
        if t_index == len(t):
            t_index = 0
            result_counter += 1
        if s_str == t[t_index]:
            t_index += 1
        else:
            result.append(result_counter)
            result_counter = 0
    if t_index == len(t):
        result_counter += 1
    result.append(result_counter)

    #print(result)
    if max(result) == len(target_s) // len(t):
        print(-1)
    else:
        print(max(result))