【POJ】2406 Power Strings

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-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
", work());

	}

	return 0;

}

　　
 
고전 문 제 는........................................................................
sa 의 방법 은 height 를 구 한 후에 저 희 는 suffix (1) 와 suffix (k + 1) 의 가장 긴 공공 접두사 가 n - k 인지 아 닌 지 만 일치 합 니 다. k 는 매 거 진 길이 입 니 다. 왜 그런 지 스스로 생각 하 세 요.