首页 > 其他分享 >题解:CF235C Cyclical Quest

题解:CF235C Cyclical Quest

时间:2024-08-25 21:03:40浏览次数:11  
标签:insert Cyclical string SAM int 题解 st vis CF235C

题意

给定一个主串 \(S\) 和 \(n\) 个询问串,求每个询问串的所有循环同构在主串中出现的次数总和。

分析

后缀自动机好题。

循环同构的过程可以看作从该串的头部删除一个字符,并在尾部加入一个字符。

在后缀自动机上,跳 parent 树的过程就相当于删除头部的若干个字符。

所以我们可以套路地把询问串 \(s_i\) 复制一遍首尾相接,然后模拟 SAM 匹配子串的过程,有以下两种情况:

  • 如果无法继续匹配,那么跳 parent 树直至可以匹配并更新长度。
  • 如果长度 \(l\) 大于该询问串的长度,删除首字母并更新当前长度,同时跳 parent 树找到当前节点。

另外一个问题是循环同构可能产生相同的子串,比如 \(\texttt{abab}\) 将前两位拼到最后得到的字符串也是 \(\texttt{abab}\)。

此时就要在节点上存储一个标记,判断该子串有没有被访问过。

也可以使用哈希等方法求出最小循环节再处理。

时间复杂度 \(O(|S|+\sum|s_i|)\)。

AC 记录

Code

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000006

namespace SAM
{
    struct node
    {
        int fa, len, ch[26];
        node() {memset(this, 0, sizeof *this);}
    }st[maxn<<1];

    int siz[maxn<<1];

    int la=1, cnt=1;

    void insert(int c)
    {
        int p=la, u=la=++cnt;
        siz[u]=1;
        st[u].len=st[p].len+1;
        for(;p&&!st[p].ch[c];p=st[p].fa)
            st[p].ch[c]=u;
        if(!p) return st[u].fa=1, void();
        int q=st[p].ch[c];
        if(st[q].len==st[p].len+1) 
            return st[u].fa=q, void();
        int v=++cnt;
        st[v]=st[q];
        st[v].len=st[p].len+1;
        st[q].fa=st[u].fa=v;
        for(;p&&st[p].ch[c]==q;p=st[p].fa)
            st[p].ch[c]=v;
    }

    vector<int> e[maxn<<1];

    void build_tree()
    {
        for(int i=2;i<=cnt;i++)
            e[st[i].fa].emplace_back(i);
    }

    void dfs(int u)
    {
        for(auto v:e[u])
            dfs(v), siz[u]+=siz[v];
    }

    bitset<maxn<<1> vis;

    int query(string &s)
    {
        vis.reset();
        int p=1, l=0, ret=0;
        int n=s.size();
        for(int i=1;i<=2;i++) for(auto c:s)
        {
            while(p&&!st[p].ch[c-'a']) l=st[p=st[p].fa].len;
            if(st[p].ch[c-'a']) p=st[p].ch[c-'a'], l++;
            while(l>n) l--, p=(l==st[st[p].fa].len)?st[p].fa:p; 
            if(l==n&&!vis[p]) ret+=siz[p], vis[p]=1;
        }
        return ret;
    }

    void insert(string &s)
    {
        for(auto c:s) insert(c-'a');
    }
}

string s;

int main()
{
    cin>>s;
    SAM::insert(s);
    SAM::build_tree();
    SAM::dfs(1);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) 
        cin>>s, cout<<SAM::query(s)<<'\n';
}#include<bits/stdc++.h>
using namespace std;
#define maxn 1000006

namespace SAM
{
    struct node
    {
        int fa, len, ch[26];
        node() {memset(this, 0, sizeof *this);}
    }st[maxn<<1];

    int siz[maxn<<1];

    int la=1, cnt=1;

    void insert(int c)
    {
        int p=la, u=la=++cnt;
        siz[u]=1;
        st[u].len=st[p].len+1;
        for(;p&&!st[p].ch[c];p=st[p].fa)
            st[p].ch[c]=u;
        if(!p) return st[u].fa=1, void();
        int q=st[p].ch[c];
        if(st[q].len==st[p].len+1) 
            return st[u].fa=q, void();
        int v=++cnt;
        st[v]=st[q];
        st[v].len=st[p].len+1;
        st[q].fa=st[u].fa=v;
        for(;p&&st[p].ch[c]==q;p=st[p].fa)
            st[p].ch[c]=v;
    }

    vector<int> e[maxn<<1];

    void build_tree()
    {
        for(int i=2;i<=cnt;i++)
            e[st[i].fa].emplace_back(i);
    }

    void dfs(int u)
    {
        for(auto v:e[u])
            dfs(v), siz[u]+=siz[v];
    }

    bitset<maxn<<1> vis;

