← 返回题目列表

AtCoder · abc257_g

G. 前缀连接

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你两个字符串 S 和 T 由小写英文字母组成。

求最小正整数 k 这样你就可以选择(不一定不同) k 的前缀 S 使它们的串联与 T.

换句话说,找到最小的正整数 k 这样 存在一个 k-元组 (a_1,a_2,\ldots, a_k) 之间的整数 1 和 |S| 这样
T=S_{a_1}+S_{a_2}+\cdots +S_{a_k}, 哪里 S_i 表示子串 S 来自 1-st 通过 i第一个字符和 + 表示字符串的串联。

如果无法使其与 T,打印 -1 。

约束

  • 1 \leq |S| \leq 5\times 10^5
  • 1 \leq |T| \leq 5\times 10^5
  • S 和 T 是由小写英文字母组成的字符串。

输入

输入由标准输入按以下格式给出:

S
T

输出

打印最小正整数 k 这样你就可以选择 k 的前缀 S 使它们的串联与 T。 让它重合是不可能的 T,打印 -1 。


示例输入 1

aba
ababaab

示例输出 1

3

T= ababaab 可以写成 ab + aba + ab,其中 ab 和 aba 是前缀 S= aba.
既然无法表达 ababaab 具有两个或更少的前缀 aba,打印 3.


示例输入 2

atcoder
ac

示例输出 2

-1

既然无法表达 T 作为前缀的串联 S,打印 -1.