hdu5782 Cycle(字尾數組+bitset)(16多校賽5)

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 235    Accepted Submission(s): 75

Problem Description Alice get two strings and the lengths are both N. Bored Alice wanna know whether all equal length prefix string of these two strings are CycleEqual. For example, "abc" and "bca" and "cab" are CycleEqual. So you need output N character, '0' is no, '1' is yes.  

Input The input contains multiple test cases.

For each test case, the first contains one string and the second line contains one string. The lengths of strings are both  N(1≤N≤10000) .  

Output For each test case, output N characters. For ith character, if prefix strings of first i character are CycleEqual, output '1', else output '0'.  

Sample Input

abc
cab
aa
aa
        

Sample Output

001
11
        

Author ZSTU  

Source 2016 Multi-University Training Contest 5

題目大意：
        給出兩個字元串a，b，對于ab每一個等長的字首，求解他們是不是互為循環串（首尾相接後通過旋轉可以得到另一個串就是循環串）
解題思路：
        首先考慮循環串有一個性質：a串可以拆成一個字首和一個字尾，交換下位置就得到了B串      

那麼對于每一個i記錄一個len，表示a串i~n和b串0~n的最長公共字首的長度。顯然這b串0~0，0~1,...,0~len-1的這些字首串和a串i~i,....i~i+len-1這些子串是相等的      

是以如果b串的那些字首串之後緊跟着的i個字元所組成的子串和a的0~i-1相等的話，那就組成了一個循環串。用bs[i]（是一個bitset）表示a串0~i和哪些b的k~k+i串相等，如果相等，bs[i][k]=1;      

相等的那些就是所有有可能放在b的那些字首後面形成循環串的方案。通過掩碼和位運算的操作可以快速得到答案。      

然後就是len的求法，字尾數組+rmq即可，不再贅述，bs的求法是通過另一個數組vt[i]表示a串0~n，b串i~n的最長公共字首的長度，實質上就是len的求解翻過來，求法字尾數組+rmq。      

有了vt[i],對vt[i]從大到小排序（下标需要記錄），對于bs，從bs[n-1]倒序的求解,記錄遊标cr=0。如果vt[cr]>=n-1，那麼這個字首一定可以包含bs[n-1]合法的k的位置，記錄到一個bitset裡，cr++，處理出所有bs。      

為什麼要從大到小求bs呢？？因為vt數組字首的長度是遞減的，更長字首之前滿足條件的k，在更短字首也滿足，是以實際上在求的bitset是逐漸增多的，并且是包含的關系。      

有了bs，有了len，那麼答案需要找出bs中滿足條件的k，條件就是i<=k+i-1<=i+len-1，是以掩碼就是除了i~i+len-1位都是1，其他位均為0，用一個pre[i]bitset表示0~i為1其他位0的串，那麼所需的就是pre[i+len-1]^pre[i-1]。      

#include<stdio.h>
#include<string.h>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
const int N = 10000 + 5;
int wa[N << 1], wb[N << 1], wc[N << 1], wv[N << 1];
bool cmp(int *r, int a, int b, int l) {
	return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int *r, int *sa, int n, int m) {
	int *x = wa, *y = wb;
	for (int i = 0; i < m; i++) wc[i] = 0;
	for (int i = 0; i < n; i++) wc[x[i] = r[i]]++;
	for (int i = 1; i < m; i++) wc[i] += wc[i - 1];
	for (int i = n - 1; i >= 0; i--) sa[--wc[x[i]]] = i;
	for (int j = 1, p = 1; p < n; j <<= 1, m = p) {
		p = 0;
		for (int i = n - j; i < n; i++) y[p++] = i;
		for (int i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
		for (int i = 0; i < n; i++) wv[i] = x[y[i]];
		for (int i = 0; i < m; i++) wc[i] = 0;
		for (int i = 0; i < n; i++) wc[wv[i]]++;
		for (int i = 1; i < m; i++) wc[i] += wc[i - 1];
		for (int i = n - 1; i >= 0; i--) sa[--wc[wv[i]]] = y[i];
		int *t = x; x = y; y = t;
		p = 1; x[sa[0]] = 0;
		for (int i = 1; i < n; i++)
			x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
	}
}
void calheight(int *r, int *sa, int *rk, int *height, int n) {
	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	int k = 0;
	for (int i = 0; i < n; height[rk[i++]] = k) {
		if (k) k--;
		for (int j = sa[rk[i] - 1]; r[i + k] == r[j + k]; k++);
	}
}
int Log[N << 1], rq[N << 1][20];

void build_rmq(int *a, int n) {
	for (int i = 1; i <= n; i++)  rq[i][0] = a[i];
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
			rq[i][j] = min(rq[i][j - 1], rq[i + (1 << j - 1)][j - 1]);
	}
	int cr = 0;
	for (int i = 1; i <= n; i++) {
		while ((1 << cr + 1) <= i) cr++;
		Log[i] = cr;
	}
}
int query_rmq(int l, int r) {
	int k = Log[r - l + 1];
	return min(rq[l][k], rq[r - (1 << k) + 1][k]);
}

int a[N << 1], sa[N << 1], rk[N << 1], height[N << 1];

char s1[N], s2[N];
bitset<10000> ans, bs[N], pre[N];
pair<int, int> vt[N];

void solve() {
	int n = strlen(s1);
	int tot = 0;
	for (int i = 0; i < n; i++) a[tot++] = s1[i] - 'a' + 1;
	a[tot++] = 27;
	for (int i = 0; i < n; i++) a[tot++] = s2[i] - 'a' + 1;
	a[tot++] = 0;
	da(a, sa, tot, 28);
	calheight(a, sa, rk, height, tot - 1);
	build_rmq(height, tot - 1);

	for (int i = 0; i < n; i++) {
		int l = rk[n + 1 + i], r = rk[0];
		if (l > r) swap(l, r);
		int len = query_rmq(l + 1, r);
		vt[i] = { -len, i };
	}
	sort(vt, vt + n);
	bitset<10000> tmp;
	int cr = 0;
	for (int i = n - 1; i >= 0; i--) {
		while (cr<n && -vt[cr].first >= i + 1) {
			tmp[vt[cr].second] = 1;
			cr++;
		}
		bs[i] = tmp;
	}
	ans.reset();
	for (int i = 0; i < n; i++) {
		int l = rk[i], r = rk[n + 1];
		if (l > r) swap(l, r);
		int len = query_rmq(l + 1, r);
		if (len > 0) {
			if (i > 0)
				ans |= (pre[i + len - 1] ^ pre[i - 1])&(bs[i - 1] << (i - 1));
			else
				ans |= pre[i + len - 1];
		}
	}
	for (int i = 0; i < n; i++) {
		if (ans.test(i)) printf("1");
		else    printf("0");
	}
	puts("");
}

void init() {
	pre[0][0] = 1;
	for (int i = 1; i <= 10000; i++) {
		pre[i] = pre[i - 1];
		pre[i][i] = 1;
	}
}

int main() {
	init();
	while (scanf("%s%s", s1, s2) == 2) {
		solve();
	}
	return 0;
}