北大 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

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

代码

#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;
}