hdu 3518 Boring counting 后缀数组基础题

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int x = 123;
const int maxn = 1010;
int t1[maxn], t2[maxn], c[maxn];
bool cmp(int *r, int a, int b, int l) {
    return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(char str[], int sa[], int Rank[], int heigh[], int n, int m)
{
    n++;
    int i, j, p, *x = t1, *y = t2;
    for(i = 0; i < m; ++i) c[i] = 0;
    for(i = 0; i < n; ++i) c[ x[i] = str[i] ]++;
    for(int i = 1; i < m; ++i) c[i] += c[i - 1];
    for(int i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;

    for(int j = 1; j <= n; j <<= 1)
    {
        p = 0;
        for(i = n - j; i < n; ++i) y[p++] = i;
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[p++] = sa[i] - j;

        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];
        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) Rank[ sa[i] ] = i;
    for(i = 0; i < n; ++i) {
        if(k) k--;
        j = sa[Rank[i] - 1];
        while(str[i + k] == str[j + k]) k++;
        heigh[ Rank[i] ] = k;
    }
}

int Rank[maxn], heigh[maxn], sa[maxn];
char s[maxn];
void out(int n) {
    ///Rank数组的有效范围是0~n-1， 值是1~n
    for(int i = 0; i <= n; ++i) printf("%d ", Rank[i]);
    puts("");
    ///sa数组的有效范围是1~n，值是0~n-1
    for(int i = 0; i <= n; ++i) printf("%d ", sa[i]);
    puts("");
    ///heigh数组的有效范围是2~n
    for(int i = 0; i <= n; ++i) printf("%d ", heigh[i]);
}
int calc(int k, int n) {
    int mi = INF, mx = -INF, res = 0;
    for(int i = 2; i <= n; ++i) {
        if(heigh[i] >= k) {
            mi = min(mi, min(sa[i - 1], sa[i]));
            mx = max(mx, max(sa[i - 1], sa[i]));
        }else {
            if(mx - mi >= k) res++;
            mx = -INF, mi = INF;
        }
    }
    if(mi != INF && mx - mi >= k) res++;
    return res;
}
int main()
{
   // freopen("in.txt", "r", stdin);
    //freopen("out2.txt", "w", stdout);
    while(scanf("%s", s)) {
        if(strcmp(s, "#") == 0) break;
        int n = strlen(s);
        da(s, sa, Rank, heigh, n, 130);
       // out(n);
        int ans = 0;
        for(int i = 1; i <= (n >> 1); ++i) ans += calc(i, n);
        printf("%d\n", ans);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int x = 123;
const int maxn = 1010;
ull H[maxn], xp[maxn];
map<ull, pair<int, int> > m;
int len;
char s[maxn];
void init() {
    xp[0] = 1;
    for(int i = 1; i <= 1005; ++i) xp[i] = xp[i - 1] * x;
}
int main() {
   // freopen("in.txt", "r", stdin);
   // freopen("out1.txt", "w", stdout);
    init();
    while(scanf("%s", s)) {
        if(strcmp(s, "#") == 0) break;
        len = strlen(s);
        H[len] = 0;
        for(int i = len - 1; i >= 0; --i) H[i] = H[i + 1] * x + (s[i]);
        m.clear();
        long long ans = 0;
        for(int k = 1; k <= len / 2; ++k) {
            for(int i = 0; i <= len - k; i++) {
                ull hash = H[i] - H[i + k] * xp[k];
                int lp = m[hash].first;
                int is = m[hash].second;
                if(is == 1 && i >= lp + k) {
                    m[hash].second = -1;
                    ans++;
                }else if(is == -1) {
                    continue;
                }else if(is == 0) {
                    m[hash].first = i;
                    m[hash].second = 1;
                }
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}