Problem p02962 (python)

Fixed submission:
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    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.ktable[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)
#    edges = [[] for i in range(n)]
#    for i in range(n):
#        if b[i]:
#            edges[i].append((i+m)%n)
#    
#    def dfs(node):
#        if visited[node] == 1:
#            return True
#        if visited[node] == 2:
#            return False
#        visited[node] = 1
#        for nei in edges[node]:
#            if dfs(nei):
#                return True
#        visited[node] = 2
#        res.append(node)
#        return False
#    visited = [-1] * n
#    res = []
#    for i in range(n):
#        if dfs(i):
#            return -1
#    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])
#    return ans

            
    visited = [0]*n
    loop = False
    ans = 0
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = 1
        cur = i
        right = 0
        while b[cur]:
            nxt = (cur + m) % n
            if visited[nxt]:
                loop = True
                break
            visited[nxt] = 1
            cur = nxt
            right += 1
        cur = i
        left = 0
        while b[(cur-m)%n]:
            nxt = (cur-m) % n
            if visited[nxt]:
                loop = True
                break
            visited[nxt] = 1
            cur = nxt
            left += 1
        if not loop:
            ans = max(ans, right+left)
        else:
            ans = -1
            break
    return ans

if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
import collections
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    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.ktable[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)
    while len(s) < m + n:
        s += s
    a = KMP(t)
    b = a.match(s)
    
    graph = [[] for i in range(n)]
    for i in range(n):
        k = (i+m)%n
        if b[i]:
            graph[i].append(k)
    
    def dfs(node):
        if visited[node] == 1: return True
        if visited[node] == 2: return False

        visited[node] = 1
        for nei in graph[node]:
            if dfs(nei): return True
        visited[node] = 2
        res.append(node)
        return False

    visited = [0] * n
    res = []
    for i in range(n):
        if dfs(i):
            return -1
    
    res = res[::-1]
    dp = [0] * n

    for k in range(n):
        i = res[k]
        for j in graph[i]:
            dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
import collections
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    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.ktable[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)
    
    graph = [[] for i in range(n)]
    for i in range(n):
        k = (i+m)%n
        if b[i]:
            graph[i].append(k)
    
    def dfs(node):
        if visited[node] == 1: return True
        if visited[node] == 2: return False

        visited[node] = 1
        for nei in graph[node]:
            if dfs(nei): return True
        visited[node] = 2
        res.append(node)
        return False

    visited = [0] * n
    res = []
    for i in range(n):
        if dfs(i):
            return -1
    
    res = res[::-1]
    dp = [0] * n

    for k in range(n):
        i = res[k]
        for j in graph[i]:
            dp[j] = max(dp[j], dp[i] + 1)
    return max(dp)

if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
import collections
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    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.ktable[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)
    
    graph = collections.defaultdict(set)
    for i in range(n):
        k = (i+m)%n
        if b[i]:
            graph[i].append(k)
    
    def dfs(node):
        if visited[node] == 1: return True
        if visited[node] == 2: return False

        visited[node] = 1
        for nei in graph[node]:
            if dfs(nei): return True
        visited[node] = 2
        res.append(node)
        return False

    visited = [0] * n
    res = []
    for i in range(n):
        if dfs(i):
            return -1
    
    res = res[::-1]
    dp = [0] * n

    for k in range(n):
        i = res[k]
        for j in graph[i]:
            dp[j] = max(dp[j], dp[i] + 1)
            ans = max(dp)
    return ans

if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    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.ktable[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)
    edges = [[] for i in range(n)]
    indegree = [0] * n
    for i in range(n):
        k = (i+m)%n
        if b[i]:
            edges[i].append(k)
            indegree[k] += 1
    
    def topSort():
        q = collections.deque()
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)
        while q:
            cur = q.popleft()
            res.append(cur)
            for nei in edges[cur]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)
        return len(res) == n
    
    res = []
    dp = [0] * n
    flag = topSort()
    if flag:
        for k in range(n):
            i = res[k]
            for j in edges[i]:
                dp[j] = max(dp[j], dp[i] + 1)
        ans = max(dp)
    else:
        ans = -1
    return ans
     

if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    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.ktable[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)
    edges = [[] for i in range(n)]
    for i in range(n):
        if b[i]:
            edges[i].append((i+m)%n)
    
    def dfs1(node):
        if visited[node] == 1:
            return True
        if visited[node] == 2:
            return False
        visited[node] = 1
        for nei in edges[node]:
            if dfs1(nei):
                return True
        visited[node] = 2
        return False
    visited = [-1] * n
    for i in range(n):
        if dfs1(i):
            return -1
    
    
    
    def dfs(node, adj, dp, vis):  
        
        vis[node] = True  
        for i in range(0, len(adj[node])):   
            if not vis[adj[node][i]]: 
                dfs(adj[node][i], adj, dp, vis)   
            dp[node] = max(dp[node], 1 + dp[adj[node][i]])   
         
    def findLongestPath(adj, n):  
    
        dp = [0] * n 
          
        vis = [False] * n
     
        for i in range(n):   
            if not vis[i]:  
                dfs(i, adj, dp, vis) 
                
        ans = 0 
        for i in range(n):   
            ans = max(ans, dp[i])  
           
        return ans
    
    ans = findLongestPath(edges, n)
    return ans

            
