AT4435 [AGC028A]两个缩写

题目描述

给定一个长度为 N 的字符串 S 和一个长度为 M 的字符串 T ，这些字符串由小写英文字符组成。

当一个字符串 X 满足以下条件时，称为好字符串 （good string） 。

• X 的长度 L 可以被 N 和 M 整除
• 连接 X 的 1, L / N +1,2× L / N +1, ...( N −1)× L / N +1 且不改变顺序，结果为 S
• 连接 X 的 1, L / M +1,2× L / M +1, ...( M −1)× L / M +1 且不改变顺序，结果为 T

判断是否存在好字符串。如果存在，请找到最短的此类字符串的长度。

输入格式

按照以下格式标准输入：

 $ N $   $ M $ 
 $ S $ 
 $ T $ 

输出格式

如果不存在任何一个好字符串，则输出 -1 ；如果存在，则打印最短的此类字符串的长度。

输入输出样例

样例见原题面

制约

• 1≤ N , M ≤10^5
• S , T 由小写字母组成
• ∣ S ∣= N
• ∣ T ∣= M

样例说明1

accept 字符串是一个好字符串。没有比这更短的字符串了，所以答案是6。