HDU - 4552 怪盜基德的挑戰書 (後綴數組)

HDU - 4552 怪盜基德的挑戰書 (後綴數組)

Description

　　“在樹最美麗的那天，當時間老人再次把大鐘平均分開時，我會降臨在燈火之城的金字塔前，帶走那最珍貴的笑容。”這是怪盜基德盜取巴黎盧浮宮的《蒙娜麗莎的微笑》這幅畫時，挑戰書上的內容。
　　但這次，怪盜基德的挑戰書上出現了一串串小寫字母“aaab sdfeeddd...”。柯南以小學生的眼睛，超凡高中生的頭腦，快速統計各種字母頻率，字符串長度，並結合挑戰書出現的時間等信息，試圖分析怪盜基德的意圖。最後，他將線索鎖定在字符串的循環次數上。並且進一步推理發現，從字符串的第一位開始，到第i位，形成該字符串的子串(c1, c2, c3 ... ci )。對於某一子串ci在該字符串中出現的次數記為ki，則全部子串的循環次數總和AIM = k1 + k2 + ... + ki + ... + kn，柯南發現，AIM恰好對應一個ASCII碼！所以，只要把挑戰書上的字符串轉變成數字，再找到對應的ASCII碼，就可以破解這份挑戰書了！
　　現在，你的任務就是把字符串轉變成對應數字，因為ASCII碼以及擴展ASCII碼全部只有256個，所以，本題只要把結果對256取余即可。

Input

輸入有多組測試數據；
每組測試數據只有一個字符串，由各種小寫字母組成，中間無空格。
字符串的長度為L(0 < L <= 100000)。

Output

請計算並輸出字符串的AIM值，每組數據輸出一行。

Sample Input

 aaa
abab 

Sample Output

 6
6 

題意：求前綴在串出現的次數。
思路：利用後綴數組求，求每個後綴與原串的匹配長度，因為和原串匹配，所以和原串的最長公共前綴都可以表示為前綴。

#include 
#include 
#include 
#include 
#include 
#include 
typedef long long ll;
using namespace std;
const int maxn = 100010;

int sa[maxn]; 
int t1[maxn], t2[maxn], c[maxn];
int rank[maxn], height[maxn];

void build_sa(int s[], int n, int m) {
    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] = 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 (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]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+j] == y[sa[i]+j] ? p-1 : p++;

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

void getHeight(int s[],int n) {
    int i, j, k = 0;
    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 (s[i+k] == s[j+k]) k++;
        height[rank[i]] = k;
    }
}

char str[maxn];
int r[maxn];

int main() {
    while (scanf("%s", str) != EOF) {
        int n = strlen(str);
        for (int i = 0; i <= n; i++)
            r[i] = str[i];

        build_sa(r, n+1, 128);
        getHeight(r, n);

        int ans = n;
        int mid = rank[0];
        int tmp = n;
        while (mid < n) {
            tmp = min(tmp, height[mid+1]);
            mid++;
            ans += tmp;
        }
        mid = rank[0];
        tmp = n;
        while (mid > 1) {
            tmp = min(tmp, height[mid]);
            mid--;
            ans += tmp;
        }

        printf("%d\n", ans % 256);
    }
    return 0;
}