poj3693（后缀数组）

poj3693

题意

给出一个串，求重复次数最多的连续重复子串，输出字典序最小的。
分析

论文例8（P21）。

Sparse-Table算法预处理出任意两个后缀串的LCP。
code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

#include<cmath>

using namespace std;

typedef unsigned long long ull;

const int MAXN = 2e5 + 10;

char s[MAXN];

int sa[MAXN], t[MAXN], t2[MAXN], c[MAXN], n; // n　为 字符串长度 + 1，最后一位为数字 0

int rnk[MAXN], height[MAXN];

// 构造字符串 s 的后缀数组。每个字符值必须为 0 ~ m-1

void build_sa(int m) {

    int i, *x = t, *y = t2;

    for(i = 0; i < m; i++) c[i] = 0;

    for(i = 0; i < n; i++) c[x[i] = s[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(int k = 1; k <= n; k <<= 1) {

        int p = 0;

        for(i = n - k; i < n; i++) y[p++] = i;

        for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;

        for(i = 0; i < m; i++) c[i] = 0;

        for(i = 0; i < n; i++) c[x[y[i]]]++;

        for(i = 0; 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]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;

        if(p >= n) break;

        m = p;

    }

}

void getHeight() {

    int i, j, k = 0;

    for(i = 0; i < n; i++) rnk[sa[i]] = i;

    for(i = 0; i < n - 1; i++) {

        if(k) k--;

        j = sa[rnk[i] - 1];

        while(s[i + k] == s[j + k]) k++;

        height[rnk[i]] = k;

    }

}

int dp[MAXN][30];

void init() {

    for(int i = 0; i < n; i++) {

        dp[i][0] = height[i];

    }

    for(int i = 1; (1 << i) < MAXN; i++) {

        for(int j = 0; j < n; j++) {

            dp[j][i] = min(dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);

        }

    }

}

int query(int l, int r) {

    if(l > r) swap(l, r);

    l++;

    int k = (int)(log((double)r - l + 1) / log(2.0));

    return min(dp[l][k], dp[r - (1 << k) + 1][k]);

}

int a[MAXN];

int main() {

    int Case = 1;

    while(~scanf("%s", s) && s[0] != '#') {

        int L = strlen(s);

        n = L + 1;

        build_sa(128);

        getHeight();

        init();

        int mx = 0;

        int cnt = 0;

        // 寻找重复次数最多的连续子串单个子串的长度，可能有多种重复次数相同的子串

        for(int l = 1; l <= L; l++) {

            for(int j = 0; j + l < L; j += l) {

                int k = query(rnk[j], rnk[j + l]); // lcp

                int res = k / l + 1;

                int pos = j - (l - (k % l));

                if(pos >= 0 && k % l && query(rnk[pos], rnk[pos + l])) res++;

                if(res > mx)  {

                    mx = res;

                    cnt = 0;

                    a[cnt++] = l;

                } else if(res == mx) {

                    a[cnt++] = l;

                }

            }

        }

        // 找字典序最小

        int len = 0, st;

        for(int i = 1; i < n && !len; i++) {

            for(int j = 0; j < cnt; j++) {

                if(query(i, rnk[sa[i] + a[j]]) >= (mx - 1) * a[j]) {

                    len = a[j];

                    st = sa[i];

                    break;

                }

            }

        }

        printf("Case %d: ", Case++);

        for(int i = st; i < st + len * mx; i++) {

            printf("%c", s[i]);

        }

        printf("\n");

    }

    return 0;

}
巴特西

poj3693（后缀数组）

poj3693

题意

分析

code

最新文章

热门文章
