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.2cto.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;i r) 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: "<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：BZOJ 1455 罗马游戏左偏树	下一篇：HDOJ 4690 EBCDIC 模拟