Power string(poj 2406)

时间:2021-10-17 12:03:59

题目大意,给出一个字符串s,求最大的k,使得s能表示成a^k的形式,如 abab 可以表示成(ab)^2;

方法:
首先 先求kmp算法求出next数组;如果 len mod (len-next[len])==0 ,答案就是 len /(len-next[len]),否则答案是1;
证明如下;
如果s能表示成 a^k的形式且k>1,k尽可能大,即s可以表示成aaaaaa(k个a);那么next[len]就等于k-1个a的长度;
aaaaaaa
  aaaaaaa
那么 (len-next[len])a的长度了;显然len mod (len-next[len]) =0, len /(len-next[len])就是k;
否则s不能表示成这样的形式 k=1;
证明完毕,虽然不是很严谨。