【CF235C】Cyclical Quest(后缀自动机)
题面
题解
大致翻译:
给定一个串
然后若干组询问
每次也给定一个串
这个串可以旋转(就是把最后一位丢到最前面这样子)
问这个串以及其旋转的串在给定的串中出现了多少次
显然,串可以旋转,那么考虑在后面再接一份就行了
匹配的话就是后缀自动机的匹配
但是额外的注意一点
如果当前匹配出来的最大长度\(>=len\)
也就是当前串的长度
那么就要跳父亲
因为旋转后可能有相同的串出现
所以要开一个数组记录当前节点是否已经算过答案
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 1200000
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Node
{
int son[26];
int ff,len;
}t[MAX<<1];
int last=1,tot=1;
int size[MAX<<1];
ll sum[MAX<<1];
char ch[MAX];
int a[MAX],c[MAX];
int vis[MAX];
void extend(int c)
{
int p=last,np=++tot;
t[np].len=t[p].len+1;
size[last=np]++;
while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;
if(!p)t[np].ff=1;
else
{
int q=t[p].son[c];
if(t[q].len==t[p].len+1)t[np].ff=q;
else
{
int nq=++tot;
t[nq]=t[q];
t[nq].len=t[p].len+1;
t[q].ff=t[np].ff=nq;
while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;
}
}
}
int main()
{
scanf("%s",ch+1);
int n=strlen(ch+1);
for(int i=1;i<=n;++i)extend(ch[i]-97);
for(int i=1;i<=tot;++i)c[t[i].len]++;
for(int i=1;i<=tot;++i)c[i]+=c[i-1];
for(int i=1;i<=tot;++i)a[c[t[i].len]--]=i;
for(int i=tot;i;--i)size[t[a[i]].ff]+=size[a[i]];
memset(vis,63,sizeof(vis));
int Q=read();
while(Q--)
{
scanf("%s",ch+1);
int l=strlen(ch+1);
for(int i=1;i<l;++i)ch[i+l]=ch[i];
int now=1,len=0;
ll ans=0;
for(int i=1;i<l+l;++i)
{
int c=ch[i]-97;
while(now&&!t[now].son[c])now=t[now].ff,len=t[now].len;
if(!now)now=1,len=0;
else now=t[now].son[c],len+=1;
while(now&&t[t[now].ff].len>=l)now=t[now].ff,len=t[now].len;
if(len>=l&&vis[now]!=Q)ans+=size[now],vis[now]=Q;
}
cout<<ans<<endl;
}
return 0;
}
【CF235C】Cyclical Quest(后缀自动机)的更多相关文章
-
【Codeforces235C】Cyclical Quest 后缀自动机
C. Cyclical Quest time limit per test:3 seconds memory limit per test:512 megabytes input:standard i ...
-
Codeforces 235C Cyclical Quest - 后缀自动机
Some days ago, WJMZBMR learned how to answer the query "how many times does a string x occur in ...
-
CF 235C. Cyclical Quest [后缀自动机]
题意:给一个主串和多个询问串,求询问串的所有样子不同的周期同构出现次数和 没有周期同构很简单就是询问串出现次数,|Right| 有了周期同构,就是所有循环,把询问串复制一遍贴到后面啊!思想和POJ15 ...
-
Codeforces Round #146 (Div. 1) C - Cyclical Quest 后缀自动机+最小循环节
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk mak ...
-
CF235C Cyclical Quest(SAM)
/* 统计串的出现次数显然可以在自动机上匹配出来即可 但是每次都挨个匹配的话会时间爆炸 那么考虑我们把串复制一份, 然后一起在后缀自动机上跑, 当我们匹配长度大于该串长度的时候强行失配即可 可能会有旋 ...
-
CF235C Cyclical Quest
题意 给定一个长度为\(n\)的母串 \(q\)组询问 这个串可以旋转(就是把最后一位丢到最前面这样子) 问这个串以及其旋转的串在给定的串中出现了多少次 Sol 旋转就把它复制一遍接在后面 然后就在\ ...
-
【CodeForces - 235C】Cyclical Quest 【后缀自动机】
题意 给出一个字符串s1和q个询问,每个询问给出一个字符串s2,问这个询问的字符串的所有不同的周期串在s1中出现的次数的和. 分析 对于s1建后缀自动机.对于询问的每个字符串s2,我们按照处理循环串的 ...
-
Cyclical Quest CodeForces - 235C (后缀自动机)
Cyclical Quest \[ Time Limit: 3000 ms\quad Memory Limit: 524288 kB \] 题意 给出一个字符串为 \(s\) 串,接下来 \(T\) ...
-
Cyclical Quest CodeForces - 235C 后缀自动机
题意: 给出一个字符串,给出一些子串,问每个子串分别在母串中圆环匹配的次数, 圆环匹配的意思是将该子串拆成两段再首位交换相接的串和母串匹配,比 如aaab变成baaa,abaa,aaba再进行匹配. ...
随机推荐
-
【转】php json_encode中文为空的解决办法
转自:http://www.cnblogs.com/oldphper/p/4123415.html 本文列举3个方法,实现json_encode()后的string显示中文问题. 做接口时不需要,但存 ...
-
Setfocus - IE 需要使用setTimeout
setTimeout(function () { $('#controlid').focus(); }, 100); document.getElementById('filterPopupInput ...
-
ubuntu下编译源码级QT
注意必须好好看官方文档: http://qt-project.org/doc/qt-5/linux.html 包括编译Qt库依赖的包等等. 编译过程中发现以下错误: All the OpenGL fu ...
-
SGU 106 The Equation 扩展欧几里得应用
Sol:线性不定方程+不等式求解 证明的去搜下别人的证明就好了...数学题. #include <algorithm> #include <cstdio> #include & ...
-
JavaScript继承基础讲解,原型链、借用构造函数、混合模式、原型式继承、寄生式继承、寄生组合式继承
说好的讲解JavaScript继承,可是迟迟到现在讲解.废话不多说,直接进入正题. 既然你想了解继承,证明你对JavaScript面向对象已经有一定的了解,如还有什么不理解的可以参考<面向对象J ...
-
Clojure新手入门
官方网站 clojure.org 环境安装 Java(JDK) Leiningen 编辑工具 Eclipse插件 -- Counterclockwise IntelliJ插件 -- Cursive E ...
-
jQuery基础(鼠标事件,表单事件,键盘事件,自定义事件 篇)
1.jQuery鼠标事件之click与dbclick事件 方法一:$ele.click()(不带参数) <div id="test">点击触发<div&g ...
-
Android的onCreateOptionsMenu()创建菜单Menu
android一共有三种形式的菜单: 1.选项菜单(optinosMenu) 2.上下文菜单(ContextMenu) 3.子菜 ...
-
查T结果与Z结果的P值[转载]
T检验P值表格来自:https://blog.csdn.net/m0_37777649/article/details/74937242 Z检验表格来自:https://wenku.baidu.com ...
-
4gcc编译器
gcc编译器(GNU C Compiler) 现在我们所说的 gcc 是 GUN Compiler Collection的缩写,可以支持多种语言编译,比如 C,C++,Java, pascal 等 g ...