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: Runtime Error

Solution code:
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_table()

    def create_table(self):
        table = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = table[j]
            j += 1
            table[i+1] = j
        self.table = table

    def match(self,s):
        n = len(s)
        j = 0
        ret = [0]*n
        for i in range(n):
            while j >= 0 and (j == self.n or s[i] != self.pattern[j]):
                j = self.table[j]
            j += 1
            if j == self.n:
                ret[(i-self.n+1)%n] = 1 
        return ret

def main():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    k = 1 - (-(m-1)//n)
    si = s*k
    a = KMP(t)
    b = a.match(si)
    #print a, b
    edges = [[] for i in range(n)]
    for i in range(n):
        if b[i]:
            edges[i].append((i+m)%n)
    #print 'edges', edges
    visited = [0]*n
    
    def dfs(node):
        if visited[node] == 1:
            return False
        if visited[node] == 2:
            return True
            
        visited[node] = 1
        
        for nei in edges[node]:
            if not dfs(nei):
                return False
        visited[node] = 2
        res.append(node)
        return True
    
    res = []
    for i in range(n):
        if not dfs(i):
            print(-1)
            break
    else:
        dp = [0] * n
        ans = 0
        for i in range(n-1, -1, -1):
            t = res[i]
            for c in edges[t]:
                dp[c] = max(dp[c], dp[t] + 1)
                ans = max(ans, dp[c])
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_table()

    def create_table(self):
        table = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = table[j]
            j += 1
            table[i+1] = j
        self.table = table

    def match(self,s):
        n = len(s)
        j = 0
        ret = [0]*n
        for i in range(n):
            while j >= 0 and (j == self.n or s[i] != self.pattern[j]):
                j = self.table[j]
            j += 1
            if j == self.n:
                ret[(i-self.n+1)%n] = 1 
        return ret

def main():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    k = 1 - (-(m-1)//n)
    si = s*k
    a = KMP(t)
    b = a.match(si)
    #print a, b
    edges = [[] for i in range(n)]
    for i in range(n):
        if b[i]:
            edges[i].append((i+m)%n)
    #print 'edges', edges
    visited = [0]*n
    
    def dfs(node):
        if visited[node] == 1:
            return False
        if visited[node] == 2:
            return True
            
        visited[node] = 1
        
        for nei in edges[node]:
            if not dfs(nei):
                return False
        visited[node] = 2
        res.append(node)
        return True
    
    res = []
    for i in range(n):
        if not dfs(i):
            print -1
            break
    else:
        dp = [0] * n
        ans = 0
        for i in range(n-1, -1, -1):
            t = res[i]
            for c in edges[t]:
                dp[c] = max(dp[c], dp[t] + 1)
                ans = max(ans, dp[c])
        print ans

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class Solution():
    def stringOfEternity(self, S, T):
        m, n = len(S), len(T)
        def getFail():
            i, j = 0, -1
            f[i] = j
            # prepare roll-back table
            while i < len(T):
                # roll-back
                while j >= 0 and T[i] != T[j]: j = f[j]
                i, j = i + 1, j + 1
                f[i] = j
                
        def KMP():
            j = 0
            for i in range(m):
                while j and S[i] != T[j]:
                    j = f[j]
                if S[i] == T[j]:
                    j = j + 1
                else:
                    j = 0
                if j == n:
                    sign[i-n+1] = 1
                    j = f[j]
#                   
      
        def dfs(node):
            if visited[node] == 1:
                return False
            if visited[node] == 2:
                return True
            
            visited[node] = 1
            
            for nei in graph[node]:
                if not dfs(nei): return False
            visited[node] = 2
            q[self.count] = node
            self.count += 1
            return True
        
        f = [0] * (n+1)
        getFail()

        sign = [0] * (m+1)
        KMP()
        
        #print sign
        graph = [[] for _ in range(m+1)]
        for i in range(len(S)):
            j = (i+n) % len(s)
            if sign[i]:
                graph[i].append(j)
        #print graph
                
        visited = [-1] * (1+m)
        q = [0] *(1+m)
        
        self.count = 0
        for i in range(m):
            if not dfs(i):
                return -1
         
        assert self.count == m
        dp = [0] * (1+m)
        ans = 0
        for i in range(m, -1, -1):
            t = q[i]
            for c in graph[t]:
                dp[c] = max(dp[c], dp[t] + 1)
                ans = max(ans, dp[c])
        return ans

s = input()
t = input()


n_, m_ = len(s), len(t)
nn = n_
S = s
while n_ < nn + m_:
    for i in range(nn):
        S += s[i]
        n_ += 1
S +='#'
T = t
print Solution().stringOfEternity(S, T)

Submission status: Runtime Error

Solution code:
maxN = 10**6+10
class Solution():
    def stringOfEternity(self, S, T):
        m, n = len(S), len(T)
        def getFail():
            i, j = 0, -1
            f[i] = j
            # prepare roll-back table
            while i < len(T):
                # roll-back
                while j >= 0 and T[i] != T[j]: j = f[j]
                i, j = i + 1, j + 1
                f[i] = j
                
        def KMP():
            j = 0
            for i in range(m):
                while j and S[i] != T[j]:
                    j = f[j]
                if S[i] == T[j]:
                    j = j + 1
                else:
                    j = 0
                if j == n:
                    sign[i-n+1] = 1
                    j = f[j]
#                   
      
        def dfs(node):
            if visited[node] == 1:
                return False
            if visited[node] == 2:
                return True
            
            visited[node] = 1
            
            for nei in graph[node]:
                if not dfs(nei): return False
            visited[node] = 2
            q[self.count] = node
            self.count += 1
            return True
        
        f = [0] * maxN
        getFail()

        sign = [0] * maxN
        KMP()
        
        graph = [[] for _ in range(maxN)]
        for i in range(len(S)):
            j = (i+n) % (m-1)
            if sign[i]:
                graph[i].append(j)
                
        visited = [-1] * maxN
        q = [0] * maxN
        
        self.count = 0
        for i in range(m):
            if not dfs(i):
                return -1
         
        assert self.count == m
        dp = [0] * maxN
        ans = 0
        for i in range(m, -1, -1):
            t = q[i]
            for c in graph[t]:
                dp[c] = max(dp[c], dp[t] + 1)
                ans = max(ans, dp[c])
        return ans

s = raw_input()
t = raw_input()

n, m = len(s), len(t)
nn = n
S = s
while n < nn + m:
    for i in range(nn):
        S += s[i]
        n += 1
S +='#'
T = t
print Solution().stringOfEternity(S, T)

Submission status: Runtime Error

Solution code:
class Solution():
    def stringOfEternity(self, S, T):
        m, n = len(S), len(T)
        def getFail():
            i, j = 0, -1
            f[i] = j
            # prepare roll-back table
            while i < len(T):
                # roll-back
                while j >= 0 and T[i] != T[j]: j = f[j]
                i, j = i + 1, j + 1
                f[i] = j
                
        def KMP():
            j = 0
            for i in range(m):
                while j and S[i] != T[j]:
                    j = f[j]
                if S[i] == T[j]:
                    j = j + 1
                else:
                    j = 0
                if j == n:
                    sign[i-n+1] = 1
                    j = f[j]
#                   
      
        def dfs(node):
            if visited[node] == 1:
                return False
            if visited[node] == 2:
                return True
            
            visited[node] = 1
            
            for nei in graph[node]:
                if not dfs(nei): return False
            visited[node] = 2
            q[self.count] = node
            self.count += 1
            return True
        
        f = [0] * (n+1)
        getFail()

        sign = [0] * (m+1)
        KMP()
        
        graph = [[] for _ in range(m+1)]
        for i in range(len(S)):
            j = (i+n) % (m-1)
            if sign[i]:
                graph[i].append(j)
                
        visited = [-1] * (1+m)
        q = [0] *(1+m)
        
        self.count = 0
        for i in range(m):
            if not dfs(i):
                return -1
         
        assert self.count == m
        dp = [0] * (1+m)
        ans = 0
        for i in range(m, -1, -1):
            t = q[i]
            for c in graph[t]:
                dp[c] = max(dp[c], dp[t] + 1)
                ans = max(ans, dp[c])
        return ans

s = input()
t = input()

n, m = len(s), len(t)
nn = n
S = s
while n < nn + m:
    for i in range(nn):
        S += s[i]
        n += 1
S +='#'
T = t
print Solution().stringOfEternity(S, T)

Submission status: Runtime Error

Solution code:
maxN = 10**6+10
class Solution():
    def stringOfEternity(self, S, T):
        m, n = len(S), len(T)
        def getFail():
            i, j = 0, -1
            f[i] = j
            # prepare roll-back table
            while i < len(T):
                # roll-back
                while j >= 0 and T[i] != T[j]: j = f[j]
                i, j = i + 1, j + 1
                f[i] = j
                
        def KMP():
            j = 0
            for i in range(m):
                while j and S[i] != T[j]:
                    j = f[j]
                if S[i] == T[j]:
                    j = j + 1
                else:
                    j = 0
                if j == n:
                    sign[i-n+1] = 1
                    j = f[j]
#                   
      
        def dfs(node):
            if visited[node] == 1:
                return False
            if visited[node] == 2:
                return True
            
            visited[node] = 1
            
            for nei in graph[node]:
                if not dfs(nei): return False
            visited[node] = 2
            q[self.count] = node
            self.count += 1
            return True
        
        f = [0] * maxN
        getFail()

        sign = [0] * maxN
        KMP()
        
        graph = [[] for _ in range(maxN)]
        for i in range(len(S)):
            j = (i+n) % (m-1)
            if sign[i]:
                graph[i].append(j)
                
        visited = [-1] * maxN
        q = [0] * maxN
        
        self.count = 0
        for i in range(m):
            if not dfs(i):
                return -1
         
        assert self.count == m
        dp = [0] * maxN
        ans = 0
        for i in range(m, -1, -1):
            t = q[i]
            for c in graph[t]:
                dp[c] = max(dp[c], dp[t] + 1)
                ans = max(ans, dp[c])
        return ans

s = raw_input()
t = raw_input()

n, m = len(s), len(t)
nn = n
S = s
while n < nn + m:
    for i in range(nn):
        S += s[i]
        n += 1
S +='#'
T = t
print Solution().stringOfEternity(S, T)

Submission status: Runtime Error

Solution code:
maxN = 10**6+10
class Solution():
    def stringOfEternity(self, S, T):
        m, n = len(S), len(T)
        def getFail():
            i, j = 0, -1
            f[i] = j
            # prepare roll-back table
            while i < len(T):
                # roll-back
                while j >= 0 and T[i] != T[j]: j = f[j]
                i, j = i + 1, j + 1
                f[i] = j
                
        def KMP():
            j = 0
            for i in range(m):
                while j and S[i] != T[j]:
                    j = f[j]
                if S[i] == T[j]:
                    j = j + 1
                else:
                    j = 0
                if j == n:
                    sign[i-n+1] = 1
                    j = f[j]
#                   
      
        def dfs(node):
            if visited[node] == 1:
                return False
            if visited[node] == 2:
                return True
            
            visited[node] = 1
            
            for nei in graph[node]:
                if not dfs(nei): return False
            visited[node] = 2
            q[self.count] = node
            self.count += 1
            return True
        
        f = [0] * maxN
        getFail()

        sign = [0] * maxN
        KMP()
        
        graph = [[] for _ in range(maxN)]
        for i in range(len(S)):
            j = (i+n) % (m-1)
            if sign[i]:
                graph[i].append(j)
                
        visited = [-1] * maxN
        q = [0] * maxN
        
        self.count = 0
        for i in range(m):
            if not dfs(i):
                return -1
         
        assert self.count == m
        dp = [0] * maxN
        ans = 0
        for i in range(m, -1, -1):
            t = q[i]
            for c in graph[t]:
                dp[c] = max(dp[c], dp[t] + 1)
                ans = max(ans, dp[c])
        return ans

s = input()
t = input()

n, m = len(s), len(t)
nn = n
S = s
while n < nn + m:
    for i in range(nn):
        S += s[i]
        n += 1
S +='#'
T = t
print Solution().stringOfEternity(S, T)

Submission status: Runtime Error

Solution code:
maxN = 10**6+10
class Solution():
    def stringOfEternity(self, S, T):
        m, n = len(S), len(T)
        def getFail():
            i, j = 0, -1
            f[i] = j
            # prepare roll-back table
            while i < len(T):
                # roll-back
                while j >= 0 and T[i] != T[j]: j = f[j]
                i, j = i + 1, j + 1
                f[i] = j
                
        def KMP():
            j = 0
            for i in range(m):
                while j and S[i] != T[j]:
                    j = f[j]
                if S[i] == T[j]:
                    j = j + 1
                else:
                    j = 0
                if j == n:
                    sign[i-n+1] = 1
                    j = f[j]
#                   
      
        def dfs(node):
            if visited[node] == 1:
                return False
            if visited[node] == 2:
                return True
            
            visited[node] = 1
            
            for nei in graph[node]:
                if not dfs(nei): return False
            visited[node] = 2
            q[self.count] = node
            self.count += 1
            return True
        
        f = [0] * maxN
        getFail()

        sign = [0] * maxN
        KMP()
        
        graph = [[] for _ in range(maxN)]
        for i in range(len(S)):
            j = (i+n) % (m-1)
            if sign[i]:
                graph[i].append(j)
        print graph
                
        visited = [-1] * maxN
        q = [0] * maxN
        
        self.count = 0
        for i in range(m):
            if not dfs(i):
                return -1
         
        assert self.count == m
        dp = [0] * maxN
        ans = 0
        for i in range(m, -1, -1):
            t = q[i]
            for c in graph[t]:
                dp[c] = max(dp[c], dp[t] + 1)
                ans = max(ans, dp[c])
        return ans

s = input()
t = input()

n, m = len(s), len(t)
nn = n
S = s
while n < nn + m:
    for i in range(nn):
        S += s[i]
        n += 1
S +='#'
T = t
print Solution().stringOfEternity(S, T)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cassert>

using namespace std;

using ll =  long long;

constexpr int S_MAX = 500000;
constexpr int T_MAX = 500000;
constexpr int INF = 1<<30;

vector<int> table(T_MAX, 0); // ずらしテーブル

void make_table(string p, int m) {
    int j = 0;
    for(int i=1;i<m;++i) {
        table[i] = j;
        if(p[i] == p[j]) {
            ++j;
        } else {
            j = 0;
        }
    }
}

int kmp(string s, string p, int i0=0, int j0=0) {
    int n = s.length(), m = p.length();

    int i = i0, j = j0;
    vector<int> s_to_p(n, -1);
    while(i < max(n, m)) {
        // cerr << i << s[i%n] << " " << j << p[j] << endl;
        if(s[i%n] == p[j]) {
            ++i;
            ++j;
            if(j == m) return i - m;
        } else if(j == 0) {
            ++i;
        } else {
            j = table[j];
        }
    }
    return -1;
}

int calc_period(string s, int n) {
    int s_period = INF;
    for(int i=1;i<=sqrt(n+1);++i) {
        if(n % i) continue;
        bool is_period = true;
        for(int j=0;j<n;++j) {
            if(s[j] != s[j%i]) {
                is_period = false;
                break;
            }
        }
        if(is_period) {
            s_period = min(s_period, i);
        }
        is_period = true;
        for(int j=0;j<n;++j) {
            if(s[j] != s[j%(n/i)]) {
                is_period = false;
                break;
            }
        }
        if(is_period) {
            s_period = min(s_period, n/i);
        }
    }
    return s_period;
}

bool is_inf(string s, string t, int n, int m) {
    int s_period = calc_period(s, n), t_period = calc_period(t, m);
    if(s_period == t_period) {
        bool are_same = true;
        for(int i=0;i<s_period;++i) {
            if(s[i] != t[i]) {
                are_same = false;
            }
        }
        if(are_same) return true;
    }
    return false;
}

int main() {
    string s,t;
    cin >> s >> t;
    int n = s.length(), m = t.length();

    // 答えが -1 の場合をここでふるい落とす
    // 周期が同じで，周期内の文字列が同じなら -1
    if(is_inf(s, t, n, m)) {
        cout << -1 << endl;
        return 0;
    }

    make_table(t, m);

    int i0 = 0, j0 = 0, ans = 0;
    vector<bool> end_of_pattern(2*n, false);
    while(i0 < 2*n) {
        int k = kmp(s+s, t, i0, j0);
        if(k == -1) {
            ++i0;
        } else {
            end_of_pattern[k+m-1] = true;
            i0 = k + m;
            j0 = table[m-1];
        }
    }

    vector<int> tmp_cnt(m, 0);
    for(int i=0;i<2*n;++i) {
        if(end_of_pattern[i]) {
            ++tmp_cnt[i%m];
            ans = max(ans, tmp_cnt[i%m]);
        } else {
            tmp_cnt[i%m] = 0;
        }
    }

    cout << ans << endl;

}

Submission status: Runtime Error

Solution code:
from math import ceil
import re

s = input()
t = input()

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

def matches1(S, W):
    def kmp_table():
        T = [0] * (len(W) + 1)

        T[0] = -1
        pos = 1
        cnd = 0
        while pos < len(W):
            if W[pos] == W[cnd]:
                T[pos] = T[cnd]
            else:
                T[pos] = cnd
                cnd = T[cnd]
                while cnd >= 0 and W[pos] != W[cnd]:
                    cnd = T[cnd]
                pos += 1
            cnd += 1
        T[pos] = cnd

        return T

    P = [False for x in S]
    j = 0
    k = 0
    T = kmp_table()

    while j < len(S):
        if W[k] == S[j]:
            j += 1
            k += 1
            if k == len(W):
                P[j - k] = True
                k = T[k]
        else:
            k = T[k]
            if k < 0:
                j += 1
                k += 1

    return P

# def matches(S, T, i):
#     M = len(T)
#     for j in range(len(T)):
#         if S[(i + j) % N] != T[j]:
#             return False
#     return True

start = 0
i = 0
count = 0
ans = 0
breaks = set()
# matches = [matches(s, t, i) for i in range(N)]
matches = matches1(s * ceil(M // N), t)
paths = [None for x in range(N)]
currentPath = []
# print(matches)
for i in range(N):
    start = i
    l = 0
    # print("Start", i)
    while matches[start]:
        # print(start)
        if start in currentPath:
            print(-1)
            exit(0)
        if paths[start] is not None:
            l += paths[start]
            break

        currentPath.append(start)
        l += 1
        start = (start + M) % N

    for j, x in enumerate(currentPath):
        paths[x] = l - j

    currentPath = []

paths = paths + [0]
# print(paths)
print(max(p for p in paths if p is not None))

Submission status: Runtime Error

Solution code:
from math import ceil
import re

s = input()
t = input()

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

def matches1(S, W):
    def kmp_table():
        T = [0] * (len(W) + 1)

        T[0] = -1
        pos = 1
        cnd = 0
        while pos < len(W):
            if W[pos] == W[cnd]:
                T[pos] = T[cnd]
            else:
                T[pos] = cnd
                cnd = T[cnd]
                while cnd >= 0 and W[pos] != W[cnd]:
                    cnd = T[cnd]
                pos += 1
            cnd += 1
        T[pos] = cnd

        return T

    P = [False for x in S]
    j = 0
    k = 0
    T = kmp_table()

    while j < len(S):
        if W[k] == S[j]:
            j += 1
            k += 1
            if k == len(W):
                P[j - k] = True
                k = T[k]
        else:
            k = T[k]
            if k < 0:
                j += 1
                k += 1

    return P

# def matches(S, T, i):
#     M = len(T)
#     for j in range(len(T)):
#         if S[(i + j) % N] != T[j]:
#             return False
#     return True

start = 0
i = 0
count = 0
ans = 0
breaks = set()
# matches = [matches(s, t, i) for i in range(N)]
matches = matches1(s * (ceil(len(M) // len(N))), t)
paths = [None for x in range(N)]
currentPath = []
# print(matches)
for i in range(N):
    start = i
    l = 0
    # print("Start", i)
    while matches[start]:
        # print(start)
        if start in currentPath:
            print(-1)
            exit(0)
        if paths[start] is not None:
            l += paths[start]
            break

        currentPath.append(start)
        l += 1
        start = (start + M) % N

    for j, x in enumerate(currentPath):
        paths[x] = l - j

    currentPath = []

paths = paths + [0]
# print(paths)
print(max(p for p in paths if p is not None))

Submission status: Runtime Error

Solution code:
import re

s = input()
t = input()

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

def matches1(S, W):
    def kmp_table():
        T = [0] * (len(W) + 1)

        T[0] = -1
        pos = 1
        cnd = 0
        while pos < len(W):
            if W[pos] == W[cnd]:
                T[pos] = T[cnd]
            else:
                T[pos] = cnd
                cnd = T[cnd]
                while cnd >= 0 and W[pos] != W[cnd]:
                    cnd = T[cnd]
                pos += 1
            cnd += 1
        T[pos] = cnd

        return T

    P = [False for x in S]
    j = 0
    k = 0
    T = kmp_table()

    while j < len(S):
        if W[k] == S[j]:
            j += 1
            k += 1
            if k == len(W):
                P[j - k] = True
                k = T[k]
        else:
            k = T[k]
            if k < 0:
                j += 1
                k += 1

    return P

# def matches(S, T, i):
#     M = len(T)
#     for j in range(len(T)):
#         if S[(i + j) % N] != T[j]:
#             return False
#     return True

start = 0
i = 0
count = 0
ans = 0
breaks = set()
# matches = [matches(s, t, i) for i in range(N)]
matches = matches1(s, t)
paths = [None for x in range(N)]
currentPath = []
# print(matches)
for i in range(N):
    start = i
    l = 0
    # print("Start", i)
    while matches[start]:
        # print(start)
        if start in currentPath:
            print(-1)
            exit(0)
        if paths[start] is not None:
            l += paths[start]
            break

        currentPath.append(start)
        l += 1
        start = (start + M) % N

    for j, x in enumerate(currentPath):
        paths[x] = l - j

    currentPath = []

paths = paths + [0]
# print(paths)
print(max(p for p in paths if p is not None))

Submission status: Runtime Error

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 で畳み込みを計算
    conv = np.round(signal.fftconvolve(s_ary, t_ary[::-1], mode="full", axes=(0,)).sum(axis=1))
    conv = conv[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: Runtime Error

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')
    exit(1)

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: Runtime Error

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')
    exit(1)
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: Runtime Error

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 = []

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 = ng[cnt] + 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)