You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

字符串乘法的定义：

• 将字符串 $T$ 乘上整数 $k$，就相当于把 $T$ 重复 $k$ 次。

如 pk*4 = pkpkpkpk。现在给你一个字符串 $S$，请你找出一个字符串 $T$ 和一个整数 $k$ 并满足 T*k = S。还不够，在所有这样成立的等式里，你还需要找出 $k$ 最大的一个等式，并输出这个等式。可以证明，答案是唯一的。

格式

输入

字符串 $S$。

输出

输出所有成立的等式中，$k$ 最大的一个等式。

样例

pkpkpkpk

pk*4 = pkpkpkpk

bcbcbc

bc*3 = bcbcbc

hello

hello*1 = hello

数据范围

样例一：有三组合法的等式，分别为 pk*4 = pkpkpkpk，pkpk*2 = pkpkpkpk，pkpkpkpk*1 = pkpkpkpk，但只有第一组被认为是正确的。

• 字符串的长度不超过 $10^3$
• 思考：如果字符串的长度不超过 $10^6$，应该怎么做呢？