数据结构 Test 0

第 $0$ 次机考，幸好不怎么计分，考了三道字符串题。

1803 故意串

题意：对于字符串 $S(|S|\le 10 ^{6})$ ，它的故意串 $D$ 满足 $D$ 是 $S$ 的真前缀且 $S$ 是 $D+D$ 的前缀（故意串可以不存在），求 $S$ 所有前缀的最大故意串长度之和（若不存在视为 $0$ ）。

解析：容易发现，字符串 $S$ 最大故意串 $D$ 的长度就是 $S$ 的长度减去 $S$ 的最小非零 $\text{Border}$ 长度。可以通过 KMP 算法求出最大 $\text{Border}$ ，那么如何计算最小的呢？通过 $next$ 数组传递即可。设 $t _{i}$ 代表前缀 $s _{1\cdots i}$ 的最小非零 $\text{Border}$ ，如果 $next _{i}=0$ ，那么令 $t _{i}=i$ ，否则令 $t _{i}=t _{next _{i}}$ 即可。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/6.
//
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
using namespace std;
const int maxn=1e6;
int n,nex[maxn+5],t[maxn+5];
char s[maxn+5];
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        long long ans=0;
        scanf("%s",s+1);
        memset(nex,0,sizeof(nex));
        int len=strlen(s+1);
        nex[1]=0;
        t[1]=1;
        for(int i=2,j=0;i<=len;i++)
        {
            while(j&&s[i]!=s[j+1])
                j=nex[j];
            if(s[i]==s[j+1])
                j++;
            nex[i]=j;
            if(!nex[i])
                t[i]=i;
            else
                t[i]=t[nex[i]];
            ans+=(i-t[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

1794 胡言乱语的ChatGPT

题意：给出 $n(n\le 2\times 10 ^{5})$ 个字符串 $t _{1},t _{2},\cdots t _{n}(\sum |t _{i}|\le 2\times 10 ^{5})$ ，同时给出文本串 $s(|s|\le 2\times 10 ^{5})$ ，定义 $s$ 与 $t _{i},t _{j}$ 的匹配度为 $s$ 串中 $t _{i}+t _{j}$ 的出现次数（起始位置不同即算不同），记作 $\text{cnt}(s,t _{i},t _{j})$ ，求 $\displaystyle{\sum _{i=1} ^{n}\sum _{j=1} ^{n}\text{cnt}(s,t _{i},t _{j})}$ 。

解析：经典数数题。对于 $t _{i}+t _{j}$ 在 $s$ 中的出现次数，考虑枚举 $k=1\sim |s|$ 作为 $t _{i}$ 与 $t _{j}$ 的分界点，求出 $s$ 中以 $s _{k}$ 为结尾的匹配数量 $end _{k}$ 和以 $s _{k+1}$ 为开头的匹配数量 $begin _{k}$ ，答案即为 $\displaystyle {\sum _{i=1} ^{|s|}end _{i}\cdot begin _{i+1}}$ 。对于 $end _{k}$ ，直接建立出 AC 自动机，对于每个字符串的结尾打上标记后，在求出每个 $s _{k}$ 对应自动机上结点在 fail 树中到根节点的路径上有多少个标记即可，可以在建立自动机的同时进行统计，也可以建立完后再向求前缀一样统计。对于 $begin _{k}$ ，将所有字符串倒过来用一个新的 AC 自动机，统计方法与 $end$ 相同。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/6.
//
#include<cstdio>
#include<cstring>
const int maxn=2e5;
int n,q[maxn+5],pos[maxn+5],rev[maxn+5];
char s[maxn+5],t[maxn+5];
class AC_automation
{
public:
    int trie[maxn+5][26],tot=0;
    int fail[maxn+5],ed[maxn+5];
    void insert(char *s)
    {
        int u=0,len=strlen(s+1);
        for(int i=1;i<=len;i++)
        {
            int c=s[i]-'a';
            if(!trie[u][c])
                trie[u][c]=++tot;
            u=trie[u][c];
        }
        ed[u]++;
    }
    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];
            }
            ed[u]+=ed[fail[u]];
        }
    }
}a,b;
int main()
{
    scanf("%s",s+1);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",t+1);
        a.insert(t);
        int len=strlen(t+1);
        for(int j=1;j<=(len+1)/2;j++)
        {
            char c=t[j];
            t[j]=t[len-j+1];
            t[len-j+1]=c;
        }
        b.insert(t);
    }
    a.build();
    b.build();
    long long ans=0;
    int m=strlen(s+1),u=0;
    for(int i=1;i<=m;i++)
    {
        u=a.trie[u][s[i]-'a'];
        pos[i]=a.ed[u];
    }
    u=0;
    for(int i=m;i>=1;i--)
    {
        u=b.trie[u][s[i]-'a'];
        rev[i]=b.ed[u];
    }
    for(int i=1;i<m;i++)
        ans+=pos[i]*rev[i+1];
    printf("%lld",ans);
    return 0;
}

1795 Dracarys

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

插入一个字符串 $s$ （保证集合中之前无 $s$ ）；
删除一个字符串 $s$ （保证 $s$ 之前在集合中）；
给出一个字符串 $t$ ，问 $t$ 中总共出现了多少个集合中的字符串（出现次数为起始位置不同即可）。

给出 $n(n\le 3\times 10 ^{5})$ 个操作，要求强制在线。同时所有操作 1 和 3 中涉及的字符串长度和不超过 $3\times 10 ^{5}$ 。

解析：原题为 CF710F String Set Queries。

由于要求强制在线，我们考虑 AC 自动机与二进制分组。

我们可以维护少于 $\log n$ 个 AC 自动机，每个自动机中插入的字符串个数为 $2$ 的幂，新来一个字符串时就先建立一个新的 AC 自动机来存它，这个 AC 自动机里面目前只有它一个字符串。每当有两个 AC 自动机中插入的字符串个数相同时，就可以合并成一个更大的 AC 自动机。这一步是建立在 trie 的合并之上的，因此我们需要保存最初的 trie 的信息，在插入与合并完之后再重新建立 AC 自动机求新的 fail。询问很简单，对于每个插入的字符串末尾结点给出贡献（插入贡献为 $1$ ，删除贡献为 $-1$ ），在每次建立 AC 自动机时与上题一样求出总和。对于询问则在每一个 AC 自动机上跑一遍字符串 $t$ 并求和即可。

由于最多有 $\log n$ 个 AC 自动机，故查询复杂度为 $\sum |t|\log n$ ；而对于插入，每个串最多经历 $\log n$ 次合并（每次合并大小翻倍），故最多经历 $\log n$ 次重构，而重构与合并都是线性的。故插入总复杂度为 $\sum |s|\log n$ 。因此最终总复杂度为 $O(n\log n)$ 级别。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/7.
//
#include<cstdio>
#include<cstring>
const int maxn=3e5;
int n,m,tot,fail[maxn+5];
int trie[maxn+5][26],ac[maxn+5][26];
int q[maxn+5],ed[maxn+5],rt[maxn+5];
int cnt,num[maxn+5];
long long sum[maxn+5];
char s[maxn+5];
void insert(char *s,int now,int val)
{
    rt[now]=++tot;
    int u=tot,len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        int c=s[i]-'a';
        if(!trie[u][c])
            trie[u][c]=++tot;
        u=trie[u][c];
    }
    ed[u]+=val;
}
void build(int root)
{
    int l=1,r=0;
    sum[root]=0;
    for(int i=0;i<26;i++)
    {
        if(trie[root][i])
        {
            ac[root][i]=trie[root][i];
            fail[ac[root][i]]=root;
            q[++r]=ac[root][i];
        }
        else
            ac[root][i]=root;
    }
    while(l<=r)
    {
        int u=q[l++];
        for(int i=0;i<26;i++)
        {
            if(trie[u][i])
            {
                ac[u][i]=trie[u][i];
                fail[ac[u][i]]=ac[fail[u]][i];
                q[++r]=ac[u][i];
            }
            else
                ac[u][i]=ac[fail[u]][i];
        }
        sum[u]=sum[fail[u]]+ed[u];
    }
}
int merge(int x,int y)
{
    if(!(x&&y))
        return x|y;
    ed[x]+=ed[y];
    for(int i=0;i<26;i++)
        trie[x][i]=merge(trie[x][i],trie[y][i]);
    return x;
}
void add(char *s,int val)
{
    insert(s,++cnt,val);
    num[cnt]=1;
    while(cnt>1&&num[cnt]==num[cnt-1])
    {
        cnt--;
        num[cnt]+=num[cnt+1];
        rt[cnt]=merge(rt[cnt],rt[cnt+1]);
    }
    build(rt[cnt]);
}
long long query(char *s)
{
    long long ans=0;
    int len=strlen(s+1);
    for(int i=1;i<=cnt;i++)
    {
        int u=rt[i];
        for(int j=1;j<=len;j++)
        {
            u=ac[u][s[j]-'a'];
            ans+=sum[u];
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    int op;
    long long lasans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %s",&op,s+1);
        if(m)
            op^=lasans;
        if(op==1)
            add(s,1);
        else if(op==2)
            add(s,-1);
        else
            printf("%lld\n",lasans=query(s));
    }
    return 0;
}