    int query(string &s)
    {
        vis.reset();
        int p=1, l=0, ret=0;
        int n=s.size();
        for(int i=1;i<=2;i++) for(auto c:s)
        {
            while(p&&!st[p].ch[c-'a']) l=st[p=st[p].fa].len;
            if(st[p].ch[c-'a']) p=st[p].ch[c-'a'], l++;
            while(l>n) l--, p=(l==st[st[p].fa].len)?st[p].fa:p; 
            if(l==n&&!vis[p]) ret+=siz[p], vis[p]=1;
        }
        return ret;
    }

    void insert(string &s)
    {
        for(auto c:s) insert(c-'a');
    }
}

string s;

int main()
{
    cin>>s;
    SAM::insert(s);
    SAM::build_tree();
    SAM::dfs(1);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) 
        cin>>s, cout<<SAM::query(s)<<'\n';
}

标签:insert,Cyclical,string,SAM,int,题解,st,vis,CF235C
From: https://www.cnblogs.com/redacted-area/p/18379568

相关文章

  • 7z解压crc错误_7-Zip - 常见问题解答
    7z解压crc错误_7-Zip-常见问题解答7z解压crc错误_7-Zip-常见问题解答1.引言1.17-Zip简介1.2CRC错误概述2.7z文件和CRC错误2.1什么是7z文件2.2CRC错误的定义2.3CRC错误对文件的影响3.常见原因分析3.1文件传输过程中的错误3.2存储介质的损坏3.3不兼容的压......
  • 题解:P5680 [GZOI2017] 共享单车
    题目分析出题人是擅长隐藏题意的建树首先给你一张无向图,然后指定一个根节点\(k\),从根节点开始沿最短路到每一个节点。如果到某个节点有多条最短路径,选择上一个节点编号最短的。考虑记录前驱的Dijkstra。namespaceDJ{intdis[maxn],pre[maxn],val[maxn],vis[maxn]......
  • 题解:SP22382 ETFD - Euler Totient Function Depth
    题目链接:link,点击这里喵。前置知识:【模板】线性筛素数,欧拉函数,点击这里喵。题意简述:给定整数$l,r,k$,求出$[l,r]$中有多少个整数不断对自己取欧拉函数刚好$k$次结果为$1$。思路:看眼数据范围,$10^{10}$的量级显然不容我们每次暴力,故考虑预处理$\varphi(i),can(i,k),su......
  • 【面试系列】大数据平台常见面试题解答
    欢迎来到我的博客,很高兴能够在这里和您见面!欢迎订阅相关专栏:工......
  • AtCoder ABC 368题解
    前言本题解部分思路来自于网络。A-Cut题目大意有\(n\)张卡片叠在一起,从上到下给出\(n\)卡片的编号,将\(k\)张卡片从牌堆底部放到顶部后,从上到下输出卡片的编号。解题思路按照题意模拟即可。code#include<bits/stdc++.h>usingnamespacestd;inta[105];intmai......
  • SP666 VOCV - Con-Junctions 题解
    注意到这个问题具有最优子结构性,考虑树上dp。记$dp[i][0/1]$表示i号节点不放灯或放灯的最小值,$s[i][0/1]$为对应的方案数。那么我们可以进行如下转移:$dp[u][0]=\sum_{u->v}dp[v][1]$$dp[u][1]=\sum_{u->v}\min(dp[v][0],dp[v][1])$在更新对应的dp数组时,我们用......
  • P9482 [NOI2023] 字符串 题解
    题目描述\(T\)组数据,给定长为\(n\)的字符串\(s\),\(q\)次询问,给定\(i,r\),求有多少个\(l\)满足:\(1\lel\ler\)。\(s[i:i+l-1]\)字典序小于\(R(s[i+l:i+2l-1])\)。数据范围\(1\leT\le5,1\len,q\le10^5,1\lei+2r-1\len\)。时间限制\(\texttt{1s}\),......
  • Triple Attack 题解
    直接暴力显然不可行。我们容易发现,变量\(T\)的增量以\(3\)为循环,一次循环会造成\(5\)的贡献,所以我们容易想到对每个\(a_i\)直接对\(5\)计算倍数和取余,然后对于余数分类讨论去增加,然后对于倍数部分统一增加即可。有些细节。Code#include<bits/stdc++.h>//#include......
  • Minimum Steiner Tree 题解
    原题,详见P10723。几乎相同,我们只需要以一个需要选择的点为根,遍历子树看看有没有出现需要选择的点,然后直接去删除即可,可以看我的博客。但是我们也可以换一种做法,用类似拓扑排序的算法。先找到所有只连一条边且没有被选择的点,然后放进队列,接着依次取出队头遍历与它相连的点,同时记......
  • k8s中coredns访问连接拒绝问题解决
    问题现象1、节点访问coredns连接拒绝2、内部pod无法正常进行解析问题解决思路检查CoreDNSPod状态是否正常[root@k8s-master01~]#kubectlgetpods-nkube-system-lk8s-app=kube-dnsNAMEREADYSTATUSRESTARTSAGEcoredns-7b8d6fc5......