2399.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2399 on 2006-10-10 at 15:32:08 */
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
const int L = 102400, KN = 18;
const int WL = 1024, WN = 128;

class SuffixArray {
private:
	int n, sn, a[L], sa[L], rank[L], h[L], hei[L];
	int st[KN][L], id[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();
	void initRMQ();
	int query(int, int);
public:
	bool make();
	void checkDNA();
};
void SuffixArray::radixSort(int* a, int* b, int* r, int n, int K) {
	int *c = new int[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];
	delete[] c;
}
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 = new int[n02+3], *R0 = new int[n0]; R[n02] = R[n02+1] = R[n02+2] = 0;
	int *SA12 = new int[n02+3], *SA0 = new int[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);
		}
	}
	delete[] R; delete[] R0; delete[] SA12; delete[] SA0;
}
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) { h[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::initRMQ() {
	for(int i = 0; i < sn; i++) st[0][i] = hei[i];
	for(int i = 1, k = 2; k < sn; i++, k <<= 1)
		for(int j = 0; j < sn; j++) {
			int sk = j+(k>>1); st[i][j] = st[i-1][j];
			if(sk < sn) st[i][j] <?= st[i-1][sk];
		}
}
int SuffixArray::query(int x, int y) {
	int len = y-x, bl;
	for(bl = -1; len != 0; bl++) len >>= 1;
	return min(st[bl][x+1], st[bl][y-(1<<bl)+1]);
}
bool SuffixArray::make() {
	char w[WL];
	scanf("%d", &n);
	if(n == 0) return false;
	for(int i = sn = 0; i < n; i++) {
		scanf("\n"); gets(w);
		for(int j = 0; w[j] != 0; j++) { id[sn] = i; a[sn++] = w[j]-'a'+1+n; }
		a[sn++] = i+1;
	}
	a[sn] = a[sn+1] = a[sn+2] = 0;
	suffixBuild(a, sa, sn, n+27);
	initHR(); initRMQ();
	return true;
}
void SuffixArray::checkDNA() {
	vector<int> index; int len = 0;
	int b, e = n, cnt[WN] = { 0 }, qn = 0, nd = n/2+1;
	for(b = n; b != sn; b++) {
		for(; e != sn && qn < nd; e++) {
			if(cnt[id[sa[e]]] == 0) qn++;
			cnt[id[sa[e]]]++;
		}
		if(qn < nd) break;
		int ml = query(b, e-1);
		if(ml < len || ml == 0) {}
		else if(ml > len) { index.clear(); index.push_back(b); }
		else if(query(index.back(), b) < ml) index.push_back(b);
		len >?= ml;
		cnt[id[sa[b]]]--;
		if(cnt[id[sa[b]]] == 0) qn--;
	}
	if(len <= 0) { printf("?\n"); return; }
	for(int i = 0; i < index.size(); i++, putchar('\n'))
		for(int j = sa[index[i]], k = 0; k < len; j++, k++)
			putchar(a[j]-n-1+'a');
}
 
SuffixArray sa;

int main()
{
	for(int t = 0; sa.make(); t++) {
		if(t != 0) putchar('\n');
		sa.checkDNA();
	}
	
	return 0;
}