字符串

专题练习 OI

书写原则

  对于每一种题目，首先有一个Todo-List构成的题目总览。如果题目简单，则在总览处写题解，否则在之后写详细题解。

后缀数组

题目总览

• xsy1828
   $n$个串串起来。二分。分类。
• uoj35
   模板题。
• bzoj1031
   倍增。
• bzoj3238
   求$\sum_{1\leq i<j\leq n}LCP(suf[i],suf[j])$。单调栈。
• bzoj4728
   二路归并。
• bzoj3230
• bzoj2251
• bzoj1692
• bzoj1717
• bzoj2119
• bzoj2946
• bzoj4556
• bzoj4310
• bzoj1692
• bzoj3172
• bzoj3277
• bzoj3473
• bzoj2754
• bzoj3796
• bzoj4199
• bzoj3879
• bzoj2780
• bzoj4698

【xsy1828】string

题意：给定$n$个字符串，求出一个最长的串，使得这个串或者这个串的回文在所有$n$个字符串中都出现。

分析：
对于$n$个字符串的处理，我们就把所有的串以及其回文串在一起。
求后缀数组sa以及height数组。
二分答案$x$，按$h[t]\ge x$进行分类，若个数等于n则OK。

关于$n$个串串在一起的实现：

char s[L]; int len;
int star[N],fini[N],slen[N];
int own[L];

后缀数组的实现：

int sa[L],rk[L],ht[L];
int sum[L],tsa[L],trk[L]; 
void Prework(void) {
    memset(sa,0,sizeof sa);
    memset(rk,0,sizeof rk);
    memset(ht,0,sizeof ht);
    memset(sum,0,sizeof sum);
    memset(tsa,0,sizeof tsa);
    memset(trk,0,sizeof trk);
    int lim=512,p;
    F(i,1,len)
        sum[rk[i]=s[i]]++;
    F(i,1,lim)
        sum[i]+=sum[i-1];
    D(i,len,1)
        sa[sum[rk[i]]--]=i;
    rk[sa[1]]=p=1;
    F(i,2,len) {
        if (s[sa[i]]!=s[sa[i-1]])
            p++;
        rk[sa[i]]=p;
    }
    lim=p;
    for (int j=1;lim!=len;j<<=1) {
        p=0;
        memset(tsa,0,sizeof tsa);
        F(i,len-j+1,len)
            tsa[++p]=i;
        F(i,1,len)
            if (sa[i]>j)
                tsa[++p]=sa[i]-j;
        memset(sum,0,sizeof sum);
        memmove(trk,rk,sizeof rk);
        F(i,1,len)
            sum[rk[i]=trk[tsa[i]]]++;
        F(i,1,lim)
            sum[i]+=sum[i-1];
        D(i,len,1)
            sa[sum[rk[i]]--]=tsa[i];
        rk[sa[1]]=p=1;
        F(i,2,len) {
            if (trk[sa[i]]!=trk[sa[i-1]]||trk[sa[i]+j]!=trk[sa[i-1]+j])
                p++;
            rk[sa[i]]=p;
        }
        lim=p;
    }
    p=0;
    F(i,1,len) {
        if (p>0)
            p--;
        while (s[i+p]==s[sa[rk[i]-1]+p])
            p++;
        ht[rk[i]]=p;
    }
}

分类的实现：

int Check(int lim) {
    tot=ind=0;
    memset(vis,0,sizeof vis);
    F(l,1,len) {
        int r=l;
        while (r+1<=len&&ht[r+1]>=lim)
            r++;
        ind++,tot=0;
        F(i,l,r)
            Add(sa[i],lim);
        if (tot==n)
            return 1;
        l=r;
    }
    return 0;
}

【bzoj3238】差异

一个细节：
对于后缀数组，我们开的空间是$n+1$。

if (trk[sa[i]]!=trk[sa[i-1]]||trk[sa[i]+j]!=trk[sa[i-1]+j]) lim++;
为什么不会越界？

