分数: 300 点
问题陈述
给你一个字符串 S 长度 N 和另一个字符串 T 长度 M。 这些字符串由小写英文字母组成。
一个字符串 X 被称为 好字符串 当以下条件全部满足时:
- 让 L 的长度 X. L 可以被两者整除 N 和 M.
- 连接 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)第一个字符 X,在不改变顺序的情况下,结果是 S.
- 连接 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)第一个字符 X,在不改变顺序的情况下,结果是 T.
确定是否存在好的字符串。如果存在,找到最短的该字符串的长度。
约束
- 1 \leq N,M \leq 10^5
- S 和 T 由小写英文字母组成。
- |S|=N
- |T|=M
输入
输入由标准输入按以下格式给出:
N M S T
输出
如果不存在好的字符串,则打印 -1;如果存在,则打印最短的此类字符串的长度。
示例输入 1
3 2 acp ae
示例输出 1
6
例如,字符串 accept 是一个很好的字符串。
没有比这更短的好字符串了,所以答案是 6.
示例输入 2
6 3 abcdef abc
示例输出 2
-1
示例输入 3
15 9 dnsusrayukuaiia dujrunuma
示例输出 3
45