【POJ】2406 Power Strings

时间：2021-01-18 19:54:55

http://poj.org/problem?id=2406

题意：给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的，求 R 的最大值。（长度<=1000000）

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <iostream>

using namespace std;

int p[2000000];

char s[2000000];

int main() {

	while(scanf("%s", s+1), s[1]!='.') {

		int j=0, n=strlen(s+1); p[1]=0;

		for(int i=2; i<=n; ++i) {

			while(j && s[j+1]!=s[i]) j=p[j];

			if(s[j+1]==s[i]) ++j;

			p[i]=j;

		}

		if(n%(n-p[n])==0) printf("%d\n", n/(n-p[n]));

		else puts("1");

	}

	return 0;

}

kmp求出next后那么最短循环串的长度为n-next[n]，只需要判断n是否整除它即可。

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

const int N=2000005;

inline void sort(int *x, int *y, int *sa, int n, int m) {

	static int c[N], i;

	for(i=0; i<m; ++i) c[i]=0;

	for(i=0; i<n; ++i) ++c[x[y[i]]];

	for(i=1; i<m; ++i) c[i]+=c[i-1];

	for(i=n-1; i>=0; --i) sa[--c[x[y[i]]]]=y[i];

}

inline void hz(int *a, int *sa, int n, int m) {

	static int t1[N], t2[N], i, j, p, *x, *y, *t;

	x=t1, y=t2;

	for(i=0; i<n; ++i) x[i]=a[i], y[i]=i;

	sort(x, y, sa, n, m);

	for(j=1, p=1; p<n; j<<=1, m=p) {

		p=0;

		for(i=n-j; i<n; ++i) y[p++]=i;

		for(i=0; i<n; ++i) if(sa[i]-j>=0) y[p++]=sa[i]-j;

		sort(x, y, sa, n, m);

		for(t=x, x=y, y=t, p=1, x[sa[0]]=0, i=1; i<n; ++i)

			x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]?p-1:p++;

	}

}

inline void geth(int *s, int *sa, int *rank, int *h, int n) {

	static int j, i, k;

	for(i=1; i<=n; ++i) rank[sa[i]]=i;

	for(k=0, i=1; i<=n; h[rank[i++]]=k)

		for(k?--k:0, j=sa[rank[i]-1]; s[i+k]==s[j+k]; ++k);

}

int a[N], sa[N], h[N], rank[N], n;

char s[N];

inline int work() {

	static int len[N], pos;

	pos=rank[1];

	for(int i=pos, mn=h[i]; i>1; --i) mn=min(h[i], mn), len[i-1]=mn;

	for(int i=pos+1, mn=h[i]; i<=n; ++i) mn=min(h[i], mn), len[i]=mn;

	int sq=sqrt(n+0.5);

	for(int k=1; k<=sq; ++k) if(n%k==0 && len[rank[k+1]]==n-k) return n/k;

	return 1;

}

int main() {

	while(scanf("%s", s+1), s[1]!='.') {

		n=strlen(s+1);

		for(int i=1; i<=n; ++i) a[i]=s[i];

		a[0]=0;

		hz(a, sa, n+1, 255);

		geth(a, sa, rank, h, n);

		printf("%d\n", work());

	}

	return 0;

}

　　

经典题...可是我tle了......因为本题听说是用kmp.............QAQ

sa的做法就是，求出height后，我们只匹配suffix(1)和suffix(k+1)的最长公共前缀是否为n-k即可，k是枚举的长度...至于为什么，请自己想...

相关文章