OI题解 - Good Substrings (Codeforces) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - Good Substrings (Codeforces)

发表于 更新于 分类于 Valine：

最近准备比赛，博客gu了好久……

# 题面

> 洛谷CF271D 洛谷的翻译比较简单，就不自己写了 awa

# 解析

本来这道题不用 SAM……但是强行套一个 SAM 也不是不行。

注意到题目要求子串本质不同，而我们知道的能够记录所有子串信息且自带去重功能的字符串算法就是 SAM 了。

因此，我们先对主串建 SAM，然后考虑计算答案。

题目的意思是让我们计算有多少个区间 $[L,R]$，满足其中的某些字符出现的总次数不超过 $k$。假如不是要让我们计算所有的区间，而是让我们找到最大的区间，我们就有一个非常简单的算法，即滑动窗口。

滑动窗口的弊端是：对于一个右端点 $R$，它只能找到最小的 $L$ 使得 $[L,R]$ 是一个满足条件的区间。但是我们知道，非常显然的，如果区间 $[L,R]$ 满足条件，那么它的后缀都满足条件。

定义一个指针 $cur$，表示当前区间 $[L,R]$ 在 SAM 上对应了哪个节点。

于是就可以先从左到右枚举 $R$，然后滑窗滑出最小的 $L$ 使得 $[L,R]$ 满足条件，同时维护 $cur$ ——

  1. 如果 $R$ 往后挪，那就在 SAM 上沿对应的转移边跳；
  2. 如果 $L$ 往后挪，就相当于取了原来位置的一个后缀，如果当前的 $cur$ 已经不能表示 $[L,R]$ 了（因为SAM的一个节点表示了长度连续的且endpos相同的一段子串，如果 $L$ 增大，区间长度减小，可能就超过 $cur$ 的表示范围了），此时就要跳 link 边到下一个后缀去。

然后要计算所有后缀的答案，为了避免重复，我们需要记录每个点代表的串有哪些已经在之前计算过了。可以这样实现：记录一个点最长匹配到了多少。因为一个点对应的长度区间是固定的，而且如果长度为 $len$ 的被匹配了，那么长度小于 $len$ 的一定也匹配了，所以只需要记录最大匹配到的长度就是了。

# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1600;

struct NODE{
    int lnk,nxt[26],len,tag;
    inline int& operator [](const int &id){return nxt[id];}
};
struct SAMAUTO{
    NODE nod[N<<1];
    int lst,ncnt;
    inline NODE& operator [](const int &id){return nod[id];}
    SAMAUTO(){nod[lst=ncnt=1].lnk=-1;}
    inline void Expand(const int &c){
        int cur=++ncnt,p=lst;lst=cur;
        nod[cur].len=nod[p].len+1;
        while((~p) && !nod[p][c]) nod[p][c]=cur,p=nod[p].lnk;
        if(~p){
            int q=nod[p][c];
            if(nod[q].len==nod[p].len+1) nod[cur].lnk=q;
            else{
                int nq=++ncnt;
                nod[nq]=nod[q],nod[nq].len=nod[p].len+1;
                nod[q].lnk=nod[cur].lnk=nq;
                while((~p) && nod[p][c]==q) nod[p][c]=nq,p=nod[p].lnk;
            }
        }
        else nod[cur].lnk=1;
    }
    inline void Update(){
        for(int i=2;i<=ncnt;i++)
            nod[i].tag=nod[nod[i].lnk].len;
    }
    inline int Calc(int cur,int mat){
        int ans=0;
        if(cur>1){
            ans+=max(0,mat-nod[cur].tag);
            nod[cur].tag=max(nod[cur].tag,mat);
            cur=nod[cur].lnk;
        }
        while(cur>1 && nod[cur].tag!=nod[cur].len){
            ans+=nod[cur].len-nod[cur].tag;
            nod[cur].tag=nod[cur].len;
            cur=nod[cur].lnk;
        }
        return ans;
    }
    inline void Move(int &cur,int &mat,const int &c){
        while(cur>1 && !nod[cur][c]){
            cur=nod[cur].lnk;
            mat=nod[cur].len;
        }
        if(nod[cur][c]) mat++,cur=nod[cur][c];
    }
    inline void Delete(int &cur,int &mat){
        if(cur>1 && (--mat)<=nod[nod[cur].lnk].len)
            cur=nod[cur].lnk;
    }
};
SAMAUTO Sa;

char str[N],sau[N];
int lim,cnt;

int main(){
    scanf("%s%s%d",str,sau,&lim);
    int len=strlen(str);
    for(int i=0;i<len;i++) Sa.Expand(str[i]-'a');
    Sa.Update();
    int cur=1,mat=0,ans=0;
    for(int rig=0,lef=0;rig<len;rig++){
        int c=str[rig]-'a';
        Sa.Move(cur,mat,c);
        cnt+=sau[c]=='0';
        while(cnt>lim){
            cnt-=sau[str[lef++]-'a']=='0';
            Sa.Delete(cur,mat);
        }
        if(lef<=rig) ans+=Sa.Calc(cur,mat);
    }
    printf("%d\n",ans);
    return 0;
}

THE END

Thanks for reading!