← 返回题目列表

AtCoder · agc028_a

A. 两个缩写

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

分数: 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