重温后缀数组(附6题)

tonyfang posted @ 2016年12月11日 19:20 in 随笔 with tags c++ OI , 239 阅读

初学后缀数组建议去hihocoder看看。

hihocoder 1403, 1407, 1415都是不错的题目。而且题目内附有详细解析。

代码如下:

# include <stdio.h>
# include <algorithm>
# include <string.h>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 50010;

# define rank RANK

int sa[M], tsa[M], rank[M], cntA[M], cntB[M], A[M], B[M], height[M];
int n, k;
int ch[M];

inline void getSA() {
	memset(cntA, 0, sizeof(cntA));
	for (int i=1; i<=n; ++i) cntA[ch[i]]++;
	for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
	for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
	rank[sa[1]] = 1;
	for (int i=2; i<=n; ++i) {
		rank[sa[i]] = rank[sa[i-1]];
		if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
	}
	for (int len = 1; rank[sa[n]] < n; len <<= 1) {
		memset(cntA, 0, sizeof(cntA));
		memset(cntB, 0, sizeof(cntB));
		for (int i=1; i<=n; ++i) {
			cntA[A[i] = rank[i]] ++;
			cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
		}
		for (int i=1; i<=n; ++i) cntB[i] += cntB[i-1];
		for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
		for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
		for (int i=n; i; --i) sa[cntA[A[tsa[i]]] -- ] = tsa[i];
		rank[sa[1]] = 1;
		for (int i=2; i<=n; ++i) {
			rank[sa[i]] = rank[sa[i-1]];
			if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
		}		
	}
	for (int i=1, j=0; i<=n; ++i) {
		if(j) --j;
		while(ch[i+j] == ch[sa[rank[i]-1] + j]) ++j;
		height[rank[i]] = j; 
	}
}

inline bool chk(int x) {
	int cnt = 0;
	for (int i=1; i<=n; ++i) {
		if(height[i] < x) continue; 
		int j = i, cur = 2;
		while(height[j+1] >= x && j+1 <= n)
			++j, ++cur;
		if(cur > cnt) cnt = cur;
		i = j;
	}
	return cnt >= k;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i=1; i<=n; ++i) scanf("%d", &ch[i]);
	getSA();
//	puts(""); 
//	for (int i=1; i<=n; ++i) printf("%d\n", height[i]); 
	int l = 0, r = n, mid, ans = 0;
	while(1) {
		if(r-l <= 3) {
			for (int i=r; i>=l; --i)
				if(chk(i)) {
					ans = i;
					break;
				}
			break;
		}
		mid = l+r >> 1;
		if(chk(mid)) l = mid;
		else r = mid;
	}
	printf("%d\n", ans); 
	return 0;
}
# include <stdio.h>
# include <algorithm>
# include <string.h>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 100010;

# define rank RANK

int sa[M], tsa[M], rank[M], cntA[M], cntB[M], A[M], B[M], height[M];
int n;
int ch[M];

inline void getSA() {
	memset(cntA, 0, sizeof(cntA));
	for (int i=1; i<=n; ++i) cntA[ch[i]]++;
	for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
	for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
	rank[sa[1]] = 1;
	for (int i=2; i<=n; ++i) {
		rank[sa[i]] = rank[sa[i-1]];
		if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
	}
	for (int len = 1; rank[sa[n]] < n; len <<= 1) {
		memset(cntA, 0, sizeof(cntA));
		memset(cntB, 0, sizeof(cntB));
		for (int i=1; i<=n; ++i) {
			cntA[A[i] = rank[i]] ++;
			cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
		}
		for (int i=1; i<=n; ++i) cntB[i] += cntB[i-1];
		for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
		for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
		for (int i=n; i; --i) sa[cntA[A[tsa[i]]] -- ] = tsa[i];
		rank[sa[1]] = 1;
		for (int i=2; i<=n; ++i) {
			rank[sa[i]] = rank[sa[i-1]];
			if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
		}		
	}
	for (int i=1, j=0; i<=n; ++i) {
		if(j) --j;
		while(ch[i+j] == ch[sa[rank[i]-1] + j]) ++j;
		height[rank[i]] = j; 
	}
}

inline bool chk(int x) {
	int maxsa = 0, minsa = n;
	for (int i=1; i<=n; ++i) {
		if(height[i] < x) {
			minsa = sa[i];
			maxsa = sa[i];
		} else {
			minsa = min(minsa, sa[i]);
			maxsa = max(maxsa, sa[i]);
			if(maxsa - minsa >= x) return true;
		}
	}
	return false;
}

