后缀数组练习

hdu 5769

题意：输入一个T，t组数据，每一组共两行，第一行是一个小写字母，第二行是仅由小写字母组成的字符串，问有多少种子串包含第一行的字符。比如的子串有。统计一个字符串有多少种子串也是后缀数组经典的应用。
从文本串中提取子串可以分两步，先确定一个后缀，然后在后缀中确定前缀。比如
1.确定后缀(表示按字典序第二小的后缀从开始的---最小的是第一小，紫书的模板最小是第0小)，也就是后缀。
2.确定前缀，可以选择，共两个前缀，对应的子串为。
3.确定后缀，有三个前缀
如果确定了一个后缀(值的范围是，从上面的例子可以知道前缀的数量是，其实就是有多少个字符就有多少个前缀)，通过上面的例子可以理解从中提取的子串和重复数量就是他们的最长公共前缀，也就是。所以不重复的子串数量为。就这么考虑就对了。
回到这一题，确定了后缀之后，对于前缀的的选取会有要求，前缀和后缀之间需要包含输入的第一行的字符，比方说改后缀后面第一个出现该字符的位置是，那么前缀选择的位置就不能小于。所以该题的答案就是。
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;
}