最新消息:点击查看大S的省钱秘笈

POJ 2406 Power Strings C语言版

POJ题解 Slyar 65浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

Description

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

Slyar:说一下题目大意。a是一个字符串,记s=a^n为a重复n次所形成的字符串。比如说a是abcd,那么当n=3时,a^3就是abcdabcdabcd。现在给出字符串s,求出最大的重复次数n。

本题利用的还是KMP模式匹配算法,当然你需要真正理解Next[i]的含义才可以自己写出代码,我在这里纠结了很久...

这里有一篇我写的KMP学习心得,可以适当参考。

//www.slyar.com/blog/kmp.html

转载请注明:Slyar Home » POJ 2406 Power Strings C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址