poj 2406 Power Strings(KMP&思维) - c++编程基础

TOP

poj 2406 Power Strings(KMP&思维)

2015-07-24 05:41:42 来源: 作者: 【大中小】浏览:5次

Power Strings

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 31093		Accepted: 12974

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

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

Source

Waterloo local 2002.07.01

题意：

定义a^n为aaaaa...aaa。a为一个字符串。现在给你一个字符串问你把它写成a^n的形式。就你求出最大的n。

思路：

kmp水题。关键是思维。需要对KMP有一定认识。画个图就明白了。

用自己和自己匹配。一次失配后会形成上图的状态。剪头所指的位置都是相同的。因为自己和自己匹配嘛。所以只需要判断凸出去的长度能不能整除整个串的长度就行了。不行再往前移。行的话答案就是突出去的长度了。

详细见代码：

#include 
  
   
#include
   
     #include
    
      using namespace std; const int maxn=1000100; int f[maxn]; char txt[maxn]; void getf(char *p) { int i,j,m=strlen(p); f[0]=f[1]=0; for(i=1;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++智能指针--auto_ptr指针	下一篇：Codeforces 444C（线段树）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: