題意：一個字符串，查詢恰好出現k次的子串的數目

思路：后綴數組在height上進行操作。我們直接枚舉長度為k的區間求min值，但是要注意的是直接這么算是會重復的，同時也可能超過k次，這樣我們就需要把枚舉的前一個和后一個都判斷一下，這樣保證了等于k次，同時也保證了沒有重復統計。

代碼：

#include<bits/stdc++.h> using namespace std; #define X first #define Y second #define PB push_back #define MP make_pair #define MEM(a,b) memset(a,b,sizeof(a)) using namespace std;const int MAXN = 5e5+100; int t1[MAXN], t2[MAXN], c[MAXN],n; bool cmp(int *r, int a, int b, int l) {return r[a] == r[b] && r[a + l] == r[b + l]; } void da(int str[], int sa[], int zrank[], int height[], int n, int m){n++;int i, j, p, *x = t1, *y = t2;//第一輪基數排序，如果s的最大值很大，可改為快速排序for (i = 0; i < m; i++)c[i] = 0;for (i = 0; i < n; i++)c[x[i] = str[i]]++;for (i = 1; i < m; i++)c[i] += c[i - 1];for (i = n - 1; i >= 0; i--)sa[--c[x[i]]] = i;for (j = 1; j <= n; j <<= 1){p = 0;//直接利用sa數組排序第二關鍵字for (i = n - j; i < n; i++)y[p++] = i;//后面的j個數第二關鍵字為空的最小for (i = 0; i < n; i++)if (sa[i] >= j)y[p++] = sa[i] - j;//這樣數組y保存的就是按照第二關鍵字排序的結果//基數排序第一關鍵字for (i = 0; i < m; i++)c[i] = 0;for (i = 0; i < n; i++)c[x[y[i]]]++;for (i = 1; i < m; i++)c[i] += c[i - 1];for (i = n - 1; i >= 0; i--)sa[--c[x[y[i]]]] = y[i];//根據sa和x數組計算新的x數組swap(x, y);p = 1; x[sa[0]] = 0;for (i = 1; i < n; i++)x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;if (p >= n)break;m = p;//下次基數排序的最大值}int k = 0;n--;for (i = 0; i <= n; i++)zrank[sa[i]] = i;for (i = 0; i < n; i++){if (k)k--;j = sa[zrank[i] - 1];while (str[i + k] == str[j + k])k++;height[zrank[i]] = k;} } int m_rank[MAXN], height[MAXN]; int RMQ[MAXN]; int mm[MAXN]; int best[30][MAXN]; void initRMQ(int n){mm[0] = -1;for (int i = 1; i <= n; i++)mm[i] = ((i&(i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];for (int i = 1; i <= n; i++)best[0][i] = i;for (int i = 1; i <= mm[n]; i++)for (int j = 1; j + (1 << i) - 1 <= n; j++){int a = best[i - 1][j];int b = best[i - 1][j + (1 << (i - 1))];if (RMQ[a]<RMQ[b])best[i][j] = a;else best[i][j] = b;} } int askRMQ(int a, int b){int t;t = mm[b - a + 1];b -= (1 << t) - 1;a = best[t][a]; b = best[t][b];return RMQ[a]<RMQ[b] ? a : b; } char str[MAXN]; int r[MAXN]; int sa[MAXN]; int Q[MAXN];int lcp(int a, int b){//a = m_rank[a]; b = m_rank[b];if(a==b) return n-sa[a];if (a>b)swap(a, b);return height[askRMQ(a + 1, b)]; }int main() {int t, k;scanf("%d", &t);while (t--) {scanf("%d", &k);scanf("%s", str);n = strlen(str);for (int i = 0; i < n; i++)r[i] = str[i];r[n] = 0;da(r, sa, m_rank, height, n, 256);long long ans = 0;for (int i = 1; i <= n; i++) {RMQ[i] = height[i];}initRMQ(n);memset(Q, 0, sizeof(Q));for (int i = 0; i+k<=n; i++) {Q[i+1] = lcp(i+k,i);}int ret;ans=0;for (int i = 0; i+k-1 <=n; i++) {ret=lcp(i+k-1,i);ans = ans+(long long)max(0,ret-max(Q[i], Q[i+1]));}printf("%lld\n", ans);}return 0; }

轉載于:https://www.cnblogs.com/zhangxianlong/p/10672485.html

總結

以上是生活随笔為你收集整理的hdu 6194 后缀数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。