后缀数组练习_牛客博客

hdu 5769

题意：输入一个T，t组数据，每一组共两行，第一行是一个小写字母，第二行是仅由小写字母组成的字符串，问有多少种子串包含第一行的字符。比如 $aab$ 的子串有 $a、b、aab、ab$ 。统计一个字符串有多少种子串也是后缀数组经典的应用。
从文本串 $s[]="aab"$ 中提取子串可以分两步，先确定一个后缀，然后在后缀中确定前缀。比如
1.确定后缀 $sa[2]=1$ (表示按字典序第二小的后缀从 $s[1]$ 开始的---最小的是第一小，紫书的模板最小是第0小)，也就是后缀 $s2[]="ab"$ 。
2.确定前缀，可以选择 $"a"或者"b"$ ，共两个前缀，对应的子串为 $"a"、"ab"$ 。
3.确定后缀 $sa[1]="aab"$ ，有三个前缀 $"a"、"aa"、"aab"$
如果确定了一个后缀 $sa_i$ (值的范围是 $0\sim len-1$ ，从上面的例子可以知道前缀的数量是 $len-sa_i$ ，其实就是 $s[sa_i]\sim s[len-1]$ 有多少个字符就有多少个前缀)，通过上面的例子可以理解从 $sa_i$ 中提取的子串和 $sa_{i-1})$ 重复数量就是他们的最长公共前缀，也就是 $height_i$ 。所以不重复的子串数量为 $\Sigma len-sa_i-height_i$ 。就这么考虑就对了。
回到这一题，确定了后缀之后，对于前缀的的选取会有要求，前缀和后缀之间需要包含输入的第一行的字符，比方说改后缀后面第一个出现该字符的位置是 $pos$ ，那么前缀选择的位置就不能小于 $pos$ 。所以该题的答案就是 $\Sigma (n-max(sa[i]+height[i],w[sa[i]]) )$ 。
Code：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;                    //字符串的长度
char s[MAXN];                            //输入字符串
int sa[MAXN],cnt[MAXN],t1[MAXN],t2[MAXN],rk[MAXN],height[MAXN];
int n;

void build_sa(int n) {                                //n是字符串长度
    int m=127;                                //m是小写字母的ASCII码值范围，构成字符串s的后缀数组，每个字符的值必须为0~m-1
    int i,*x=t1,*y=t2;
    for(i=0;i<m;i++)    cnt[i]=0;
    for(i=0;i<n;i++)    cnt[x[i]=s[i]]++;//记录每个字符出现的次数
    for(i=1;i<m;i++)    cnt[i]+=cnt[i-1];//记录ASCII码小于等于i的字符个数 ，也就是每个字符的排名
    for(i=n-1;i>=0;i--)  sa[--cnt[x[i]]]=i;//--cnt[x[i]]就是一个字符出现多次，最后一个出现的排名最高
    //sa[]:从0到n-1
    for(int k=1;k<=n;k*=2){                    //利用对长度为k的排序结果对长度为2k的排序
        int p=0;
        //2nd
        for(i=n-k;i<n;i++)    y[p++]=i;
        for(i=0;i<n;i++)    if(sa[i]>=k)    y[p++]=sa[i]-k;
        //1st
        for(i=0;i<m;i++)    cnt[i]=0;
        for(i=0;i<n;i++)    cnt[x[y[i]]]++;
        for(i=1;i<m;i++)    cnt[i]+=cnt[i-1];
        for(i=n-1;i>=0;i--) sa[--cnt[x[y[i]]]]=y[i];
        swap(x,y);//y为中间数组更新x
        p=1; x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;//得到中间的rk[]值
        if(p>=n)    break;
        m=p;
    }
}
void getheight(){                        //n是字符串长度
    int i,j,k=0;
    for(i=0;i<=n;i++)    rk[sa[i]]=i;    //用sa[]推导rk[]
    for(i=0;i<n;i++){
        if(k)    k--;
        int j=sa[rk[i]-1];
        while(s[i+k]==s[j+k])    k++;
        height[rk[i]]=k;
    }
}
int w[MAXN],i,j,t;
long long ans;
char ch;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf(" %c%s",&ch, s);
        n=strlen(s);
           build_sa(n+1);                     //求后缀数组
           getheight();
           for (w[n]=n,i=n-1;i>=0;i--)
            if (s[i]==ch) w[i]=i;
            else w[i]=w[i+1];
        for (ans=0,i=1;i<=n;i++)
            ans+=(long long)(n-max(sa[i]+height[i],w[sa[i]]));
        printf("Case #%d: %lld\n", ++j, ans);
    }
    return 0;
}