北大 acm 2406 Power Strings 解题报告

Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 10581 Accepted: 4410

Description

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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

abcdaaaaababab

Sample Output

143

用暴力解决思路:每次取不同的底数字符串直到条件成立

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
int getString(char f[],char to[],int m,long n) //获取底数字符串
{
long i;
for(i=0;i<=n;i++)
to[i]=f[i];
to[n+1]='\0';
return 0;
}
int compare(char str[],char sou[],long n,long stlen,long slen) //进行比较
{
long i,k=0;
for(i=n;i<stlen;i++)
{
if(sou[k++]!=str[i]) return 0; //一旦发现有不相同就返回0
if(k==slen) k=0;
}
return 1;
}
int main()
{
char str[1000002],sour[1000002];;
long len,pow,i;
while(scanf("%s",str)!=-1&&strcmp(str,".")!=0)
{
len=strlen(str);
for(i=0;i<len;i++)
if(len%(i+1)==0) //必须能被字符串长度整除
{
getString(str,sour,0,i); //获取底数字符串
if(compare(str,sour,i+1,len,strlen(sour))==1) //返回1说明底数字符串为真
{
pow=len/(i+1);
break;
}
}
cout<<pow<<endl;
}
return 0;
}