某岛

… : "…アッカリ~ン . .. . " .. .
October 24, 2013

BZOJ 3230. 相似子串

Brief description:

设两个字符串的最长公共前缀和后缀的长度分别为 $$a$$, $$b$$。
则它们相似程度,定义为 $$a^2 + b^2$$。
给定一个字符串,每次询问其字典序第 k1-th 大和第 k2-th 大的两个子串间的相似程度。

Analysis:

求一个字符串的字典序第 k-th 大子串可以用 SA 做到每次询问log(n)
方法是,在搞出高度函数的时候,顺便开一个数组记录到 SA 中的的某个为止,共会出现多少子串。每次询问直接在这个数组上二分即可。

(Open Problem: 这里我们只需要输出子串的左右下标,类似对于 Rank 我们给出子串的下标,同样 SA 可以用类似方法在 log(n) 时间内解决问题。对于 Select 以及 Rank,用 SAM 是否也可以达到 log(n) 的复杂度?。

之后就是 lcp 了。。。(这题我用 hash 求 lcp 挂了。。= =)。

https://gist.github.com/lychees/7079186

const int N = int(1e5)+9, M = 26+1, LV = 20;
 
LL a[N]; char s[N]; int n;
int C[N], key[N], t1[N], t2[N];
 
struct SA{
 
    int a[3*N], sa[3*N], rk[N], h[N];
 
    inline void rs(int*x,int*y,int*sa,int n,int m){
        REP(i, n)key[i]=i[y][x];
        memset(C, 0,sizeof(C[0])*m);
        REP(i, n) ++C[key[i]];
        FOR(i, 1, m) C[i] += C[i-1];
        DWN(i, n, 0) sa[--C[key[i]]] = y[i];
    }
 
    void da(int*a,int*sa,int n,int m){
        int *x = t1, *y = t2;
        memset(C,0,sizeof(C[0])*m);
        REP(i, n)++C[x[i]=a[i]];
        FOR(i, 1, m)C[i]+=C[i-1];
        DWN(i, n, 0)sa[--C[x[i]]]=i;
        for(int l=1,p=1;p<n;l<<=1,m=p){
            p=0; FOR(i, n-l, n) y[p++]=i;
            REP(i, n) if (sa[i]>=l) y[p++]=sa[i]-l;
            rs(x,y,sa,n,m),swap(x,y),x[sa[0]]=p=0;FOR(i, 1, n)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+l]==y[sa[i-1]+l])?p:++p;
            ++p;
        }
    }
 
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int c0(int*r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int*r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
 else return r[a]<r[b]||r[a]==r[b]&&key[a+1]<key[b+1];}
 
void dc3(int*a,int*sa,int n,int m){
    int i, j, *an=a+n, *san=sa+n, ta=0, tb=(n+1)/3, tbc=0, p;
    a[n] = a[n+1] = 0; REP(i, n) if (i%3) t1[tbc++]=i;
 
    rs(a+2,t1,t2,tbc,m),rs(a+1,t2,t1,tbc,m),rs(a,t1,t2,tbc,m);
    p=0,an[F(t2[0])]=0;FOR(i, 1, tbc)
        an[F(t2[i])]=c0(a,t2[i-1],t2[i])?p:++p;
 
    if (++p < tbc) dc3(an,san,tbc,p);
    else REP(i, tbc) san[an[i]] = i;
 
    REP(i, tbc) if(san[i] < tb) t2[ta++] = san[i] * 3;
    if (n%3==1) t2[ta++] = n-1; rs(a,t2,t1,ta,m);
    REP(i, tbc) key[t2[i]=G(san[i])] = i;
 
    for(i=0,j=0,p=0; i<ta && j<tbc; p++)
        sa[p]=c12(t2[j]%3,a,t1[i],t2[j]) ? t1[i++] : t2[j++];
    for(;i<ta;p++) sa[p]=t1[i++]; for(;j<tbc;p++) sa[p]=t2[j++];
}
 
void get_h(){
    REP_1(i, n) rk[sa[i]] = i;
    int k=0;for(int i=0;i<n;h[rk[i++]]=k){
        if (k)--k;for(int j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
    }
}
 
int ST[LV][N];
 
#define cmp(a, b) (h[a]<h[b]?a:b)
 
inline int lcp(int l, int r){
    int lv = lg2(r - l); ++l, ++r;
    return min(h[ST[lv][l]], h[ST[lv][r-_1(lv)]]);
}
 
inline int lcpp(int l, int r){
    if (l == r) return n-l;
    l = rk[l], r = rk[r]; if (l > r) swap(l, r);
    return lcp(l, r);
}
 
void get_lcp(){
    REP_1(i, n) ST[0][i] = i;
    for (int lv = 1; _1(lv) <= n; ++lv){
        for (int i = 1; i + _1(lv) <= n + 1; ++i)
            ST[lv][i] = cmp(ST[lv-1][i], ST[lv-1][i+_1(lv-1)]);
    }
}
 
void bd(){
    dc3(a,sa,n+1,M),get_h(),get_lcp();
}
} A, B;
 
PII get(LL k){
    int r = lower_bound(a, a+n, k) - a; k -= a[r-1];
    return MP(A.sa[r]+1, A.h[r]+k);
}
 
LL f(LL x, LL y){
    if (x>a[n] || y>a[n]) return -1;
    PII a = get(x), b = get(y); int t = min(a.se, b.se);
    return sqr(LL(min(t,A.lcpp(a.fi-1, b.fi-1)))) + sqr(LL(min(t,B.lcpp(n-(a.fi+a.se-1), n-(b.fi+b.se-1)))));
}
 
 
int main(){
 
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
 
    int m; RD(n, m); strlen(RS(s));  REP(i, n) B.a[n-i-1]=A.a[i]=s[i]-='a'-1;
    A.bd(); B.bd(); REP_1(i, n) a[i]=a[i-1]+n-A.sa[i]-A.h[i];
    DO(m) OT(f(RD(), RD()));
}

External link:

http://www.lydsy.com:808/JudgeOnline/problem.php?id=3230