1. 首页
2. 后缀数组
3. 本页

HDU 5769 Substring (后缀数组)

题目链接：点我~~

题意：输入一个字符，一个串，问你输入的串中的子串中有多少个包含这个字符。

思路：不重复子串的个数是len-sa[i]-height[i]，但是现在有这样的情况，就是字符是c，而sa[i]是dddcddd，那么它能贡献的值就是len-max((sa[i]+height[i]),c的位置)，因为若sa[i]+height[i]的值大于c的位置，这与正常的没有区别，但是若c的位置大于sa[i]+height[i]，那么这个sa能贡献的就只有c位置和之后的串，所遇这里取个最大值就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 800000;
const int MAXM = 20100;
/*
*suffix array
*倍增算法 O(n*logn)
*待排序数组长度为n,放在0~n-1中，在最后面补一个0
*da(str,n+1,sa,rank,height,, );  //注意是n+1;
*例如：
*n = 8;
* num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0
*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值
*  sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值
height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值
*/
//sa[i] 字典序第i小的后缀的下标
//height[i]  sa[i]与sa[i-1]两个后缀的相同前缀长度
//不重复子串的个数是len-sa[i]-height[i]  height为重复的

int t1[MAXN],t2[MAXN],c[MAXN];
//求SA数组需要的中间变量，不需要赋值
//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
//除s[n-1]外的所有s[i]都大于0，r[n-1]=0
//函数结束以后结果放在sa数组中

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

void da(char *str,int *sa,int *Rank,int *height,int n,int m)
{
    n++;
    int i, j, p, *x = t1, *y = t2;     //第一轮基数排序，如果s的最大值很大，可改为快速排序
    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;         //直接利用sa数组排序第二关键字
        for(i = n-j; i < n; i++)y[p++] = i;//后面的j个数第二关键字为空的最小
        for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j;         //这样数组y保存的就是按照第二关键字排序的结果
        //基数排序第一关键字
        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];        //根据sa和x数组计算新的x数组
        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++)
        Rank[sa[i]] = i;
    for(i = 0; i < n; i++)
    {
        if(k)
            k--;
        j = sa[Rank[i]-1];
        while(str[i+k] == str[j+k])
            k++;
        height[Rank[i]] = k;
    }
}

int Rank[MAXN],height[MAXN];

char str[MAXN];
int r[MAXN];
int sa[MAXN];
int nex[MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    int casee=1;
    while(t--)
    {
        char c[5];
        scanf("%s %s",c,str);
        int len = strlen(str);
        int n = len;
        da(str,sa,Rank,height,n,128);
        int pos=n;
        for(int i=n-1; i>=0; i--)
        {
            if(str[i]==c[0])
                pos=i;
            nex[i]=pos;
        }
        LL ans=0;
        for(int i=1; i<=n; ++i)
        {
            ans+=n-max(sa[i]+height[i],nex[sa[i]]);
        }
        printf("Case #%d: %lld\n",casee++,ans);

    }
    return 0;
}