問題はこちら。

解説を見ながらなんとか実装した。

KMPは文字列検索を線形時間で終わらせるアルゴリズムで以前作っておいたものを使った。解説はwikipedia参照。最長経路の計算ではループもあり得るのでループ検出をする必要がある。

有向グラフのループ検出をするアルゴリズムを忘れかけていたので軽くメモしておく。

dfsで全探索するときに、訪問したことを示すvisitedというフラグと、処理が完了したことを示すfinishedというフラグを用意して、それぞれ行きがけと帰りがけにチェックする。finishしてないのにvisitedがTrueになっている頂点に訪れているということはループが存在するということなのでこれを使ってループ検出できる。

import sys
sys.setrecursionlimit(10**9)
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class KMP():
   def __init__(self, pattern):
       n = len(pattern)
       table = [0]*(n + 1)
       table[0], table[1] = -1, 0
       i, j = 2, 0
       while i <= n:
           if pattern[i - 1] == pattern[j]:
               table[i] = j + 1
               i += 1; j += 1
           elif j > 0:
               j = table[j]
           else:
               table[i] = 0
               i += 1
       self.size = n
       self.pattern = pattern
       self.table = table
   
   def search(self, text):
       l = len(text)
       n = self.size
       table = self.table
       pattern = self.pattern
       m, i = 0, 0
       ret = []
       while m + i < l:
           if pattern[i] == text[m + i]:
               i += 1
               if i == n:
                   ret.append(m)
                   m += i - table[i]
                   i = table[i]
           else:
               m += i - table[i]
               if i > 0:
                   i = table[i]
       return ret
       
def main():
   s = readline().strip()
   t = readline().strip()
   ls, lt = len(s), len(t)
   times = lt // ls + 2
   S_inf = s * times
   
   kmp = KMP(t)
   conn = [[] for _ in range(ls)]
   match = kmp.search(S_inf)
   for i in match:
       if i < ls:
           conn[i].append((i + lt) % ls)
           
   dp = [0]*ls
   visited = [False]*ls
   finished = [False]*ls
   
   def dfs(x):
       visited[x] = True
       for y in conn[x]:
           if visited[y]:
               if finished[y]:
                   dp[x] = max(dp[x], dp[y])
                   continue
               else:
                   print(-1)
                   sys.exit()
           dfs(y)
           dp[x] = max(dp[x], dp[y])
       dp[x] += 1
       finished[x] = True
       
   for x in range(ls):
       if finished[x]:
           continue
       dfs(x)
       
   print(max(dp) - 1)
   
if __name__ == "__main__":
  main()