By

文章目录
  1. 1. 题意
  2. 2. 分析

原题

题意

给你一个字符和一个字符串，问这个字符串的所有子串中包含这个字符的字串有多少个。

分析

当时看到的第一想法就是后缀数组，奈何只是去年区域赛接触了一下，忘得差不多了，也没有系统的写过运用的专题，所以刚开始还想的是用后缀自动机这个字符跑后缀自动机，但是对于每个字串，是包含字符又不是跟这个字符一毛一样，所以陷入迷局；

然后开始重新看后缀数组，想起来后缀数组处理单个字符串的不同字串个数！感觉有戏！然后，发现没办法处理重复的问题，减去height[]数组本身就是为了去重，我再减去这个
后缀中最靠前的字符x的位置的话，肯定多减去了，前面不包含x的前缀重复的部分。

ans+=n-sa[i]-height[i]-(*it-sa[i]);

所以，完全没辙试了很多种想法，跪完了比赛，比赛完，打开题解就发现，自己就是这个问题解决不了，看到答案一脸懵逼。

ans+=n-max(sa[i]+height[i],*it);

最后善良可爱穿女装的my告诉我了，虽然他觉得这个不算容斥啦，但是我还是觉得是容斥，因为完全没想过这种处理方法：
因为假设对于当前这个后缀来说，最近的x位置大于需要被去重的部分的长度，那么所有包含x的子串都是唯一的，如果最近的x位置小于需要被去重的部分的长度，那么需要被去重的包含x的子串已经存在不需要再被记录，而后面包含x的子串则也是唯一的。

wa：我也是服了我自己了，想打long long一个顺手写了个double活生生wa了快半个小时。。MDZZ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <vector>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int MAXN=100007;
int sa[MAXN];//SA数组，表示将S的n个后缀从小到大排序后把排好序的
             //的后缀的开头位置顺次放入SA中
int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值
int ran[MAXN],height[MAXN];
//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
//除s[n-1]外的所有s[i]都大于0，r[n-1]=0
//函数结束以后结果放在sa数组中
void build_sa(int s[],int n,int m)
{
    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]=s[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]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
        if(p>=n)break;
        m=p;//下次基数排序的最大值
    }
}
void getHeight(int s[],int n)
{
    int i,j,k=0;
    for(i=0;i<=n;i++)ran[sa[i]]=i;
    for(i=0;i<n;i++)
    {
        if(k)k--;
        j=sa[ran[i]-1];
        while(s[i+k]==s[j+k])k++;
        height[ran[i]]=k;
    }
}
char str[MAXN],x[3];
int s[MAXN];
vector<int>locx;
vector<int>::iterator it;
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    scanf("%d",&T);
    int kase=0;
    while(T--)
    {
        locx.clear();
        scanf("%s",x);
        scanf("%s",str);
        int n=strlen(str);
        for(int i=0;i<=n;i++){
            if(str[i]==x[0]){
                locx.push_back(i);
            }
        }
        for(int i=0;i<=n;i++)s[i]=str[i];
        build_sa(s,n+1,128);
        getHeight(s,n);
        long long ans=0;
        for(int i=0;i<=n;i++){
            it=lower_bound(locx.begin(),locx.end(),sa[i]);
            if(it!=locx.end()) {
                ans+=n-max(sa[i]+height[i],*it);
            }
        }
        printf("Case #%d: %I64d\n",++kase,ans);
    }
    return 0;
}
文章目录
  1. 1. 题意
  2. 2. 分析