Power Strings

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 1

- abcd

  aaaa

  ababab

  .

Sample Output 1

思路1

暴力

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

using namespace std;

const int Max=1000001;

string a;

int x,n,m;

int p[Max];

void prime(int n)

{

	int k=(int)sqrt(n*1.0);

	p[1]=1;

	for(int i=2; i<=k; i++)

		if(n%i==0)

			p[++m]=i;

	int end=m;

	if(k*k==n)	end--;

	for(int i=end; i>=1; i--)

		p[++m]=n/p[i];

}

bool ok(int x)

{

	string s=a.substr(0,x);

	for(int i=0; i<a.size(); i+=x)

		if(s!=a.substr(i,x))	return false;

	return true;

}

int main()

{

	while(getline(cin,a))

	{

		x=1,n=a.size();m=1;

		prime(n);

		while(x<=m)

		{

			if(ok(p[x]))

			{cout<<a.size()/p[x]<<endl;break;}

			x++;

		}

	}

	return 0;

}

思路2

利用\(KMP\)的\(next[]\)数组

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

using namespace std;

const int Max=1000001;

string a;

int N,M,ans,nx[Max];

void makenx(int M)

{

	memset(nx,0,sizeof(nx));

	int i=0,j=-1;

	nx[i]=j;

	while(i<M)

	{

		if(j==-1||a[i]==a[j])	i++,j++,nx[i]=j;

		else    j=nx[j];

	}

}

int main()

{

	bool fl;

	while(getline(cin,a)&&a[0]!='.')

	{

		fl=true;

		M=a.size();makenx(M);

		if(M%(M-nx[M])==0)	cout<<M/(M-nx[M])<<endl;

		else	cout<<1<<endl;

	}

	return 0;

}

巴特西

Power Strings[poj2406]题解

Power Strings

Description

Input

Output

Sample Input 1

Sample Output 1

思路1

暴力

思路2

利用\(KMP\)的\(next[]\)数组

最新文章

热门文章