1534.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1534 on 2006-08-26 at 15:18:37 */ 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

const int L = 1 << 17;
 
class SuffixArray {
private:
	int sn, tl, a[L], sa[L], rank[L], h[L], hei[L];
	char w[L];
	inline int less(int t0, int r0, int t1, int r1) const 
		{ return t0 < t1 || (t0 == t1 && r0 <= r1); }
	inline int less(int t0, int r0, int c0, int t1, int r1, int c1) const 
		{ return t0 < t1 || (t0 == t1 && less(r0, c0, r1, c1)); }
	void radixSort(int*, int*, int*, int, int);
	void suffixBuild(int*, int*, int, int);
	void initHR();
public:
	void make();
	void checkPiece();
};
void SuffixArray::radixSort(int* a, int* b, int* r, int n, int K) {
	int c[K+1]; memset(c, 0, sizeof(int)*(K+1));
	for(int i = 0; i < n; i++) c[r[a[i]]]++;
	for(int i = 0, sum = 0; i <= K; i++)
		{ int t = c[i]; c[i] = sum; sum += t; }
	for(int i = 0; i < n; i++) b[c[r[a[i]]]++] = a[i];
}
void SuffixArray::suffixBuild(int* T, int* SA, int n, int K) {
	int n0 = (n+2)/3, n1 = (n+1)/3, n2 = n/3, n02 = n0+n2;
	int R[n02+3], R0[n0]; R[n02] = R[n02+1] = R[n02+2] = 0;
	int SA12[n02+3], SA0[n0]; SA12[n02] = SA12[n02+1] = SA12[n02+2] = 0;
	for(int i = 0, j = 0; i < n+(n0-n1); i++)
		if(i%3) R[j++] = i;
	radixSort(R, SA12, T+2, n02, K);
	radixSort(SA12, R, T+1, n02, K);
	radixSort(R, SA12, T, n02, K);
	int name = 0, c0 = -1, c1 = -1, c2 = -1;
	for(int i = 0; i < n02; i++) {
		if(T[SA12[i]] != c0 || T[SA12[i]+1] != c1 || T[SA12[i]+2] != c2)
			{ name++; c0 = T[SA12[i]]; c1 = T[SA12[i]+1]; c2 = T[SA12[i]+2]; }
		if(SA12[i] % 3 == 1) R[SA12[i]/3] = name;
		else R[SA12[i]/3+n0] = name;
	}
	if(name != n02) {
		suffixBuild(R, SA12, n02, name);
		for(int i = 0; i < n02; i++) R[SA12[i]] = i + 1;
	} else
		for(int i = 0; i < n02; i++) SA12[R[i]-1] = i;
	for(int i = 0, j = 0; i < n02; i++)
		if(SA12[i] < n0) R0[j++] = SA12[i]*3;
	radixSort(R0, SA0, T, n0, K);
	for(int i = 0, j = 0, k = n0-n1; i < n; i++) {
#define getI(m) (SA12[m] < n0 ? SA12[m]*3+1 : (SA12[m]-n0)*3+2)
		int p = getI(k), t = SA0[j];
		if(SA12[k] < n0 ?
			less(T[p], R[SA12[k]+n0], T[t], R[t/3]) :
			less(T[p], T[p+1], R[SA12[k]-n0+1], T[t], T[t+1], R[t/3+n0])) {
			SA[i] = p; k++;
			if(k != n02) continue;
			for(i++; i < n; i++, j++) SA[i] = SA0[j];
		} else {
			SA[i] = t; j++;
			if(j != n0) continue;
			for(i++; i < n; i++, k++) SA[i] = getI(k);
		}
	}
}
void SuffixArray::initHR() {
	for(int i = 0; i < sn; i++) rank[sa[i]] = i;
	for(int i = 0; i < sn; i++) {
		if(rank[i] == 0) continue;
		int j = i, k = sa[rank[i]-1], p = (i == 0 || h[i-1] <= 1) ? 0 : h[i-1]-1;
		for(; a[j+p] == a[k+p]; j++, k++);
		h[i] = j-i+p;
	}
	for(int i = 0; i < sn; i++) hei[i] = h[sa[i]];
}
void SuffixArray::make() {
	scanf("\n");
	tl = sn = strlen(gets(w));
	w[sn++] = 1;
	while(gets(w+sn) != NULL) {
		sn += strlen(w+sn);
		w[sn++] = '.';
	}
	w[sn++] = 2; w[sn] = 0;
	for(int i = 0; i < sn; i++) {
		if(isupper(w[i])) a[i] = w[i]-'A'+'a';
		else a[i] = w[i];
	}
	a[sn] = a[sn+1] = a[sn+2] = 0;
	suffixBuild(a, sa, sn, 127); initHR();
}
void SuffixArray::checkPiece() {
	int len[tl+1], pos[tl]; memset(len, 0, sizeof(int)*(tl+1));
	for(int i = 2, mh = L, mp = 0; i < sn; i++) {
		if(sa[i] >= tl) { mh = L; mp = sa[i]; continue; }
		if(i != 2) mh <?= hei[i];
		if(mh != L && len[sa[i]] < mh) { len[sa[i]] = mh; pos[sa[i]] = mp; }
	}
	for(int i = sn-1, mh = L, mp = 0; i >= 2; i--) {
		if(sa[i] >= tl) { mh = hei[i]; mp = sa[i]; continue; }
		if(mh != L && len[sa[i]] < mh) { len[sa[i]] = mh; pos[sa[i]] = mp; }
		mh <?= hei[i];
	}
	int pn = 0;
	for(int i = 0; i < tl; i += len[i], pn++)
		while(w[i] == ' ') i++;
	printf("%d\n", pn);
	for(int i = 0; i < tl; i += len[i]) {
		while(w[i] == ' ') i++;
		if(i == tl) break;
		printf("%.*s\n", len[i], w+pos[i]);
	}
}

SuffixArray sa;

int main()
{
	sa.make();
	sa.checkPiece();
	
	return 0;
}