poj 3693 Maximum repetition substring(後綴數組)

poj 3693 Maximum repetition substring(後綴數組)

題目鏈接：poj 3693 Maximum repetition substring

題目大意：求一個字符串中循環子串次數最多的子串。

解題思路：對字符串構建後綴數組，然後枚舉循環長度，分區間確定。對於一個長度l，每次求出i和i+l的LCP，那麼以i為起點，循環子串長度為l的子串的循環次數為LCP/l+1，然後再考慮一下從i-l+1~i之間有沒有存在增長的可能性。

#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 100005;

struct Suffix_Arr {
    int n, s[maxn];
    int SA[maxn], rank[maxn], height[maxn];
    int tmp_one[maxn], tmp_two[maxn], c[305];

    int d[maxn][20];

    void init(char* str);
    void build(int m);
    void get_height();
    void rmq_init();
    int rmq_query(int x, int y);
    void solve();
}AC;

char str[maxn];

int main () {
    int cas = 0;
    while (scanf("%s", str) == 1 && strcmp(str, "#")) {
        AC.init(str);
        AC.build(27);
        AC.get_height();
        printf("Case %d: ", ++cas);
        AC.solve();
    }
    return 0;
}

void Suffix_Arr::init(char* str) {
    n = 0;
    int len = strlen(str);

    for (int i = 0; i < len; i++)
        s[n++] = str[i] - 'a' + 1;
    s[n++] = 0;
}

void Suffix_Arr::solve() {

    /*
    for (int i = 0; i < n; i++)
        printf("%d ", SA[i]);
    printf("\n");

    for (int i = 0; i < n; i++)
        printf("%d ", height[i]);
    printf("\n");
    */

    rmq_init();

    int ans = 0;
    vector vec;

    for (int l = 1; l < n; l++) {
        for (int i = 0; i + l < n; i += l) {
            int lcp = rmq_query(rank[i], rank[i + l]);
            int k = lcp / l + 1;
            int p = i - (l - lcp % l);

            if (p >= 0 && lcp % l && rmq_query(rank[p], rank[p + l]) >= lcp)
                k++;

            if (k > ans) {
                ans = k;
                vec.clear();
            }

            if (k == ans)
                vec.push_back(l);
        }
    }

    int pos, len;
    for (int i = 0; i < n; i++) {
        bool flag = false;

        for (int j = 0; j < vec.size(); j++) {

            if (SA[i] + vec[j] >= n)
                continue;

            if (rmq_query(i, rank[SA[i] + vec[j]]) >= (ans - 1) * vec[j]) {
                pos = SA[i];
                len = vec[j] * ans;
                flag = true;
                break;
            }
        }

        if (flag)
            break;
    }

    for (int i = 0; i < len; i++)
        printf("%c", s[pos + i] + 'a' - 1);
    printf("\n");
}

void Suffix_Arr::rmq_init() {
    for (int i = 0; i < n; i++) d[i][0] = height[i];

    for (int k = 1; (1< y)
        swap(x, y);
    x++;

    int k = 0;
    while ((1<<(k+1) <= y - x + 1)) k++;
    return min(d[x][k], d[y - (1<= 0; i--) SA[--c[x[i]]] = i;

    for (int k = 1; k <= n; k <<= 1) {

        int mv = 0;
        for (int i = n - k; i < n; i++) y[mv++] = i;
        for (int i = 0; i < n; i++) if (SA[i] >= k)
            y[mv++] = SA[i] - k;

        for (int i = 0; i < m; i++) c[i] = 0;
        for (int i = 0; i < n; i++) c[x[y[i]]]++;
        for (int i = 1; i < m; i++) c[i] += c[i-1];
        for (int i = n - 1; i >= 0; i--) SA[--c[x[y[i]]]] = y[i];

        swap(x, y);
        mv = 1;
        x[SA[0]] = 0;

        for (int i = 1; i < n; i++)
            x[SA[i]] = (y[SA[i-1]] == y[SA[i]] && y[SA[i-1] + k] == y[SA[i] + k] ? mv - 1 : mv++);

        if (mv >= n)
            break;
        m = mv;
    }
}