程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDOJ 4691 Front compression ºó׺Êý×é

HDOJ 4691 Front compression ºó׺Êý×é

編輯:C++入門知識

HDOJ 4691 Front compression ºó׺Êý×é



ºó׺Êý×éÇóÁ½×Ó´®¼äµÄ×î´ó¹«¹²Ç°×º.

Front compression

Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 1382 Accepted Submission(s): 517


Problem Description Front compression is a type of delta encoding compression algorithm whereby common prefixes and their lengths are recorded so that they need not be duplicated. For example:
\

The size of the input is 43 bytes, while the size of the compressed output is 40<†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPi4gSGVyZSwgZXZlcnkgc3BhY2UgYW5kIG5ld2xpbmUgaXMgYWxzbyBjb3VudGVkIGFzIDEgYnl0ZS48YnI+CkdpdmVuIHRoZSBpbnB1dCwgZWFjaCBsaW5lIG9mIHdoaWNoIGlzIGEgc3Vic3RyaW5nIG9mIGEgbG9uZyBzdHJpbmcsIHdoYXQgYXJlIHNpemVzIG9mIGl0IGFuZCBjb3JyZXNwb25kaW5nIGNvbXByZXNzZWQgb3V0cHV0PwoKIAo8YnI+CgpJbnB1dAoKVGhlcmUgYXJlIG11bHRpcGxlIHRlc3QgY2FzZXMuIFByb2Nlc3MgdG8gdGhlIEVuZCBvZiBGaWxlLjxicj4KVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgaXMgYSBsb25nIHN0cmluZyBTIG1hZGUgdXAgb2YgbG93ZXJjYXNlIGxldHRlcnMsIHdob3NlIGxlbmd0aCBkb2Vzbg=="t exceed 100,000. The second line contains a integer 1 ¡Ü N ¡Ü 100,000, which is the number of lines in the input. Each of the following N lines contains two integers 0 ¡Ü A < B ¡Ü length(S), indicating that that line of the input is substring [A, B) of S.
Output For each test case, output the sizes of the input and corresponding compressed output.
Sample Input
frcode
2
0 6
0 6
unitedstatesofamerica
3
0 6
0 12
0 21
myxophytamyxopodnabnabbednabbingnabit
6
0 9
9 16
16 19
19 25
25 32
32 37

Sample Output
14 12
42 31
43 40

Author Zejun Wu (watashi)
Source 2013 Multi-University Training Contest 9


#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long int LL;

const int maxn=102100;

int sa[maxn],rank[maxn],rank2[maxn],h[maxn],c[maxn],*x,*y,ans[maxn];
char str[maxn];

bool cmp(int* r,int a,int b,int l,int n)
{
    if(r[a]==r[b]&&a+l=0;i--) sa[--c[x[y[i]]]]=y[i];
}

void get_sa(char c[],int n,int sz=128)
{
    x=rank,y=rank2;
    for(int i=0;i=len) y[yid++]=sa[i]-len;

        radix_sort(n,sz);

        swap(x,y);
        x[sa[0]]=yid=0;

        for(int i=1;i=n) break;
    }
    for(int i=0;ir) swap(l,r);
    ///!!!!!if(l==r) return n-sa[l];
    int a=l+1,b=r;
    int k=Log[b-a+1];
    return min(dp[a][k],dp[b-(1<>a>>b)
    cout<<"lcp: "<


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