后缀数组简单总结(二)
se print(r, t, n); printf("\n"); } int main() { int t,i; int l, n, m; int ncase = 1; while (cin >> t && t) { n = 0; m = 256; CLR(idx, 0);///!!! FE(i, 1, t) { RS(r); l = strlen(r); REP(j, l) { a[n] = (int)r[j]; idx[n++] = i; } a[n++] = m++; } a[--n] = 0; build_sa(a,sa,n+1,m); getHeight(a,sa,n); solve(t, n); } return 0; } /** 11、出现或反转后出现所有字符串中的最长子串 Pku1226--Substrings 题目大意：给出n个串，求一个最长的串x，它或者它的反串出现在所有的串中。 */ int wa[MAXN], wb[MAXN], wv[MAXN], wn[MAXN]; char r[MAXN]; int a[MAXN], sa[MAXN], rank[MAXN], height[MAXN]; int idx[MAXN]; int getid(int x) { return idx[sa[x]]; } bool check(int l, int t, int n) { int vis[110], step, tol; CLR(vis, 0); step = 1; int x = getid(1); vis[x] = step; tol = 1; FE(i, 2, n) { if (height[i] < l) { CLR(vis, 0); ++step; x = getid(i); vis[x] = step; tol = 1; } else { x = getid(i); if (vis[x] != step) { vis[x] = step; ++tol; } if (tol >= t) return 1; } } return 0; } void solve(int t, int n) { int l = 0, r = 100; while (l <= r) { int mid = (l + r) >> 1; if (check(mid, t, n)) l = mid + 1; else r = mid - 1; } cout << r << endl; } int main() { int T; cin >> T; int t, n, m; while (T--) { RI(t); CLR(idx, 0); n = 0; m = 256; FE(i, 1, t)///1 { RS(r); int l = strlen(r); REP(j, l) { a[n] = (int)r[j]; idx[n++] = i; } a[n++] = m++; for (int j = l - 1; j >= 0; j--) { a[n] = (int)r[j]; idx[n++] = i; } a[n++] = m++; } a[--n] = 0; --m; if (t == 1) { cout << strlen(r) << endl; continue; } build_sa(a, sa, n + 1, m); get_height(a, sa, n); solve(t, n); } return 0; } /** 12、不重叠地至少两次出现在所有字符串中的最长子串 spoj220 题目大意：给出n个字符串，求一个最长的串x，x在每个字符串中不重叠出现至少两次。 */ int wa[MAXN], wb[MAXN], wv[MAXN], wn[MAXN]; char r[MAXN]; int a[MAXN], sa[MAXN], rank[MAXN], height[MAXN]; int idx[MAXN]; int ns; int n, m; int lmax; int used[12]; int smin[12], smax[12]; int getid(int x) { return idx[sa[x]]; } void clear_up() { REP(i, 12) smin[i] = MAXN; REP(i, 12) smax[i] = -1; } bool check(int L) { clear_up(); smin[getid(1)] = sa[1]; smax[getid(1)] = sa[1]; FE(i, 2, n) { int x = getid(i); int y = sa[i]; if (height[i] < L) { int tol = 0; REP(i, ns) if (smax[i] - smin[i] >= L) tol++; if (tol == ns) return 1; clear_up(); smin[x] = smax[x] = y; } else { smin[x] = min(smin[x], y); smax[x] = max(smax[x], y); } } if (height[n] >= L) { int tol = 0; REP(i, ns) if (smax[i] - smin[i] >= L) tol++; if (tol == ns) return 1; } return 0; } void solve() { int l = 0; int r = lmax; while (l <= r) { int m = (l + r) >> 1; if (check(m)) l = m + 1; else r = m - 1; } WI(r); } int main() { int T; RI(T); while (T--) { RI(ns); CLR(idx, 0); m = 256; n = 0; lmax = -1; REP(i, ns) { RS(r); int l = strlen(r); if (lmax == -1 || lmax > l) lmax = l; REP(j, l) { a[n] = r[j]; idx[n++] = i; } a[n++] = m++; // idx[n++] = 0; } a[--n] = 0; build_sa(a, sa, n + 1, m); getHeight(a, sa, n); solve(); } return 0; } /** 13.两个字符串的重复子串个数。 Pku3415--Common Substrings 题目大意：给出两个字符串，求在这两个字符串中出现次数不少于k的公共子串的个数（可以重复）。 例如xx和xx这两个字符串，假如k=1，则有5个。（4个位置不同的“x”，和一个“xx”）。 */ int wa[MAXN], wb[MAXN], wv[MAXN], wn[MAXN]; char r[MAXN]; int a[MAXN], sa[MAXN], rank[MAXN], height[MAXN]; int idx[MAXN]; int h[MAXN][30]; int n1, n2, n, m, k; int getid(int x) { return idx[sa[x]]; } stack
> S; LL getnum(int l, int r, int op) { LL ret = 0; LL now = 0; while (!S.empty()) S.pop(); FE(i, l, r - 1) { int c = getid(i); if (c == op) ret += now; else now += height[i + 1] - k + 1; int xn = (c == op 0 : 1); int xs = 0; while (!S.empty() && S.top().first >= height[i + 1]) { xn += S.top().second; now -= 1LL * S.top().second * (S.top().first - height[i + 1]); S.pop(); } if (xn) S.push(make_pair(height[i + 1], xn)); } if (getid(r) == op) ret += now; return ret; } void solve() { LL ans = 0; LL last = 1; FE(i, 2, n) { if (height[i] < k) { ans += getnum(last, i - 1, 1) + getnum(last, i - 1, 2); last = i; } } if (height[n] >
= k) ans += getnum(last, n, 1) + getnum(last, n, 2); cout << ans << endl; } int main() { int x; while (cin >> k && k) { CLR(idx, 0); n = 0; m = 256; RS(r); n1 = strlen(r); REP(i, n1) { a[n] = r[i]; idx[n++] = 1; } a[n++] = m++; RS(r); n2 = strlen(r); REP(i, n2) { a[n] = r[i]; idx[n++] = 2; } a[n] = 0; build_sa(a, sa, n + 1, m); getHeight(a, sa, n); solve(); } return 0; }
一些其他题目： /*** 输出n个串中，每个串不属于于其它串的最小子串 URAL 1713 Key Substrings 后缀数组 */ const int MAXN = 1010 * 100; int wa[MAXN], wb[MAXN], wv[MAXN], wn[MAXN]; char r[MAXN]; int a[MAXN], sa[MAXN], rank[MAXN], height[MAXN]; int idx[MAXN]; inline int getid(int x) { return idx[sa[x]]; } int n, m; int ll[MAXN], rr[MAXN];///left记录sa中i位置的左边第一个不是同一串的后缀之间的lcp，rr同理。没有则值为0 void pre() { CLR(ll, 0); CLR(rr, 0); for (int i = 2; i <= n; i++) { if (getid(i) != getid(i - 1)) ll[i] = height[i]; else ll[i] = min(ll[i - 1], height[i]); } for (int i = n - 1; i >= 1; i--) { if (getid(i) != getid(i + 1)) rr[i] = height[i + 1]; else rr[i] = min(rr[i + 1], height[i + 1]); } } void solve() { pre(); int p[2]; p[0] = INF; p[1] = 0; for (int i = 0; i <= n; i++) { if (idx[i]) { int x = max(ll[rank[i]], rr[rank[i]]); x++; if (idx[i + x - 1] == idx[i] && p[0] > x) p[0] = x, p[1] = i;///判断是否超过长度 } else { for (int j = p[1]; j < p[1] + p[0]; j++) printf("%c", (char)a[j]); printf("\n"); p[0] = INF; p[1] = 0; } } } int main() { int t, i, l; while (~scanf("%d", &t)) { n = 0; m = 256; CLR(idx, 0); for(int i = 1; i <= t; i++) { scanf("%s", r); l = strlen(r); REP(j, l) { a[n] = (int)r[j]; idx[n++] = i; } a[n++] = m++; } a[--n] = 0; build_sa(a, sa, n + 1, m); getHeight(a, sa, n); solve1(); } return 0; } /*** 题目：给出一个A串，给出若干个B串，问A串中有多少个不同的子串不是B中的子串 hdu4416Good Article Good sentence 将所有的串拼接在一起，中间用一个不同的字符分隔开。然后求一次后缀数组以及height数组。 然后对于A中的某一个后缀，统计一下有B中的LCA有多少，就OK了，说明有A的这个后缀有LCA个子串在B中出现过。 只需要从前往后以及从后往前统计一次height就OK了。注意我们这里统计的是A与B的LCA。如果连续的两个sa是A中，那我们需要求一次最小值，保证求的是和B串的LCA。 但是题目要求的是A中的不同的子串，所以还要去重，遍历一次，如果连续两个都是A串的，则更新一下 */ int wa[MAXN], wb[MAXN], wv[MAXN], wn[MAXN]; char r[MAXN]; int a[MAXN], sa[MAXN], rank[MAXN], height[MAXN]; int ncase; int n, m; int L; int pos[MAXN]; void init() { CLR(pos, 0); ///从前向后 int tmp = INF; for (int i = 1; i <= n; i++) if (sa[i] < L) { tmp = min(tmp, height[i]); pos[sa[i]] = max(pos[sa[i]], tmp); } else tmp = INF; ///从后向前 tmp = INF; for (int i = n; i >= 1; i--) if (sa[i - 1] < L) { tmp = min(tmp, height[i]); pos[sa[i - 1]] = max(pos[sa[i - 1]], tmp); } else tmp = INF; } void solve() { init(); for(int i=1;i<=n;i++) if(sa[i]
0) ans += 1L