1969.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1969 on 2006-08-13 at 12:13:14 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int L = 102400;
const char END_INFO[][32] = { "END TDP CODEBASE", "END JCN CODEBASE" };
 
char text[L];
int tjn;
 
class Segment {
public:
	int pos, len;
	void set(int p, int l) { pos = p; len = l; }
	int rightEnd() const { return pos+len; }
	void print() const { printf("LENGTH %d POSITION %d\n%.*s\n", len, pos-tjn-1, len, text+pos); }
};
 
Segment seg[L];
 
class SuffixArray {
private:
	int sn, a[L], sa[L], rank[L], h[L], hei[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();
	int checkInfr();
};
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++) {
		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() {
	sn = 0; scanf("\n");
	char *w = text;
	for(int i = 0; i < 2; i++) {
		gets(w); *w = 0;
		while(true) {
			int len = strlen(gets(w));
			if(!strcmp(w, END_INFO[i])) { *w = 0; break; }
			w[len] = '\n'; w[len+1] = 0; w += len+1; sn += len+1;
		}
		if(i == 0) tjn = sn;
		*(w++) = i+1; *w = 0; sn++;
	}
	memset(a, 0, sizeof(int)*(sn+3));
	for(int i = 0; i < sn; i++) a[i] = text[i];
	suffixBuild(a, sa, sn, 127);
	initHR();
}
int SuffixArray::checkInfr() {
	int gn = 0, *len = new int[sn];
	for(int i = 2, mh = L; i < sn; i++) {
		if(sa[i] < tjn) { mh = hei[i+1]; continue; }
		if(i != 2) mh <?= hei[i];
		if(mh == L) len[i] = 0;
		else len[i] = mh;
	}
	for(int i = sn-1, mh = L; i > 1; i--) {
		if(sa[i] < tjn) { mh = hei[i]; continue; }
		if(i < sn-1) mh <?= hei[i+1];
		if(mh == L && len[i] != 0) seg[gn++].set(sa[i], len[i]);
		else if(mh != L && (mh != 0 || len[i] != 0)) seg[gn++].set(sa[i], max(len[i], mh));
	}
	delete[] len;
	return gn;
}
 
SuffixArray sa;
 
bool cmp1(const Segment&, const Segment&);
bool cmp2(const Segment&, const Segment&);
 
int main()
{
	int k;
 
	for(int t = 1; scanf("%d", &k) != EOF && k != 0; t++) {
		if(t != 1) putchar('\n');
		sa.make();
		int n = sa.checkInfr(), m = n;
		sort(seg, seg+n, cmp1);
		for(int i = n = 1; i < m; i++)
			if(seg[n-1].rightEnd() < seg[i].rightEnd()) seg[n++] = seg[i];
		sort(seg, seg+n, cmp2);
		printf("CASE %d\n", t);
		for(int i = 0; i < min(n, k); i++) {
			printf("INFRINGING SEGMENT %d ", i+1);
			seg[i].print();
		}
	}
	
	return 0;
}
 
bool cmp1(const Segment& s1, const Segment& s2)
{
	if(s1.pos != s2.pos) return s1.pos < s2.pos;
	else return s1.len > s2.len;
}
bool cmp2(const Segment& s1, const Segment& s2)
{
	if(s1.len != s2.len) return s1.len > s2.len;
	else return s1.pos < s2.pos;
}