int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) scanf("%d", &ch[i]);
	getSA();
//	puts(""); 
//	for (int i=1; i<=n; ++i) printf("%d\n", height[i]); 
	int l = 0, r = n, mid, ans = 0;
	while(1) {
		if(r-l <= 3) {
			for (int i=r; i>=l; --i)
				if(chk(i)) {
					ans = i;
					break;
				}
			break;
		}
		mid = l+r >> 1;
		if(chk(mid)) l = mid;
		else r = mid;
	}
	printf("%d\n", ans); 
	return 0;
}
# include <stdio.h>
# include <algorithm>
# include <string.h>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 200010;

# define rank RANK

int sa[M], tsa[M], rank[M], cntA[M], cntB[M], A[M], B[M], height[M];
int n;
char ch[M]; 

inline void getSA() {
	memset(cntA, 0, sizeof(cntA));
	for (int i=1; i<=n; ++i) cntA[ch[i]]++;
	for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
	for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
	rank[sa[1]] = 1;
	for (int i=2; i<=n; ++i) {
		rank[sa[i]] = rank[sa[i-1]];
		if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
	}
	for (int len = 1; rank[sa[n]] < n; len <<= 1) {
		memset(cntA, 0, sizeof(cntA));
		memset(cntB, 0, sizeof(cntB));
		for (int i=1; i<=n; ++i) {
			cntA[A[i] = rank[i]] ++;
			cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
		}
		for (int i=1; i<=n; ++i) cntB[i] += cntB[i-1];
		for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
		for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
		for (int i=n; i; --i) sa[cntA[A[tsa[i]]] -- ] = tsa[i];
		rank[sa[1]] = 1;
		for (int i=2; i<=n; ++i) {
			rank[sa[i]] = rank[sa[i-1]];
			if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
		}		
	}
	for (int i=1, j=0; i<=n; ++i) {
		if(j) --j;
		while(ch[i+j] == ch[sa[rank[i]-1] + j]) ++j;
		height[rank[i]] = j; 
	}
}

int main() {
	scanf("%s", ch+1);
	int curl = strlen(ch+1);
	ch[++curl] = '$';
	scanf("%s", ch + curl + 1);
	n = strlen(ch+1); 
	getSA();
//	puts(""); 
//	for (int i=1; i<=n; ++i) printf("%d\n", height[i]); 
	int ans = 0;
	for (int i=2; i<=n; ++i) {
		int cur = sa[i], pre = sa[i-1];
		int big, sma; big = max(cur, pre); sma = min(cur, pre);
		if(big > curl && sma <= curl) 
			ans = max(ans, height[i]);
	}
	printf("%d\n", ans); 
	return 0;
}

BZOJ做题:

BZOJ1031

【题解】裸后缀数组。

# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 500010;

# define rank RANK

int sa[M], tsa[M], rank[M], A[M], B[M], cntA[M], cntB[M], n;
char ch[M];
const int N = 256;

inline void getsa() {
	memset(cntA, 0, sizeof(cntA));
	for (int i=1; i<=n; ++i) cntA[ch[i]] ++;
	for (int i=1; i<=N; ++i) cntA[i] += cntA[i-1];
	for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
	rank[sa[1]] = 1;
	for (int i=2; i<=n; ++i) {
		rank[sa[i]] = rank[sa[i-1]];
		if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
	}
	for (int len=1; rank[sa[n]] < n; len <<= 1) {
		memset(cntA, 0, sizeof(cntA));
		memset(cntB, 0, sizeof(cntB));
		for (int i=1; i<=n; ++i) {
			cntA[A[i] = rank[i]] ++;
			cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
		}
		for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1], cntB[i] += cntB[i-1];
		for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
		for (int i=n; i; --i) sa[cntA[A[tsa[i]]] --] = tsa[i];
		rank[sa[1]] = 1;
		for (int i=2; i<=n; ++i) {
			rank[sa[i]] = rank[sa[i-1]];
			if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
		}
	}
}

int main() {
	scanf("%s", ch+1);
	n = strlen(ch+1);
	for (int i=1; i<=n; ++i) ch[i+n] = ch[i];
	n <<= 1;
	getsa();
	for (int i=1; i<=n; ++i) {
		if(sa[i] <= (n>>1))
			printf("%c", ch[sa[i]+(n>>1)-1]);
	}
	return 0;
}

BZOJ4278

后缀数组比较大小+贪心选取。

# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 500010;

# define rank RANK

