后缀数组入门题

先上da算法(n*logn)求height的板子：

注意：height的有效值是2-n，sa的有效值是1-n，rank的有效值是0-n-1. 

　　　str 转成 r的时候，是从第0位到n位，最后的也带上，不然会RE

const int MAXN=2e5+5;

int t1[MAXN], t2[MAXN], c[MAXN];

bool cmp(int *r, int a, int b, int l){
    return r[a]==r[b] && r[a+l]==r[b+l];
}

void da(int str[], int sa[], int rk[], int height[], int n, int m) 
{
    n++;
    int i, j, p, *x=t1, *y=t2;
    for(i=0; i<m; i++) c[i]=0;
    for(i=0; i<n; i++) c[x[i]=str[i]]++;
    for(i=1; i<m; i++) c[i]+=c[i-1];
    for(i=n-1; i>=0; i--) sa[--c[x[i]]]=i;
    for(j=1; j<=n; j<<=1)
    {
        p=0;
        for(i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<m; i++) c[i]=0;
        for(i=0; i<n; i++) c[x[y[i]]]++;
        for(i=1; i<m; i++) c[i]+=c[i-1];
        for(i=n-1; i>=0; i--) sa[--c[x[y[i]]]]=y[i];
        swap(x, y);
        p=1; x[sa[0]]=0;
        for(i=1; i<n; i++) 
            x[sa[i]]=cmp(y, sa[i-1], sa[i], j)? p-1:p++;
        if(p>=n) break;
        m=p;
    }
    int k=0;
    n--;
    for(i=0; i<=n; i++) rk[sa[i]]=i;
    for(i=0; i<n; i++) 
    {
        if(k) k--;
        j=sa[rk[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[rk[i]]=k; 
    }
}

int rk[MAXN], sa[MAXN], height[MAXN], r[MAXN];
char str[MAXN]; 

例题：求不相同子串的个数（SPOJ 694）

题解：不同字串等于全部的子串-相同的子串个数（height的和）

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e3+5;

int t1[MAXN], t2[MAXN], c[MAXN];

bool cmp(int *r, int a, int b, int l){
    return r[a]==r[b] && r[a+l]==r[b+l];
}

void da(int str[], int sa[], int rk[], int height[], int n, int m) 
{
    n++;
    int i, j, p, *x=t1, *y=t2;
    for(i=0; i<m; i++) c[i]=0;
    for(i=0; i<n; i++) c[x[i]=str[i]]++;
    for(i=1; i<m; i++) c[i]+=c[i-1];
    for(i=n-1; i>=0; i--) sa[--c[x[i]]]=i;
    for(j=1; j<=n; j<<=1)
    {
        p=0;
        for(i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<m; i++) c[i]=0;
        for(i=0; i<n; i++) c[x[y[i]]]++;
        for(i=1; i<m; i++) c[i]+=c[i-1];
        for(i=n-1; i>=0; i--) sa[--c[x[y[i]]]]=y[i];
        swap(x, y);
        p=1; x[sa[0]]=0;
        for(i=1; i<n; i++) 
            x[sa[i]]=cmp(y, sa[i-1], sa[i], j)? p-1:p++;
        if(p>=n) break;
        m=p;
    }
    int k=0;
    n--;
    for(i=0; i<=n; i++) rk[sa[i]]=i;
    for(i=0; i<n; i++) 
    {
        if(k) k--;
        j=sa[rk[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[rk[i]]=k; 
    }
}


int rk[MAXN], sa[MAXN], height[MAXN], r[MAXN];
char str[MAXN];

int main()
{
    int T;
    for(cin>>T; T--; )
    {
        scanf("%s", str);
        int n=strlen(str);
        for(int i=0; i<=n; i++)
            r[i]=str[i];
        da(r, sa, rk, height, n, 128);
        int ans=n*(n+1)/2;
        for(int i=2; i<=n; i++)
            ans-=height[i];
        cout<<ans<<endl;
    }
    return 0;    
} 

例题：不可重叠最长重复子串（POJ 1743）

题解：二分答案k（子串的长度），转化成判定性问题，在扫一遍height，判断是否存在一段的height(该段的height都大于等于k)中的重复子串不相交。、

　　　本题题意：n个数组成的串，求是否有多个满足条件且不重叠的子串的长度大于等于5，有的话输出子串长度（最长）否则0，条件：子串的每一位和前一位的数字差相等。

　　　记录原串中每一位和前一位的差，在这个串中长度为n的串即对应原串中长度为n+1的串，注意这里还要满足子串要有间隔，否则对应的原串是恰好相连的。

　　　细节：sa算法中涉及到了桶排序，数字不可为负，为此可以同时加上一个数。

// 全部用scanf 220ms
// 用解除流绑定的cin 720ms
// 不太明白为什么时间差了这么多 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN=2e4+5;

int t1[MAXN], t2[MAXN], c[MAXN];
int rk[MAXN], sa[MAXN], height[MAXN], r[MAXN];
int a[MAXN];

bool cmp(int *r, int a, int b, int l){
    return r[a]==r[b] && r[a+l]==r[b+l];
}

void da(int str[], int sa[], int rk[], int height[], int n, int m) 
{
    n++;
    int i, j, p, *x=t1, *y=t2;
    for(i=0; i<m; i++) c[i]=0;
    for(i=0; i<n; i++) c[x[i]=str[i]]++;
    for(i=1; i<m; i++) c[i]+=c[i-1];
    for(i=n-1; i>=0; i--) sa[--c[x[i]]]=i;
    for(j=1; j<=n; j<<=1)
    {
        p=0;
        for(i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<m; i++) c[i]=0;
        for(i=0; i<n; i++) c[x[y[i]]]++;
        for(i=1; i<m; i++) c[i]+=c[i-1];
        for(i=n-1; i>=0; i--) sa[--c[x[y[i]]]]=y[i];
        swap(x, y);
        p=1; x[sa[0]]=0;
        for(i=1; i<n; i++) 
            x[sa[i]]=cmp(y, sa[i-1], sa[i], j)? p-1:p++;
        if(p>=n) break;
        m=p;
    }
    int k=0;
    n--;
    for(i=0; i<=n; i++) rk[sa[i]]=i;
    for(i=0; i<n; i++) 
    {
        if(k) k--;
        j=sa[rk[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[rk[i]]=k; 
    }
}

bool check(int k, int n)
{
    int L=sa[1], R=sa[1];
    for(int i=2; i<=n; i++)
    {
        if(height[i]>=k)
        {
            L=min(L, sa[i]);
            R=max(R, sa[i]);
            if(R-L>k)  //这里是大于，要有间隔 
                return true;    
        }
        else 
            L=R=sa[i];
    }
    return false;
}

int main()
{
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    while(cin>>n, n)
    {
        //for(int i=0; i<n; i++) cin>>a[i];
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        n--;
        for(int i=0; i<n; i++) r[i]=a[i+1]-a[i]+100;
        r[n]=0;
        da(r, sa, rk, height, n, 256);
        
        int l=1, r=n/2; //这种二分从1开始 
        while(l<=r)       
        {
            int mid=(l+r)/2;
            if(check(mid, n)) l=mid+1;
            else r=mid-1;
        }
        if(r>=4) cout<<r+1<<endl;
        else cout<<"0"<<endl;
    }
    return 0;    
} 

例题：可重叠kci的最长重复子串（POJ 3261）

题解：二分答案，在check一下就完事了。注意这里的m很大，求sa数组的中间变量 ws（或者c）也要相应变大，而不是MAXN了

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN=2e4+5;
const int MAXM=1e6+5;

int t1[MAXN], t2[MAXN], c[MAXM];

bool cmp(int *r, int a, int b, int l){
    return r[a]==r[b] && r[a+l]==r[b+l];
}

void da(int str[], int sa[], int rk[], int height[], int n, int m) 
{
    n++;
    int i, j, p, *x=t1, *y=t2;
    for(i=0; i<m; i++) c[i]=0;
    for(i=0; i<n; i++) c[x[i]=str[i]]++;
    for(i=1; i<m; i++) c[i]+=c[i-1];
    for(i=n-1; i>=0; i--) sa[--c[x[i]]]=i;
    for(j=1; j<=n; j<<=1)
    {
        p=0;
        for(i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<m; i++) c[i]=0;
        for(i=0; i<n; i++) c[x[y[i]]]++;
        for(i=1; i<m; i++) c[i]+=c[i-1];
        for(i=n-1; i>=0; i--) sa[--c[x[y[i]]]]=y[i];
        swap(x, y);
        p=1; x[sa[0]]=0;
        for(i=1; i<n; i++) 
            x[sa[i]]=cmp(y, sa[i-1], sa[i], j)? p-1:p++;
        if(p>=n) break;
        m=p;
    }
    int k=0;
    n--;
    for(i=0; i<=n; i++) rk[sa[i]]=i;
    for(i=0; i<n; i++) 
    {
        if(k) k--;
        j=sa[rk[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[rk[i]]=k; 
    }
}

int rk[MAXN], sa[MAXN], height[MAXN], r[MAXN];

bool check(int n, int k, int len)
{
    int cnt=1;
    for(int i=2; i<=n; i++)
    {
        if(height[i]>=len)
        {
            cnt++;
            if(cnt>=k) return true;
        }
        else cnt=1;
    }
    return false;
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++)
        scanf("%d", &r[i]);
    r[n]=0;
    da(r, sa, rk, height, n, 1000002);
    int l=1, r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(n, k, mid)) l=mid+1;
        else r=mid-1;
    }
    printf("%d
", r);
    return 0;
}

例题：求给定2个字符串A和B的最长公共子串（POJ 2774）

题解：中间隔开，连在一起，da，在扫一遍height，如果此时不是同一个字符串中的话，ans=max（ans， height【i】）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN=2e5+5;

int t1[MAXN], t2[MAXN], c[MAXN];

bool cmp(int *r, int a, int b, int l){
    return r[a]==r[b] && r[a+l]==r[b+l];
}

void da(int str[], int sa[], int rk[], int height[], int n, int m) 
{
    n++;
    int i, j, p, *x=t1, *y=t2;
    for(i=0; i<m; i++) c[i]=0;
    for(i=0; i<n; i++) c[x[i]=str[i]]++;
    for(i=1; i<m; i++) c[i]+=c[i-1];
    for(i=n-1; i>=0; i--) sa[--c[x[i]]]=i;
    for(j=1; j<=n; j<<=1)
    {
        p=0;
        for(i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<m; i++) c[i]=0;
        for(i=0; i<n; i++) c[x[y[i]]]++;
        for(i=1; i<m; i++) c[i]+=c[i-1];
        for(i=n-1; i>=0; i--) sa[--c[x[y[i]]]]=y[i];
        swap(x, y);
        p=1; x[sa[0]]=0;
        for(i=1; i<n; i++) 
            x[sa[i]]=cmp(y, sa[i-1], sa[i], j)? p-1:p++;
        if(p>=n) break;
        m=p;
    }
    int k=0;
    n--;
    for(i=0; i<=n; i++) rk[sa[i]]=i;
    for(i=0; i<n; i++) 
    {
        if(k) k--;
        j=sa[rk[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[rk[i]]=k; 
    }
}

int rk[MAXN], sa[MAXN], height[MAXN], r[MAXN];
char str[MAXN]; 

int main()
{
    scanf("%s", str);
    int len1=strlen(str);
    str[len1]='$';
    scanf("%s", str+len1+1);
    int n=strlen(str);
    for(int i=0; i<n; i++) r[i]=str[i];
    r[n]=0;
    da(r, sa, rk, height, n, 128);
    int ans=0;
    for(int i=2; i<=n; i++)
    {
        if(len1<max(sa[i-1], sa[i]) && len1>min(sa[i-1], sa[i]))
            ans=max(ans, height[i]);
    }
    printf("%d
",ans);
    return 0;
}