后缀数组求两子串间的最大公共前缀.

Front compression

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?

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

14 12
42 31
43 40

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

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<n&&b+l<n&&r[a+l]==r[b+l]) return true;
    return false;
}

void radix_sort(int n,int sz)
{
    for(int i=0;i<sz;i++) c[i]=0;
    for(int i=0;i<n;i++) c[x[y[i]]]++;
    for(int i=1;i<sz;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=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<n;i++) x[i]=c[i],y[i]=i;
    radix_sort(n,sz);
    for(int len=1;len<n;len<<=1)
    {
        int yid=0;
        for(int i=n-len;i<n;i++) y[yid++]=i;
        for(int i=0;i<n;i++)
            if(sa[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;i++)
        {
            x[sa[i]]=cmp(y,sa[i],sa[i-1],len,n)?yid:++yid;
        }

        sz=yid+1;
        if(sz>=n) break;
    }
    for(int i=0;i<n;i++)
        rank[i]=x[i];
}

void get_h(char str[],int n)
{
    int k=0; h[0]=0x3f3f3f3f;
    for(int i=0;i<n;i++)
    {
        if(rank[i]==0) continue;
        k=max(k-1,0);
        int j=sa[rank[i]-1];
        while(i+k<n&&j+k<n&&str[i+k]==str[j+k]) k++;
        h[rank[i]]=k;
    }
}

int dp[maxn][20],Log[maxn];

void RMQ_init(int n)
{
    for(int i=0;i<n;i++) dp[i][0]=h[i];
    for(int i=1;i<=Log[n];i++)
    {
        for(int j=0;j+(1<<i)-1<n;j++)
        {
            dp[j][i]=min(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
        }
    }
}

int lcp(int l,int r)
{
    l=rank[l];r=rank[r];
    if(l>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<<k)+1][k]);
}

void init_Log()
{
    Log[0]=-1;
    for(int i=1;i<maxn;i++)
    {
        Log[i]=(i&(i-1))?Log[i-1]:Log[i-1]+1;
    }
}

void debug(int n)
{
    for(int i=0;i<n;i++)
    {
        cout<<sa[i]<<",";
    }
    cout<<endl;
    for(int j=0;j<n;j++)
    {
        cout<<h[j]<<",";
    }
    cout<<endl;
    for(int j=0;j<n;j++)
    {
        cout<<rank[j]<<",";
    }
    cout<<endl;
    int a,b;
    while(cin>>a>>b)
    cout<<"lcp: "<<lcp(a,b)<<endl;
}

int getwei(int x)
{
    if(x==0) return 1;
    int ret=0;
    while(x)
    {
        x/=10;
        ret++;
    }
    return ret;
}

int main()
{
    init_Log();
    while(scanf("%s",&str)!=EOF)
    {
        int n=strlen(str);
        get_sa(str,n);
        get_h(str,n);
        RMQ_init(n);

        //debug(n);

        int m;
        LL ans1=0,ans2=0;

        scanf("%d",&m);
        bool first=true;
        int lastL,lastR;
        while(m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            ans1+=r-l+1LL;
            if(first==true)
            {
                ans2+=r-l+3;
                first=false;
            }
            else
            {
                if(lastL==l)
                {
                    int minR=min(lastR-1,r-1);
                    int com=minR-l+1;///公共长度
                    int diff=r-l+1-com;///不同的长度
                    int wei=getwei(com);

                    ans2+=diff+wei+1LL;
                    if(diff==0) ans2+=1LL;
                }
                else
                {
                    int com=lcp(lastL,l);///LCP
                    com=min(com,min(lastR-lastL,r-l));///公共长度
                    int diff=r-l+1-com;
                    int wei=getwei(com);
                    ans2+=diff+wei+1LL;
                    if(diff==0) ans2+=1LL;
                }
            }
            lastL=l; lastR=r;
        }
        cout<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}

HDOJ 4691 Front compression 后缀数组