int sa[M], tsa[M], rank[M], A[M], B[M], cntA[M], cntB[M], n;
int ch[M];
const int N = 1010;

inline void getsa() {
	memset(cntA, 0, sizeof(cntA));
	for (int i=1; i<=n; ++i) cntA[ch[i]] ++;
	for (int i=1; i<=N; ++i) cntA[i] += cntA[i-1];
	for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
	rank[sa[1]] = 1;
	for (int i=2; i<=n; ++i) {
		rank[sa[i]] = rank[sa[i-1]];
		if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
	}
	for (int len=1; rank[sa[n]] < n; len <<= 1) {
		memset(cntA, 0, sizeof(cntA));
		memset(cntB, 0, sizeof(cntB));
		for (int i=1; i<=n; ++i) {
			cntA[A[i] = rank[i]] ++;
			cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
		}
		for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1], cntB[i] += cntB[i-1];
		for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
		for (int i=n; i; --i) sa[cntA[A[tsa[i]]] --] = tsa[i];
		rank[sa[1]] = 1;
		for (int i=2; i<=n; ++i) {
			rank[sa[i]] = rank[sa[i-1]];
			if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
		}
	}
}

int n1, n2;
int a[M], b[M];

int main() {
	n = 0;
	scanf("%d", &n1);
	for (int i=1; i<=n1; ++i) {
		scanf("%d", &a[i]);
		ch[++n] = a[i];
	}
	scanf("%d", &n2);
	ch[++n] = 1001;
	for (int i=1; i<=n2; ++i) {
		scanf("%d", &b[i]);
		ch[++n] = b[i];
	}
	getsa();
	int pa = 1, pb = 1;
	while(pa <= n1 && pb <= n2) {
		int sA = rank[pa], sB = rank[n1 + pb + 1];
		if(sA < sB) {
			printf("%d ", a[pa]);
			++pa;
		} else {
			printf("%d ", b[pb]);
			++pb;
		}
	}
	while(pa <= n1) {
		printf("%d ", a[pa]);
		++pa;
	}
	while(pb <= n2) {
		printf("%d ", b[pb]);
		++pb;
	}
	
	return 0;
}

BZOJ3172

后缀数组求完后乱搞即可(暴力) 实际上正解应该是AC自动机。

# include <stdio.h>
# include <algorithm>
# include <string.h>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 1600010;

# define rank RANK

int n, sa[M], tsa[M], cntA[M], cntB[M], rank[M], A[M], B[M];
char ch[M];
int height[M];

const int N = 256;

int t, beg[M], lens[M]; 

inline void getsa() {
	memset(cntA, 0, sizeof(cntA));
	for (int i=1; i<=n; ++i) cntA[ch[i]] ++;
	for (int i=1; i<=N; ++i) cntA[i] += cntA[i-1];
	for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
	rank[sa[1]] = 1;
	for (int i=2; i<=n; ++i) {
		rank[sa[i]] = rank[sa[i-1]];
		if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
	}
	for (int len=1; rank[sa[n]] < n; len <<= 1) {
		memset(cntA, 0, sizeof(cntA));
		memset(cntB, 0, sizeof(cntB));
		for (int i=1; i<=n; ++i) {
			cntA[A[i] = rank[i]] ++;
			cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
		}
		for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1], cntB[i] += cntB[i-1];
		for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
		for (int i=n; i; --i) sa[cntA[A[tsa[i]]] --] = tsa[i];
		rank[sa[1]] = 1;
		for (int i=2; i<=n; ++i) {
			rank[sa[i]] = rank[sa[i-1]];
			if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
		}
	}
	for (int i=1, j=0; i<=n; ++i) {
		if(j) j--;
		while(ch[i+j] == ch[sa[rank[i]-1] + j]) ++j;
		height[rank[i]] = j;
	}
}

int main() {
	scanf("%d", &t);
	int cur = 1;
	for (int i=1; i<=t; ++i) {
		beg[i] = cur;
		scanf("%s", ch+cur);
		cur = strlen(ch+1);
		lens[i] = cur - beg[i] + 1;
		ch[++cur] = '$';
		++cur;
	}
	--cur;
	n = cur;
	getsa();
	for (int i=1; i<=t; ++i) {
		int cur = rank[beg[i]];
		int l, r;
		l=r=cur;
		while(height[l] >= lens[i] && l>0) --l;
		while(height[r+1] >= lens[i] && r<n) ++r;
		printf("%d\n", r-l+1);
	}
	return 0;
}

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter