数据结构 Homework 1

一个学期没写博客，因为没啥时间写，本来打算靠寒假把上学期的博客补了，结果也没实现。这学期决定好好搞博客。

第一周的作业主要是字符串算法，只有四道题。

1790 Unique Substring

题意：计算一个长度为 $n(n\le 10 ^{6})$ 的字符串中有多少长度为 $m(m<n,m\le10 ^{5})$ 的不同子串。

解析：水题，Hash 即可，这题卡了 $10 ^{6}+7$ 和 $10 ^{9}+7$ 的模数，自然溢出可以过。

代码：

//
// Created by 屋顶上的小丑 on 2023/2/27.
//
#include<cstdio>
#include<cstring>
#include<unordered_map>
using namespace std;
const int maxn=1e6;
int n,m;
unsigned long long p[maxn+5],h[maxn+5];
long long seed=37;
char s[maxn+5];
unsigned long long val(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
unordered_map<unsigned long long,bool> x;
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    h[0]=p[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*seed+s[i]-'a';
        p[i]=p[i-1]*seed;
    }
    int ans=0;
    for(int i=1;i<=n-m+1;i++)
    {
        long long v=val(i,i+m-1);
        if(!x[v])
        {
            ans++;
            x[v]=1;
        }
    }
    printf("%d",ans);
    return 0;
}

题意：给 $m(1\le m\le 100)$ 个数字字符串 $s _{i}(1\le \sum|s _{i}|\le 1500)$ 构成的集合 $S$ ，如果一个数不包含 $S$ 中的任何字符串为子串，那么这个数就是幸运数，求不大于 $n(1\le n\le 10 ^{2021})$ 的幸运数有多少个，答案对 $10 ^{9}+7$ 取模。保证 $n$ 没有前导零，但是 $s _{i}$ 可能有前导零。

解析：原题为[SDOI2014] 数数，一个数数题，要用到 AC 自动机和数位 DP。

建出 AC 自动机后，考虑怎么判断某个数包不包含 $S$ 中的字符串，首先插入时给每个字符串末尾打上标记，显然在自动机上不能经过这些点，否则就会包含其中一个串。然后考虑其他哪些节点跳 fail 后会到达这些叶节点，这些节点显然也不能经过，它们所代表的串的后缀也是 $S$ 中的某个串。我们可以在求 fail 时把以上不能经过的节点都打上标记。

然后就是经典数位 DP 了。 $i,j,k,l$ 分别代表各下标分别代表其中从高到低第 $i$ 位，在 AC 自动机上的 $j$ 节点，是否到达上界（判断是否不大于 $n$ ），是否之前全是前导 $0$ 。 $dp _{i,j,k,l}$ 则代表已经求出位数小于等于 $i$ 在以上限制下的幸运数数量。用记忆化搜索求出即可。

代码：

//
// Created by 屋顶上的小丑 on 2023/2/27.
//
#include<cstdio>
#include<cstring>
const int maxn=2021,maxm=1e2;
const int mod=1e9+7,maxs=1500;
int trie[maxs+5][10];
int m,tot,fail[maxs+5],q[maxs+5];
int dp[maxn+5][maxs+5][2][2],nlen;//长度，节点，是否匹配
bool end[maxs+5];
char n[maxn+5],s[maxm+5][maxs+5];
int inc(int a,int b)
{
    return (a+b>=mod)?a+b-mod:a+b;
}
void insert(char *s)
{
    int u=0,len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        if(!trie[u][s[i]-'0'])
            trie[u][s[i]-'0']=++tot;
        u=trie[u][s[i]-'0'];
    }
    end[u]=true;
}
void build()
{
    int l=1,r=0;
    for(int i=0;i<=9;i++)
        if(trie[0][i])
            q[++r]=trie[0][i];
    while(l<=r)
    {
        int u=q[l++];
        for(int i=0;i<=9;i++)
        {
            if(trie[u][i])
            {
                fail[trie[u][i]]=trie[fail[u]][i];
                end[trie[u][i]]|=end[trie[fail[u]][i]];
                q[++r]=trie[u][i];
            }
            else
                trie[u][i]=trie[fail[u]][i];
        }
    }
}
int solve(int now,int pos,bool lim,bool lead)
{
    if(end[pos])
        return 0;
    if(now>nlen)
        return !lead;
    if(dp[now][pos][lim][lead])
        return dp[now][pos][lim][lead];
    int res=0;
    int up=lim?(n[now]-'0'):9;
    for(int i=0;i<=up;i++)
    {
        bool flag=lead&(!i);
        res=inc(res,solve(now+1,flag?0:trie[pos][i],lim&(i==(n[now]-'0')),flag));
    }
    return dp[now][pos][lim][lead]=res;
}
int main()
{
    scanf("%s",n+1);
    nlen=strlen(n+1);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s[i]+1);
        insert(s[i]);
    }
    build();
    int ans=solve(1,0,1,1);
    printf("%d",ans);
    return 0;
}

1789 Period

题意：维护一个字符串 $s$ ，支持以下操作：

在 $s$ 的末尾加入字符 $x$ ，询问 $s$ 的最小周期。其中 $s$ 的一个周期 $p(p\in \N ^{\star})$ 满足 $\forall i(i+p\le |s|)$ 有 $s _{i}=s _{i+p}$ ；
删除 $s$ 末尾的一个字符。

字符集大小为 $10 ^{6}$ 级别。

解析：维护一个单串，会用到 KMP 自动机（其实就可以看作只添加一个字符串的 AC 自动机）。

要求求周期，对于一个长度为 $n$ 的字符串，已经求到了它的 $fail$ 指针（也是 KMP 中的 $next$ 数组），那么它的最小周期即为 $n-fail _{n}$ 。

现在考虑如何动态维护 $fail$ 指针。这里就会用到所谓的 KMP 自动机，不难发现如果只往 AC 自动机中添加一个字符串，那么每个字符的节点编号其实和它在串中的位置编号是一样的，我们只用考虑增加和删除字符的情况下如何快速求出 $fail$ 指针。

转移方程非常简单，假设我们已经处理好了 $u$ 之前的字符，对于第 $u+1$ 个字符，那么 $fail _{u+1}=trie _{fail _{u},s _{u+1}}$ ，同时更改 $trie$ 的结构，即：

trie _{u,c}=\begin{cases} trie _{fail _{u},c} & c\neq s _{u+1}\\ u+1 & c=s _{u+1} \end{cases}

有了转移方程就很好办了。不过要处理 $10 ^{6}$ 级别的字符集，我们需要利用可持久化线段树来加速维护，对于每一个节点都建立一颗线段树，然后支持查询和修改即可。

代码：

//
// Created by 屋顶上的小丑 on 2023/2/27.
//
#include<cstdio>
#include<cstring>
#define lson l,mid,ls[rt]
#define rson mid+1,r,rs[rt]
const int maxn=3e5;
const int maxx=1e6;
int n,tot,cnt,root[maxn+5];
int data[(maxn<<5)+5],now;
int ls[(maxn<<5)+5];
int rs[(maxn<<5)+5];
int p[maxx+5],fail[maxn+5];
void New(int &rt)
{
    ++tot;
    ls[tot]=ls[rt];
    rs[tot]=rs[rt];
    data[tot]=data[rt];
    rt=tot;
}
void update(int x,int val,int l,int r,int &rt)
{
    New(rt);
    if(l==r)
    {
        data[rt]=val;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        update(x,val,lson);
    else
        update(x,val,rson);
}
int query(int x,int l,int r,int rt)
{
    if(!rt)
        return 0;
    if(l==r)
        return data[rt];
    int mid=(l+r)>>1;
    if(x<=mid)
        return query(x,lson);
    else
        return query(x,rson);
}
void insert(int c)
{
    root[now]=root[fail[now]];
    fail[now+1]=query(c,1,n,root[now]);
    update(c,now+1,1,n,root[now]);
    now++;
    printf("%d\n",now-fail[now]);
    return ;
}
void remove()
{
    now--;
    if(!now)
        root[now]=0;
}
int main()
{
    scanf("%d",&n);
    int op,x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&x);
            if(!p[x])
                p[x]=++cnt;
            insert(p[x]);
        }
        else
            remove();
    }
    return 0;
}

1583 小W的字符串

题意：有一个 $m(1\le m\le 3\times 10 ^{5})$ 个字符串 $a _{i}(\sum |a _{i}|\le 3\times 10 ^{5})$ 构成的集合 $S$ ，可以利用其中的字符串拼成一个新的字符串（其中字符串之间可以重叠，即具有相同后缀与前缀的字符串可以合在一起，例如 $\mathtt{abc}$ 和 $\mathtt{bcd}$ 可以合成 $\mathtt{abcd}$ ）。现在给出一个新的字符串 $s(1\le |s|\le 3\times 10 ^{5})$ ，问要至少多少个 $S$ 中的字符串可以拼成 $s$ （ $S$ 中的字符串可重复使用），若拼不成输出 $-1$ 。

解析：AC 自动机与区间覆盖的合并。

多个字符串，先建立 AC 自动机，然后考虑怎么拼成 $s$ 。显然，如果用到了一个单词 $a _{i}$ ，那么 $a _{i}$ 一定是 $s$ 中的子串。于是就转化成了一个匹配问题，我们考虑如何求出 $s$ 中每个位置向前能匹配到的最大长度，显然能匹配的长度越大越优（匹配长度越大，需要用到的字符串就越少）。求出后就可以得到了一组匹配的区间，然后就转成了经典的区间覆盖问题，贪心即可。

要求能匹配，那么就说明要经过 AC 自动机中的叶节点，要记录长度则需要记录叶节点的深度，即它代表的字符串的长度。现在考虑其他节点，如果其他节点能通过跳 fail 到达叶节点，那么说明某个 $S$ 中的字符串是它的后缀，我们也需要为这个节点记录它能够匹配的长度，即这个后缀的长度。

如何实现呢？事实上我们只用记录叶节点的深度，然后记录其他节点能够跳到哪个叶节点即可。后者我们可以在求 fail 指针时一起实现。

最后就是区间覆盖的细节问题了，求出区间后，容易得到区间的右端点是有序的（就是 $s$ 中的每个位置），因此倒着扫描即可。区间覆盖问题用贪心解决，注意判断无解情况。

代码：

//
// Created by 屋顶上的小丑 on 2023/2/27.
//
#include<cstdio>
#include<cstring>
const int maxn=3e5;
int n,tot,fail[maxn+5];
int trie[maxn+5][26];
int q[maxn+5],dep[maxn+5];
int match[maxn+5],p[maxn+5];
bool end[maxn+5];
char s[maxn+5],a[maxn+5];
void insert(char *s)
{
    int u=0,len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        if(!trie[u][s[i]-'a'])
            trie[u][s[i]-'a']=++tot;
        u=trie[u][s[i]-'a'];
    }
    dep[u]=len;
    end[u]=1;
}
void build()
{
    int l=1,r=0;
    for(int i=0;i<26;i++)
        if(trie[0][i])
            q[++r]=trie[0][i];
    while(l<=r)
    {
        int u=q[l++];
        for(int i=0;i<26;i++)
        {
            if(trie[u][i])
            {
                fail[trie[u][i]]=trie[fail[u]][i];
                q[++r]=trie[u][i];
            }
            else
                trie[u][i]=trie[fail[u]][i];
            if(end[u])
                match[u]=u;
            else
                match[u]=match[fail[u]];
        }
    }
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a+1);
        insert(a);
    }
    build();
    int len=strlen(s+1),u=0;
    for(int i=1;i<=len;i++)
    {
        u=trie[u][s[i]-'a'];
        p[i]=dep[match[u]];
    }
    int l=len-p[len]+1,r=len,ans=1;
    if(l>r)
    {
        puts("-1");
        return 0;
    }
    while(l>1)
    {
        int nexl=l;
        for(int i=l-1;i<r;i++)
            if(i-p[i]+1<nexl)
                nexl=i-p[i]+1;
        if(nexl>=l)
        {
            puts("-1");
            return 0;
        }
        ans++;
        r=l-1;
        l=nexl;
    }
    printf("%d",ans);
    return 0;
}

1790 Unique Substring

1586 小O爱数数

1789 Period

1583 小W的字符串