Front compression

翻译见后

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. Here, every space and newline is also counted as 1 byte. Given the input, each line of which is a substring of a long string, what are sizes of it and corresponding compressed output?

Input

There are multiple test cases. Process to the End of File. The first line of each test case is a long string S made up of lowercase letters, whose length doesn’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

翻译：

题意： 根据图中的方法压缩输入的字符串，压缩后为可匹配的长度空格与剩余的字符串，输出未压缩字符串的长度与压缩后的长度，空格与提行也算。

我们来模拟一个样例： frcode 2 0 6 0 6 则第一个输入串为frcode，第二个也为frcode，原串为 frcode frcode 它的压缩后结果为 0 frcode 6 于是它的原长为14，压缩后为12。

那么我们发现原长十分好算，即每次的长度相加即可，而压缩后的长度就可以有后缀数组来解决(这个题数据水，暴力也能过)。最后注意一下精度就AC~(≧▽≦)/~啦啦啦。

附代码：

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <string> #include <iomanip> #include <ctime> #include <climits> #include <cctype> #include <algorithm> #define clr(x) memset(x,0,sizeof(x)) #define LL long long #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; const int maxn = 100010; int newline,str[maxn]; int n,m,len; LL bf,la; int t[maxn],t2[maxn],c[maxn],height[maxn],sa[maxn],rk[maxn],dp[maxn][20]; char s[maxn]; void build() { int *x = t, *y = t2; m = 27; for(int i = 0; i < m; i++) c[i] = 0; for(int i = 0; i < n; i++) ++c[x[i] = str[i]]; for(int i = 1; i < m; i++) c[i] += c[i-1]; for(int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; for(int k = 1; k <= n; k <<= 1) { int p = 0; for(int i=n-k; i<n; ++i) y[p++]=i; for(int i=0; i<n; ++i) if(k<=sa[i]) y[p++]=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); p = 1; x[sa[0]] = 0; for(int i = 1; i < n; i++) x[sa[i]] = y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? p-1 : p++; if(p >= n) break; m = p; } } void Height() { for(int i = 0; i <= len; i++) rk[sa[i]] = i; for(int i = 0, k = 0; i < len; i++) { if(k) --k; if(rk[i] < 1) continue; int j = sa[rk[i]-1]; while(str[i+k] == str[j+k]) k++; height[rk[i]] = k; } } void ST() { for(int i = 1; i <= len; i++) dp[i][0] = height[i]; for(int j = 1; (1<<j) <= len; j++) for(int i = 1; i+(1<<j)-1 <= len; i++) dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); } int RMQ(int L,int R) { int k = 0; while((1<<(k+1)) <= R-L+1) k++; return min(dp[L][k], dp[R-(1<<k)+1][k]); } int lcp(int a, int l) { if(a == l) return len-a; int u = rk[a], v = rk[l]; if(u > v) return RMQ(v+1, u); else return RMQ(u+1, v); } int cal(int p) { int v = p; for(int i = 1; ; i++) if(!(v/10)) return i; else v /= 10; } int main() { while(scanf("%s",s) != EOF) { len = strlen(s); for(int i = 0; i < len; i++) str[i] = s[i]-'a'+1; str[len] = 0; n = len+1; build(); Height(); ST(); int a,b,l,r; scanf("%d%d%d",&newline,&a,&b); bf = b-a+1; la = b-a+3; newline--; while(newline--) { scanf("%d%d",&l,&r); bf += r-l+1; int p = min(lcp(a, l), min(b-a, r-l)); la += (r-l)-p+2+cal(p); a = l; b = r; } printf(AUTO" "AUTO"\n",bf,la); } return 0; }