#    visited = [0]*n
#    loop = False
#    ans = 0
#    for i in range(n):
#        if visited[i]:
#            continue
#        visited[i] = 1
#        cur = i
#        right = 0
#        while b[cur]:
#            nxt = (cur + m) % n
#            if visited[nxt]:
#                loop = True
#                break
#            visited[nxt] = 1
#            cur = nxt
#            right += 1
#        cur = i
#        left = 0
#        while b[(cur-m)%n]:
#            nxt = (cur-m) % n
#            if visited[nxt]:
#                loop = True
#                break
#            visited[nxt] = 1
#            cur = nxt
#            left += 1
#        if not loop:
#            ans = max(ans, right+left)
#        else:
#            ans = -1
#            break
#    return ans

if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    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.ktable[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)
    edges = [[] for i in range(n)]
    for i in range(n):
        if b[i]:
            edges[i].append((i+m)%n)
    
    def dfs(node):
        if visited[node] == 1:
            return True
        if visited[node] == 2:
            return False
        visited[node] = 1
        for nei in edges[node]:
            if dfs(nei):
                return True
        visited[node] = 2
        res.append(node)
        return False
    visited = [-1] * n
    res = []
    for i in range(n):
        if dfs(i):
            return -1
    
    res = res[::-1]
    dp = [0] * n
    ans = 0
    for i in range(n):
        t = res[i]
        for c in edges[t]:
            dp[c] = max(dp[c], dp[t] + 1)
            ans = max(ans, dp[c])
    return ans

            
#    visited = [0]*n
#    loop = False
#    ans = 0
#    for i in range(n):
#        if visited[i]:
#            continue
#        visited[i] = 1
#        cur = i
#        right = 0
#        while b[cur]:
#            nxt = (cur + m) % n
#            if visited[nxt]:
#                loop = True
#                break
#            visited[nxt] = 1
#            cur = nxt
#            right += 1
#        cur = i
#        left = 0
#        while b[(cur-m)%n]:
#            nxt = (cur-m) % n
#            if visited[nxt]:
#                loop = True
#                break
#            visited[nxt] = 1
#            cur = nxt
#            left += 1
#        if not loop:
#            ans = max(ans, right+left)
#        else:
#            ans = -1
#            break
#    return ans

if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
class KMP():
    def __init__(self, pattern):
        self.pattern = pattern
        self.n = len(pattern)
        self.create_k_table()
    
    def create_k_table(self):
        ktable = [-1]*(self.n+1)
        j = -1
        for i in range(self.n):
            while j >= 0 and self.pattern[i] != self.pattern[j]:
                j = ktable[j]
            j += 1
            if i+1 < self.n and self.pattern[i+1] == self.pattern[j]:
                ktable[i+1] = ktable[j]
            else:
                ktable[i+1] = j
        self.ktable = ktable

    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.ktable[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)
    edges = [[] for i in range(n)]
    for i in range(n):
        if b[i]:
            edges[i].append((i+m)%n)
    
    def dfs(node):
        if visited[node] == 1:
            return True
        if visited[node] == 2:
            return False
        visited[node] = 1
        for nei in edges[node]:
            if dfs(nei):
                return True
        visited[node] = 2
        res.append(node)
        return False
    visited = [-1] * n
    res = []
    for i in range(n):
        if dfs(i):
            return -1
    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])
    return ans

            
#    visited = [0]*n
#    loop = False
#    ans = 0
#    for i in range(n):
#        if visited[i]:
#            continue
#        visited[i] = 1
#        cur = i
#        right = 0
#        while b[cur]:
#            nxt = (cur + m) % n
#            if visited[nxt]:
#                loop = True
#                break
#            visited[nxt] = 1
#            cur = nxt
#            right += 1
#        cur = i
#        left = 0
#        while b[(cur-m)%n]:
#            nxt = (cur-m) % n
#            if visited[nxt]:
#                loop = True
#                break
#            visited[nxt] = 1
#            cur = nxt
#            left += 1
#        if not loop:
#            ans = max(ans, right+left)
#        else:
#            ans = -1
#            break
#    return ans

if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
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 True
        if visited[node] == 2:
            return False
            
        visited[node] = 1
        
        for nei in edges[node]:
            if dfs(nei):
                return True
        visited[node] = 2
        res.append(node)
        return False
    
    res = []
    for i in range(n):
        if 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()

Buggy submission (verdict: Runtime Error):
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()

Buggy submission (verdict: Runtime Error):
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()

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)