因为若$a[i]=a[j]$，则$i+l-1\leq n,j+1-l\leq n$。
所以$i+l\leq n+1,j+l\leq n+1$。
所以$i+l,j+l$不会越界。

部分代码：

void Prework(void) {
    int lim=256;
    F(i,1,n) sum[rk[i]=s[i]]++;
    F(i,1,lim) sum[i]+=sum[i-1];
    D(i,n,1) sa[sum[rk[i]]--]=i;
    rk[sa[1]]=lim=1;
    F(i,2,n) {
        if (s[sa[i]]!=s[sa[i-1]])   //注意用s 
            lim++;
        rk[sa[i]]=lim;
    }
    for (int j=1;lim!=n;j<<=1) {
        memset(tsa,0,sizeof tsa); int p=0;
        F(i,n-j+1,n) tsa[++p]=i;
        F(i,1,n) if (sa[i]>j) tsa[++p]=sa[i]-j;
        memset(sum,0,sizeof sum);
        memcpy(trk,rk,sizeof rk);
        F(i,1,n) sum[rk[i]=trk[tsa[i]]]++;
        F(i,1,lim) sum[i]+=sum[i-1];
        D(i,n,1) sa[sum[rk[i]]--]=tsa[i];
        rk[sa[1]]=lim=1;
        F(i,2,n) {
            if (trk[sa[i]]!=trk[sa[i-1]]||trk[sa[i]+j]!=trk[sa[i-1]+j]) lim++;
            rk[sa[i]]=lim;
        }
    }
    int p=0;
    F(i,1,n) {
        if (p>0) p--;
        while (s[i+p]==s[sa[rk[i]-1]+p]) p++;
        ht[rk[i]]=p;
    }
}

void XXX(void) {
    stk[top=0]=1;
    F(j,2,n) {
        while (top>0&&ht[j]<=ht[stk[top]]) {
            tmp-=(LL)ht[stk[top]]*(stk[top]-stk[top-1]);
            stk[top--]=0;
        }
        stk[++top]=j;
        tmp+=(LL)ht[j]*(j-stk[top-1]);
        ans+=tmp;
    }
}

【bzoj4278】【ontak2015】Tasowanie

分析：每次肯定要尽可能选一个小一点的。一样大怎么办？比较字典序。可能会出现比较完的情况，所以在两个串的末尾都加一个INF。
把两个串接起来，后缀排序。

实现：在实现的时候由于数组没有开大一倍，RE了。
不明白为什么会RE。
但是不论如何，后缀数组的空间还是开大一倍好了。
以免出题人出错数据。

$k$路合并也可做。
用个优先队列。

Hash

bzoj3098
bzoj3162
bzoj2085
bzoj1125
bzoj2803
bzoj1054
bzoj3207
bzoj3507
bzoj4337
bzoj2124
bzoj1862
bzoj1056
bzoj3067
bzoj3097
bzoj2258
bzoj3198
bzoj2795
bzoj1414
bzoj3574

KMP

bzoj1009
bzoj3670
bzoj3942
bzoj1355
bzoj1461
bzoj3620
bzoj3213
bzoj1511
bzoj1729
bzoj3899
bzoj3796

exKMP

Manacher

回文自动机

后缀自动机

后缀树

bzoj3238
bzoj3879
bzoj3998
bzoj2555

波兰表

AC自动机

bzoj2754
bzoj2434
bzoj2938
bzoj1030
bzoj3881
bzoj3940
bzoj3172
bzoj1195
bzoj2533
bzoj1009
bzoj1444
bzoj4327
bzoj1212
bzoj3028

Fail树

bzoj3881
bzoj2434

Trie

bzoj3689
bzoj1954
bzoj3439
bzoj3166
bzoj1819
bzoj2741
bzoj3906
bzoj4212
bzoj4567
bzoj4523

最小表示法