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:
s = input()
t = input()

double_s = s + s
target_s = s + s

result = [0]
result_counter = 0
if t not in double_s:
    print('0')
else:
    while len(target_s) < len(t):
        target_s += s

    #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))

Submission status: Wrong Answer

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

double_s = s + s
target_s = s + s

result = [0]
result_counter = 0
if t not in double_s:
    print('0')
else:
    while len(target_s) < len(t):
        target_s += s

    #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

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

Submission status: Wrong Answer

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

def Z(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 not j:
            i += 1
            continue
        k = 1
        while len(S)-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

word = [t,'?'] + [s]*(len(t)//len(s)+1)

z = Z(''.join(word))
z = z[len(t)+1:]

g = [-1]*len(s)
c = [0]*len(s)

for i in range(len(s)):
    if z[i] == len(t):
        g[i] = (i+len(t))%len(s)

for i in range(len(s)):
    if c[i] > 0 or g[i] < 0:
        continue
    q = g[i]
    tmp = 0
    while q >= 0:
        tmp += 1

        if c[q] > 0:
            c[i] = tmp + c[q]
            break
        
        if tmp != 0 and q == i:
            print(-1)
            exit()
        
        q = g[q]

    c[i] = max(c[i],tmp)

print(max(c))

Submission status: Wrong Answer

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

def Z(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 not j:
            i += 1
            continue
        k = 1
        while len(S)-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

z = Z(t+'?'+s*(len(t)//len(s) + 1))
z = z[len(t)+1:]

g = [-1]*len(s)

for i in range(len(s)):
    if z[i] == len(t):
        g[i] = (i+len(t))%len(s)

ans = 0

for i in range(len(s)):
    tmp = 0
    q = g[i]
    while q >= 0:
        q = g[q]
        if tmp != 0 and q == i:
            print(-1)
            exit()
        tmp += 1
    ans = max(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


s = ns()
t = ns()

s = list(s)
t = list(t)

lens = len(s)
lent = len(t)

ng = [0]*lent
cnt = 0
for i in range(1, lent):
    ng[i] = cnt
    if t[i] == t[cnt]:
        cnt += 1
    else:
        cnt = 0

ans = set()
cnt = 0
for i, si in enumerate(s * max(3, -(-3*lent // lens))):
    if si == t[cnt]:
        if cnt == lent-1:
            ans.add((i-lent+1) % lens)

        else:
            cnt += 1
            continue

    if si == t[ng[cnt]]:
        cnt = min(ng[cnt] + 1, lent-1)
    else:
        cnt = 0

edge = {}
for ansi in ans:
    edge.update({ansi: (ansi+lent)%lens})

ins = {i: 0 for i in range(lens)}
for src, dst in edge.items():
    ins[dst] += 1

from collections import deque
que = deque()
visited = [False]*lens
dist = [0]*lens
for key, val in ins.items():
    if val == 0:
        que.append(key)

while que:
    cur = que.popleft()
    visited[cur] = True

    if cur in edge:
        dist[edge[cur]] = dist[cur] + 1
        que.append(edge[cur])

if all(visited):
    print(max(dist))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


s = ns()
t = ns()

s = list(s)
t = list(t)

lens = len(s)
lent = len(t)

ng = [0]*lent
cnt = 0
for i in range(1, lent):
    ng[i] = cnt
    if t[i] == t[cnt]:
        cnt += 1
    else:
        cnt = 0

ans = set()
cnt = 0
for i, si in enumerate(s * max(2, -(-3*lent // lens))):
    if si == t[cnt]:
        if cnt == lent-1:
            ans.add((i-lent+1) % lens)

        else:
            cnt += 1
            continue

    if si == t[ng[cnt]]:
        cnt = min(ng[cnt] + 1, lent-1)
    else:
        cnt = 0

edge = {}
for ansi in ans:
    edge.update({ansi: (ansi+lent)%lens})

ins = {i: 0 for i in range(lens)}
for src, dst in edge.items():
    ins[dst] += 1

from collections import deque
que = deque()
visited = [False]*lens
dist = [0]*lens
for key, val in ins.items():
    if val == 0:
        que.append(key)

while que:
    cur = que.popleft()
    visited[cur] = True

    if cur in edge:
        dist[edge[cur]] = dist[cur] + 1
        que.append(edge[cur])

if all(visited):
    print(max(dist))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


s = ns()
t = ns()

s = list(s)
t = list(t)

lens = len(s)
lent = len(t)

ng = [0]*lent
cnt = 0
for i in range(1, lent):
    ng[i] = cnt
    if t[i] == t[cnt]:
        cnt += 1
    else:
        cnt = 0

ans = set()
cnt = 0
for i, si in enumerate(s * -(-3*lent // lens)):
    if si == t[cnt]:
        if cnt == lent-1:
            ans.add((i-lent+1) % lens)

        else:
            cnt += 1
            continue

    if si == t[ng[cnt]]:
        cnt = min(ng[cnt] + 1, lent-1)
    else:
        cnt = 0

edge = {}
for ansi in ans:
    edge.update({ansi: (ansi+lent)%lens})

ins = {i: 0 for i in range(lens)}
for src, dst in edge.items():
    ins[dst] += 1

from collections import deque
que = deque()
visited = [False]*lens
dist = [0]*lens
for key, val in ins.items():
    if val == 0:
        que.append(key)

while que:
    cur = que.popleft()
    visited[cur] = True

    if cur in edge:
        dist[edge[cur]] = dist[cur] + 1
        que.append(edge[cur])

if all(visited):
    print(max(dist))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


s = ns()
t = ns()

s = list(s)
t = list(t)

lens = len(s)
lent = len(t)

ng = [0]*lent
cnt = 0
for i in range(1, lent):
    ng[i] = cnt
    if t[i] == t[cnt]:
        cnt += 1
    else:
        cnt = 0

ans = []
cnt = 0
for i, si in enumerate(s * -(-lent // lens)):
    if si == t[cnt]:
        if cnt == lent-1:
            ans.append((i-lent+1) % lens)

        else:
            cnt += 1
            continue

    if si == t[ng[cnt]]:
        cnt = min(ng[cnt] + 1, lent-1)
    else:
        cnt = 0

edge = {}
for ansi in ans:
    edge.update({ansi: (ansi+lent)%lens})

ins = {i: 0 for i in range(lens)}
for src, dst in edge.items():
    ins[dst] += 1

from collections import deque
que = deque()
visited = [False]*lens
dist = [0]*lens
for key, val in ins.items():
    if val == 0:
        que.append(key)

ok = True
while que:
    cur = que.popleft()
    visited[cur] = True

    if cur in edge:
        dist[edge[cur]] = dist[cur] + 1
        que.append(edge[cur])

if all(visited):
    print(max(dist))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


s = ns()
t = ns()

s = list(s)
t = list(t)

lens = len(s)
lent = len(t)

ng = [0]*lent
cnt = 0
for i in range(1, lent):
    ng[i] = cnt
    if t[i] == t[cnt]:
        cnt += 1
    else:
        cnt = 0

ans = []
cnt = 0
for i, si in enumerate(s):
    if si == t[cnt]:
        if cnt == lent-1:
            ans.append((i-lent+1) % lens)

        else:
            cnt += 1
            continue

    if si == t[ng[cnt]]:
        cnt = min(ng[cnt] + 1, lent-1)
    else:
        cnt = 0

edge = {}
for ansi in ans:
    edge.update({ansi: (ansi+lent)%lens})

ins = {i: 0 for i in range(lens)}
for src, dst in edge.items():
    ins[dst] += 1

from collections import deque
que = deque()
visited = [False]*lens
dist = [0]*lens
for key, val in ins.items():
    if val == 0:
        que.append(key)

ok = True
while que:
    cur = que.popleft()
    visited[cur] = True

    if cur in edge:
        dist[edge[cur]] = dist[cur] + 1
        que.append(edge[cur])

if all(visited):
    print(max(dist))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())



s = list("abcabab")
t = list("ab")

s = ns()
t = ns()

lens = len(s)
lent = len(t)

graph = [[] for _ in range(lens)]

cnt = 0
ng = [0]*lent
for i in range(1, lent):
    ng[i] = cnt
    if t[i] == t[cnt]:
        cnt += 1
    else:
        cnt = 0

cur = 0
cnt = 0
while cur < (lens + lent - 1):
    if s[cur % lens] == t[cnt]:
        if cnt == lent-1:
            graph[(cur - lent) % lens].append(cur % lens)
            cnt = ng[cnt]

        else:
            cur += 1
            cnt += 1

    else:
        if cnt == 0:
            cur += 1

        else:
            cnt = ng[cnt]

ins = {i: 0 for i in range(lens)}
for row in graph:
    if row:
        nex = row[0]
        ins[nex] += 1

dist = [0]*lens
from collections import deque
que = deque()
for node, cnt in ins.items():
    if cnt == 0:
        que.append(node)

visited = [False]*lens
while que:
    cur = que.popleft()
    visited[cur] = True
    if graph[cur]:
        nex = graph[cur][0]
        ins[nex] -= 1

        if ins[nex] == 0:
            dist[nex] = dist[cur] + 1
            que.append(nex)

if all(visited):
    print(max(dist))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import os
import sys

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

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

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

S += S
LS = len(S)
LT = len(T)

s = S
while len(S) <= LT * 5:
    S += s


def solve():
    i = 0
    ret = 0
    seen = [False] * len(S)
    while i < len(S):
        if not seen[i]:
            j = 0
            while S.startswith(T, i + j * LT):
                seen[i + j * LT] = True
                if j * LT >= LS * 2:
                    return -1
                j += 1
            ret = max(j, ret)
        i += 1
    return ret


ans = solve()
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys

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

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

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

S += S
LS = len(S)
LT = len(T)

s = S
while len(S) <= LT * 3:
    S += s


def solve():
    i = 0
    ret = 0
    seen = [False] * len(S)
    while i < len(S):
        if not seen[i]:
            j = 0
            while S.startswith(T, i + j * LT):
                seen[i + j * LT] = True
                if j * LT >= LS:
                    return -1
                j += 1
            ret = max(j, ret)
        i += 1
    return ret


ans = solve()
print(ans)

Submission status: Wrong Answer

Solution code:
# sの中からp(pattern)を探して位置を返す
def kmp(s, p):
    cnt = 0
    sn = len(s)
    pn = len(p)
    slide = [0] * (pn + 3)

    # 2つのpを先頭をずらしながら、不一致の文字の前が何文字一致しているか数える
    i = 1
    ii = 0
    st = 0  # 初めての先頭と同じ文字
    lng = 0  # stからの共通部分の長さ
    while i < pn:
        if p[i] == p[ii]:
            if st == 0: st = i
            i += 1
            ii += 1
            slide[i] = ii
        elif ii:
            if lng == 0 and st: lng = ii
            ii = 0
        else:
            i += 1
            slide[i] = ii
        if lng == 0 and st: lng = pn - st

    # 一致していた場合siとpiを1進める
    # pi = 0(パターン先頭文字)で不一致の場合、siを1進める
    # その他(不一致)の場合、piをslideから取得した位置にする

    si = pi = 0
    while si - pn < sn - 1:
        if s[si % sn] == p[pi]:
            si += 1
            pi += 1
        elif pi == 0:
            si += 1
        else:
            pi = slide[pi]
        # すべて一致すれば、先頭の位置を記録し、その位置以降から開始
        if pi == pn:
            ex[si - pn] = True
            cnt += 1
            if st:
                si += - pn + st + lng
                pi = lng
            else:
                pi = 0
    return cnt

def get_group(k):
    g = ps[k]
    if g < 0:
        return k
    gg = get_group(g)
    ps[k] = gg
    return gg

def merge(j, k):
    g1 = get_group(j)
    g2 = get_group(k)
    if g1 != g2:
        s1 = -ps[g1]
        s2 = -ps[g2]
        if s2 > s1:
            g1, g2 = g2, g1
        ps[g1] = -(s1 + s2)
        ps[g2] = g1

s = input()
t = input()
tn = len(t)
s = s * (tn // len(s) + 1)
sn = len(s)
ps = [-1] * (sn + 1)  # 親(parent)と大きさ(size)。0以上は親。負の場合、そのノードが根で絶対値が大きさ。
ex = [False] * sn
cnt = kmp(s, t)
if cnt < 2:
    print(cnt)
    exit()
for i in range(sn):
    ni = (i + tn) % sn
    if ex[i] and ex[ni]:
        if get_group(i) == get_group(ni):
            print(-1)
            exit()
        merge(i, ni)
print(-min(ps))

Submission status: Wrong Answer

Solution code:
# sの中からp(pattern)を探して位置を返す
def kmp(s, p):
    cnt = 0
    sn = len(s)
    pn = len(p)
    slide = [0] * (pn + 3)

    # 2つのpを先頭をずらしながら、不一致の文字の前が何文字一致しているか数える
    i = 1
    ii = 0
    st = 0  # 初めての先頭と同じ文字
    lng = 0  # stからの共通部分の長さ
    while i < pn:
        if p[i] == p[ii]:
            if st == 0: st = i
            i += 1
            ii += 1
            slide[i] = ii
        elif ii:
            if lng == 0 and st: lng = ii
            ii = 0
        else:
            i += 1
            slide[i] = ii
        if lng == 0 and st: lng = pn - st

    # 一致していた場合siとpiを1進める
    # pi = 0(パターン先頭文字)で不一致の場合、siを1進める
    # その他(不一致)の場合、piをslideから取得した位置にする

    si = pi = 0
    while si - pn < sn - 1:
        if s[si % sn] == p[pi]:
            si += 1
            pi += 1
        elif pi == 0:
            si += 1
        else:
            pi = slide[pi]
        # すべて一致すれば、先頭の位置を記録し、その位置以降から開始
        if pi == pn:
            ex[si - pn] = True
            cnt += 1
            if st:
                si += - pn + st + lng
                pi = lng
            else:
                pi = 0
    return cnt

def get_group(k):
    g = ps[k]
    if g < 0:
        return k
    gg = get_group(g)
    ps[k] = gg
    return gg

def merge(j, k):
    g1 = get_group(j)
    g2 = get_group(k)
    if g1 != g2:
        s1 = -ps[g1]
        s2 = -ps[g2]
        if s2 > s1:
            g1, g2 = g2, g1
        ps[g1] = -(s1 + s2)
        ps[g2] = g1

s = input()
t = input()
tn = len(t)
s = s * (tn // len(s) + 1)
sn = len(s)
ps = [-1] * (sn + 1)  # 親(parent)と大きさ(size)。0以上は親。負の場合、そのノードが根で絶対値が大きさ。
ex = [False] * sn
cnt = kmp(s, t)
print(ex,cnt)
if cnt < 2:
    print(cnt)
    exit()
for i in range(sn):
    ni = (i + tn) % sn
    if ex[i] and ex[ni]:
        if get_group(i) == get_group(ni):
            print(-1)
            exit()
        merge(i, ni)
print(-min(ps))

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

len0 = len(S)
S = S * ((len(T) + len(S) - 1) // len(S) * 2)

MOD = 10 * 20 + 1
base = 26

hashS = [0]
hashT = 0
for s in S :
    hashS.append((hashS[-1] * base + ord(s) - 97) % MOD)
for t in T :
    hashT = (hashT * base + ord(t) - 97) % MOD

ok = [False] * len0
for i in range(len0) :
    if (hashS[i+len(T)] - hashS[i] * pow(base, len(T), MOD)) % MOD == hashT :
        ok[i] = True

def solve() :
    ret = 0
    visited = [-1]*len0
    for i in range(len0) :
        if ok[i] and visited[i] == -1 :
            j = i
            count = 0
            while ok[j] :
                if visited[j] != -1 :
                    count += visited[j]
                    break
                    
                count += 1
                visited[j] = 1
                j = (j+len(T))%len0
                if j == i :
                    return -1
            visited[i] = count
            ret = max(ret, count)
    return ret
        
print(solve())

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

len0 = len(S)
S = S * ((len(T) + len(S) - 1) // len(S) * 2)

MOD = 10 * 16 + 61
base = 26

hashS = [0]
hashT = 0
for s in S :
    hashS.append((hashS[-1] * base + ord(s) - 97) % MOD)
for t in T :
    hashT = (hashT * base + ord(t) - 97) % MOD

ok = [False] * len0
for i in range(len0) :
    if (hashS[i+len(T)] - hashS[i] * pow(base, len(T), MOD)) % MOD == hashT :
        ok[i] = True

def solve() :
    ret = 0
    visited = [-1]*len0
    for i in range(len0) :
        if ok[i] and visited[i] == -1 :
            j = i
            count = 0
            while ok[j] :
                if visited[j] != -1 :
                    count += visited[j]
                    break
                    
                count += 1
                visited[j] = 1
                j = (j+len(T))%len0
                if j == i :
                    return -1
            visited[i] = count
            ret = max(ret, count)
    return ret
        
print(solve())

Submission status: Wrong Answer

Solution code:
# sの中からp(pattern)を探して位置を返す
def kmp(s, p):
    cnt = 0
    sn = len(s)
    pn = len(p)
    slide = [0] * (pn + 3)

    # 2つのpを先頭をずらしながら、不一致の文字の前が何文字一致しているか数える
    i = 1
    ii = 0
    st = 0  # 初めての先頭と同じ文字
    lng = 0  # stからの共通部分の長さ
    while i < pn:
        if p[i] == p[ii]:
            if st == 0: st = i
            i += 1
            ii += 1
            slide[i] = ii
        elif ii:
            if lng == 0 and st: lng = ii
            ii = 0
        else:
            i += 1
            slide[i] = ii
        if lng == 0 and st: lng = pn - st

    # 一致していた場合siとpiを1進める
    # pi = 0(パターン先頭文字)で不一致の場合、siを1進める
    # その他(不一致)の場合、piをslideから取得した位置にする

    si = pi = 0
    while si - pn < sn - 1:
        if s[si % sn] == p[pi]:
            si += 1
            pi += 1
        elif pi == 0:
            si += 1
        else:
            pi = slide[pi]
        # すべて一致すれば、先頭の位置を記録し、その位置以降から開始
        if pi == pn:
            ex[si - pn] = True
            cnt += 1
            if st:
                si += - pn + st + lng
                pi = lng
            else:
                pi = 0
    return cnt

def get_group(k):
    g = ps[k]
    if g < 0:
        return k
    gg = get_group(g)
    ps[k] = gg
    return gg

def merge(j, k):
    g1 = get_group(j)
    g2 = get_group(k)
    if g1 != g2:
        s1 = -ps[g1]
        s2 = -ps[g2]
        if s2 > s1:
            g1, g2 = g2, g1
        ps[g1] = -(s1 + s2)
        ps[g2] = g1

s = input()
t = input()
tn = len(t)
s = s * (tn // len(s) + 3)
sn = len(s)
ps = [-1] * (sn + 1)  # 親(parent)と大きさ(size)。0以上は親。負の場合、そのノードが根で絶対値が大きさ。
ex = [False] * sn
cnt = kmp(s, t)
if cnt < 2:
    print(cnt)
    exit()
for i in range(sn):
    ni = (i + tn) % sn
    if ex[i] and ex[ni]:
        if get_group(i) == get_group(ni):
            print(-1)
            exit()
        merge(i, ni)
print(-min(ps))

Submission status: Wrong Answer

Solution code:
S = input().strip()
T = input().strip()

if len(T) / len(S) >= 1:
    S = S * int(round(len(T) / len(S)))

len_S = len(S)
len_T = len(T)

A = [0] * len_S
for i in range(len_S - len_T + 1):
    if S[i:i+len_T] == T:
        for j in range(len_T):
            A[i+j] = 1

e = len_S
for i in range(len_S - 1):
    if A[i:i+2] == [0, 1]:
        e = i
        break

SS = S[e+1:] + S[:e+1]

max_C = 0
C = 0
i = 0
while True:
    if SS[i:i+len_T] == T:
        C += 1
        i += len_T
    else:
        C = 0
        i += 1
    max_C = max(max_C, C)
    if i >= len_S:
        break

if max_C * len_T == len_S:
    print('-1')
else:
    print(max_C)

Submission status: Wrong Answer

Solution code:
S = 'aba'
T = 'baaab'

if len(T) / len(S) >= 1:
    S = S * int(round(len(T) / len(S)))

len_S = len(S)
len_T = len(T)

A = [0] * len_S
for i in range(len_S - len_T + 1):
    if S[i:i+len_T] == T:
        for j in range(len_T):
            A[i+j] = 1

e = len_S
for i in range(len_S - 1):
    if A[i:i+2] == [0, 1]:
        e = i
        break

SS = S[e+1:] + S[:e+1]

max_C = 0
C = 0
i = 0
while True:
    if SS[i:i+len_T] == T:
        C += 1
        i += len_T
    else:
        C = 0
        i += 1
    max_C = max(max_C, C)
    if i >= len_S:
        break

if max_C * len_T == len_S:
    print('-1')
else:
    print(max_C)

Submission status: Wrong Answer

Solution code:
from collections import deque
def kmp_search(S,T):
    m=0
    i=0
    N=len(S)
    M=len(T)
    U=[0 for i in range(M)]
    j=0
    res=[]
    for i in range(1,M):
        if T[i]==T[j]:
            j+=1
            U[i]=j
        else:
            U[i]=j
            j=0
    i=0;j=0
    while(i<N):
        if S[i]==T[j]:
            i+=1
            j+=1
        elif j==0:
            i+=1
        else:
            j=U[j]
        if j==M:
            res.append(i-j)
            j=0
    return res
s=input()
t=input()
N=len(s)
M=len(t)
k=-((-2*M)//N)+1
#print(s*k)
#print(t)
X=kmp_search(s*k,t)
#print(X)
G=[[] for i in range(N)]
for i in X:
    G[i%N].append((i+M)%N)
#print(G)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
#print(res)
if len(res)==0:
    print(-1)
    exit()
ans=[0 for i in range(N)]
for i in res[::-1]:
    #print(ans)
    tmp=0
    for j in G[i]:
        tmp=max(ans[j],tmp)
    ans[i]=tmp+1
print(max(ans)-1)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1000
        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 + 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) * 3) // len(s)
t = t * 4
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)
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 = 1000
        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 + 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) * 3) // len(s)
t = t * 4
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 = 1000
        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 + 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)