module mod_union_find
  implicit none
  type union_find
    integer :: n
    integer, pointer :: par(:), rnk(:), siz(:)
    logical, pointer :: ntr(:), usd(:)
  end type union_find
  private
  public :: union_find, init_union_find, release_union_find
  public :: find, same, unite, size_of, not_tree, used, is_used
contains
  subroutine init_union_find(uf,n)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: n
    integer :: i
    uf%n = n
    allocate(uf%par(n),uf%rnk(n),uf%siz(n),uf%ntr(n),uf%usd(n))
    uf%rnk = 0
    uf%siz = 1
    uf%ntr = .false.
    uf%usd = .false.
    do i = 1, n
      uf%par(i) = i
    end do
    return
  end subroutine init_union_find
  subroutine release_union_find(uf)
    implicit none
    type(union_find), intent(inout) :: uf
    if (associated(uf%par)) deallocate(uf%par)
    if (associated(uf%rnk)) deallocate(uf%rnk)
    if (associated(uf%siz)) deallocate(uf%siz)
    return
  end subroutine release_union_find
  recursive function find(uf,i) result(j)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i
    integer :: j
    if (uf%par(i).ne.i) then
      uf%par(i) = find(uf,uf%par(i))
    end if
    j = uf%par(i)
    return
  end function find
  function same(uf,i,j) result(y)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i, j
    logical :: y
    y = find(uf,i).eq.find(uf,j)
  end function same
  subroutine unite(uf,i,j)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i, j
    integer :: x, y
    x = find(uf,i)
    y = find(uf,j)
    if (x.eq.y) then
      uf%ntr(x) = .true.
      return
    end if
    if (uf%rnk(x).lt.uf%rnk(y)) then
      uf%par(x) = y
      uf%siz(y) = uf%siz(y)+uf%siz(x)
      if (uf%ntr(x)) uf%ntr(y) = .true.
    else
      uf%par(y) = x
      uf%siz(x) = uf%siz(x)+uf%siz(y)
      if (uf%ntr(y)) uf%ntr(x) = .true.
      if (uf%rnk(x).eq.uf%rnk(y)) uf%rnk(x) = uf%rnk(x)+1
    end if
    return
  end subroutine unite
  function size_of(uf,i) result(s)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i
    integer :: s
    s = uf%siz(find(uf,i))
  end function size_of
  function not_tree(uf,i) result(b)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i
    logical :: b
    b = uf%ntr(find(uf,i))
    return
  end function not_tree
  subroutine used(uf,i)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i
    uf%usd(find(uf,i)) = .true.
    return
  end subroutine used
  function is_used(uf,i) result(b)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i
    logical :: b
    b = uf%usd(find(uf,i))
    return
  end function is_used
end module mod_union_find
program strings_of_eternity
  use mod_union_find
  implicit none
  type(union_find) :: uf
  character(500000) :: s, t
  character(2500000) :: ss
  character(5000000) :: ts
  integer :: n, m, x, i, z(5000000) = 0
  logical :: ok(500000) = .false.
  read(*,*) s
  read(*,*) t
  n = len_trim(s)
  m = len_trim(t)
  ss = trim(s)//trim(s)//trim(s)
  if (len_trim(ss) < 2*m) ss = repeat(trim(ss),(2*m+len_trim(ss)-1)/len_trim(ss))
  ts = trim(t)//trim(ss)
  x = len_trim(ts)
  z(1:x) = z_algorithm(ts(1:x))
  do i = 1, n
    if (z(m+i) >= m) ok(i) = .true.
  end do
  call init_union_find(uf,n)
  do i = 1, n
    if (ok(i) .and. ok(mod(m+i-1,n)+1)) then
      if (same(uf,i,mod(m+i-1,n)+1)) then
        write(*,'(i0)') -1
        stop
      end if
      call unite(uf,i,mod(m+i-1,n)+1)
    end if
  end do
  x = 0
  do i = 1, n
    if (ok(i)) x = max(x,size_of(uf,i))
  end do
  write(*,'(i0)') x
  stop
contains
  function z_algorithm(s) result(z)
    implicit none
    character(*) :: s
    integer :: z(len_trim(s)), n, i, j, k
    z = 0
    n = len_trim(s)
    z(1) = n
    i = 1
    j = 0
    do while (i < n)
      do while (i+j < n .and. s(j+1:j+1) == s(i+j+1:i+j+1))
        j = j+1
      end do
      z(i+1) = j
      if (j == 0) then
        i = i+1
        cycle
      end if
      k = 1
      do while (i+k < n .and. k+z(k+1) < j)
        z(i+k+1) = z(k+1)
        k = k+1
      end do
      i = i+k
      j = j-k
    end do
    return
  end function z_algorithm
end program strings_of_eternity

Measured memory_bytes: 30724