【SPOJ 220】Relevant Phrases of Annihilation

http://www.spoj.com/problems/PHRASES/

求出后缀数组然后二分。

因为有多组数据，所以倍增求后缀数组时要特判是否越界。

二分答案时的判断要注意优化！

时间复杂度\(O(TnL\log L)\)，L为字符串总长度。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 100103;

int t1[N << 1], t2[N << 1], c[N];

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

	memset(c, 0, sizeof(int) * (m + 1));

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

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

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

}

void mkhz(int *r, int *sa, int n, int m) {

	int *x = t1, *y = t2, *t, i, j, p;

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

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

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

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

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

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

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

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

	}

}

void mkh(int *r, int *sa, int *h, int *rank, int n) {

	int i, j, k = 0;

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

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

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

}

char s[N];

int r[N], n, id[N], slen, len, sa[N], h[N], rank[N], L[13], R[13], maxl[13], minr[13], used[13];

bool can(int x) {

	int left = 1, ret, right, tl, tr, idnow;

	while (left <= len) {

		for (right = left + 1; h[right] >= x && right <= len; ++right);

		--right;

		if (right - left + 1 < (n << 1)) {left = right + 1; continue;}

		ret = 0;

		for (int i = 1; i <= n; ++i) maxl[i] = L[i] - 1, minr[i] = R[i] + 1, used[i] = 0;

		for (int i = left; i <= right; ++i)

			if ((idnow = id[i]) && !used[idnow]) {

				tl = sa[i]; tr = tl + x - 1;

				if (tr < maxl[idnow] || tl > minr[idnow])

					++ret, used[idnow] = 1;

				else

					maxl[idnow] = max(maxl[idnow], tl), minr[idnow] = min(minr[idnow], tr);

			}

		if (ret == n) return true;

		left = right + 1;

	}

	return false;

}

int main() {

	int T; scanf("%d", &T);

	while (T--) {

		scanf("%d", &n);

		len = 0; int minslen = 0x7ffffff;

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

			scanf("%s", s);

			slen = strlen(s);

			minslen = min(minslen, slen);

			L[i] = len + 1;

			R[i] = len + slen;

			for (int j = 0; j < slen; ++j)

				r[++len] = s[j];

			r[++len] = 200 + i;

		}

		r[len + 1] = -1;

		mkhz(r, sa, len + 1, 300);

		mkh(r, sa, h, rank, len + 1);

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

			for (int j = L[i], top = R[i]; j <= top; ++j)

				id[rank[j]] = i;

			id[rank[R[i] + 1]] = 0;

		}

		int left = 0, mid, right = minslen >> 1;

		while (left < right) {

			mid = (left + right + 1) >> 1;

			if (can(mid)) left = mid;

			else right = mid - 1;

		}

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

	}

	return 0;

}

巴特西

【SPOJ 220】Relevant Phrases of Annihilation

最新文章

热门文章