后缀数组训练

求允许重叠的至少出现k次的子串的最大长度

二分答案，将高度数组分组，若某一组有k个数（或以上）满足高度大于k，则可行

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 2e4 + 10;
 8 
 9 int n, t, k;
10 int S[maxn];
11 int rnk[maxn];
12 int tmp[maxn];
13 int sa[maxn];
14 int lcp[maxn];
15 
16 bool compare_sa(int i, int j) {
17     if (rnk[i] != rnk[j]) {
18         return rnk[i] < rnk[j];
19     } else {
20         int ri = i + k <= n ? rnk[i + k] : -1;
21         int rj = j + k <= n ? rnk[j + k] : -1;
22         return ri < rj;
23     }
24 }
25 
26 void construct_sa(int* S, int *sa) {
27     for (int i = 0; i <= n; i++) {
28         sa[i] = i;
29         rnk[i] = i < n ? S[i] : -1;
30     }
31     for (k = 1; k <= n; k *= 2) {
32         sort(sa, sa + n + 1, compare_sa);
33         tmp[sa[0]] = 0;
34         for (int i = 1; i <= n; i++) {
35             tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
36         }
37         for (int i = 0; i <= n; i++) {
38             rnk[i] = tmp[i];
39         }
40     }
41 }
42 
43 void construct_lcp(int *S, int *sa, int *lcp) {
44     for (int i = 0; i <= n; i++) rnk[sa[i]] = i;
45     int h = 0;
46     lcp[0] = 0;
47     for (int i = 0; i < n; i++) {
48         int j = sa[rnk[i] - 1];
49         if (h > 0) h--;
50         for (; j + h < n && i + h < n; h++) {
51             if (S[i + h] != S[j + h]) break;
52         }
53         lcp[rnk[i] - 1] = h;
54     }
55 }
56 
57 bool ck(int m) {
58     int cnt = 1;
59     for (int i = 1; i < n; i++) {
60         if (lcp[i] >= m) {
61             cnt++;
62         } else {
63             cnt = 1;
64         }
65         if (cnt >= t) {
66             return true;
67         }
68     }
69     return false;
70 }
71 
72 int main() {
73     scanf("%d%d", &n, &t);
74     for (int i = 0; i < n; i++) {
75         scanf("%d", &S[i]);
76     }
77     construct_sa(S, sa);
78     construct_lcp(S, sa, lcp);
79     int dn = 1, up = n + 1;
80     while (up - dn > 1) {
81         int mid = (dn + up) / 2;
82         if (ck(mid)) {
83             dn = mid;
84         } else {
85             up = mid;
86         }
87     }
88     printf("%d
", dn);
89     return 0;
90 }

View Code

SPOJ694

求一个串的所有不同子串数目

总的子串数目减去重复数（利用高度数组读得）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int T;
int k;
int n;
const int maxn = 1e3 + 10;
int rnk[maxn], sa[maxn], tmp[maxn], lcp[maxn];

string S;

bool compare_sa(int i, int j) {
    if (rnk[i] != rnk[j]) {
        return rnk[i] < rnk[j];
    } else {
        int ri = i + k <= n ? rnk[i + k] : -1;
        int rj = j + k <= n ? rnk[j + k] : -1;
        return ri < rj;
    }
}

void construct_sa(string S, int *sa) {
    n = S.length();
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        rnk[i] = i < n ? S[i] : -1;
    }

    for (k = 1; k <= n; k *= 2) {
        sort(sa, sa + n + 1, compare_sa);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++) {
            rnk[i] = tmp[i];
        }
    }
}


void construct_lcp(string S, int* sa, int* lcp) {
    for (int i = 0; i <= n; i++) rnk[sa[i]] = i;

    int h = 0;
    lcp[0] = 0;
    for (int i = 0; i < n; i++) {
        int j = sa[rnk[i] - 1];
        if (h > 0) h--;
        for (; i + h < n && j + h < n; h++) {
            if (S[i + h] != S[j + h]) break;
        }
        lcp[rnk[i] - 1] = h;
    }
}

int main() {
    cin >> T;
    while (T--) {
        cin >> S;
        construct_sa(S, sa);
        construct_lcp(S, sa, lcp);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += n - sa[i] - lcp[i - 1];//i-1
        }
        printf("%d
", ans);
    }


    return 0;
}

View Code

HDU - 4552

求一个字符串的所有前缀在字符串中出现次数的总合

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;

int n, k;
int tmp[maxn], rnk[maxn], sa[maxn], lcp[maxn];
char S[maxn];

bool compare_sa(int i, int j) {
    if (rnk[i] != rnk[j]) {
        return rnk[i] < rnk[j];
    } else {
        int ri = i + k <= n ? rnk[i + k] : -1;
        int rj = j + k <= n ? rnk[j + k] : -1;
        return ri < rj;
    }
}

void construct_sa(int *sa) {
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        rnk[i] = i < n ? S[i] : -1;
    }
    for (k = 1; k <= n; k *= 2) {
        sort(sa, sa + n + 1, compare_sa);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++) {
            rnk[i] = tmp[i];
        }
    }
}

void construct_lcp(int* sa, int* lcp) {
    for (int i = 0; i <= n; i++) rnk[sa[i]] = i;
    int h = 0;
    for (int i = 0; i <= n; i++) {
        int j = sa[rnk[i] - 1];
        if (h > 0) h--;
        for (; j + h < n && i + h < n; h++) {
            if (S[i + h] != S[j + h]) break;
        }
        lcp[rnk[i] - 1] = h;
    }
}

int main() {
    while (~scanf("%s", S)) {
        n = strlen(S);
        construct_sa(sa);
        construct_lcp(sa, lcp);
        LL ans = n;
        int t = rnk[0];
        int match = n;
        while (t < n) {
            match = min(match, lcp[t]);
            ans += match;
            t++;
        }
        t = rnk[0];
        match = n;
        while (t) {
            match = min(match, lcp[t - 1]);
            ans += match;
            t--;
        }
        printf("%lld
", ans % 256);
    }

    return 0;
}

跑得很慢找机会再写