程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU - 4552 怪盜基德的挑戰書 (後綴數組)

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

編輯:C++入門知識

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;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved