【文文殿下】[51nod1469] 淋漓尽致子串

时间:2023-01-04 11:40:44

SAM的经典应用

一个状态的SIze==1绝对不合法。

一个状态在parent树上有一个Size>1的后继绝对不合法(前面可以再补字符)

一个状态可以转移到Size>1的节点绝对不合法,因为可以在后面补字符。

#include<cstdio>
#include<cstring>
#include<map>
typedef long long ll;
const int maxn = 2e5+20;
int par[maxn],mx[maxn],tr[maxn][26],Right[maxn],c[maxn],id[maxn];
char A[maxn>>1];
int tot=0;
int cnt = 1,last = 1;
ll ans = 0;
void extend(int x) {
int np = ++cnt,p = last;
Right[np]=1;
mx[np]=mx[p]+1;
last=np;
while(p&&!tr[p][x]) tr[p][x]=np,p=par[p];
if(!p) par[np]=1;
else {
int q = tr[p][x];
if(mx[q]==mx[p]+1) {
par[np]=q;
}
else {
int nq = ++cnt;
mx[nq]=mx[p]+1;
memcpy(tr[nq],tr[q],sizeof tr[nq]);
par[nq]=par[q];
par[q]=par[np]=nq;
while(p&&tr[p][x]==q) tr[p][x]=nq,p=par[p];
}
}
return;
}
int n,k,t;
inline void topsort() {
for(int i = 1;i<=cnt;++i) ++c[mx[i]];
for(int i = 1;i<=n;++i) c[i]+=c[i-1];
for(int i = 1;i<=cnt;++i) id[c[mx[i]]--]=i;
for(int i = cnt;i;--i) Right[par[id[i]]]+=Right[id[i]];
return;
}
bool vis[maxn];
int main() {
scanf("%s",A+1);
n = strlen(A+1);
for(int i = 1;i<=n;++i) extend(A[i]-'a');
topsort();Right[0]=0;
for(int i =cnt;i;--i) {
if(Right[id[i]]>1||vis[id[i]]) vis[par[id[i]]]=1;
}
for(int i = 1;i<=cnt;++i) if(Right[i]<=1) vis[i]=1;
for(int i = 1;i<=cnt;++i) for(int j = 0;j<26;++j) if(Right[tr[i][j]]>1) vis[i]=1;
for(int i = 2;i<=cnt;++i) if(!vis[i]) ++ans;
printf("%lld\n",ans);
return 0;
}

【文文殿下】[51nod1469] 淋漓尽致子串的更多相关文章

  1. 【文文殿下】洛谷P2408 不同子串个数

    题目链接https://www.luogu.org/problemnew/show/P2408 SAM裸题,大力求就行了 #include<cstdio> #include<cstr ...

  2. 【文文殿下】后缀自动机&lpar;SAM&rpar;求最长公共子串的方法

    首先,在A 串上建立一个SAM,然后用B串在上面跑.具体跑的方法是: 从根节点开始,建立一个指针 p ,指着B串的开头,同步移动指针,沿着SAM的边移动,如果可以移动(即存在边)那么万事皆好,直接le ...

  3. 【文文殿下】WC2019游记

    Day0 今天早上三点半才睡着,五点起床,前往省城郑州.与省实验常老师汇合,坐上高铁,下午三点半多才到广州二中. 下午随便找了一个教室进去敲一敲代码,发现自己越来越菜了. 和一大堆网上的dalao面基 ...

  4. 【文文殿下】NOIp2018游记

    Day-1 本段更新于 2018年11月8日23:26:44 今天还在机房里面,无所事事吧.上午睡了一上午,出去理了一下发,花了20块钱 QAQ. 下午来到机房,复习了一下exgcd的东西. 发现自己 ...

  5. 【文文殿下】【CF724C】Ray Tracing &lpar;中国剩余定理)

    题解 我们考虑将棋盘扩大一倍,这样相当于取膜.然后,我们只要对x,y,的位置分类讨论,做四次crt就行.具体细节看文文代码. #include<cstdio> #include<al ...

  6. 【文文殿下】后缀自动机&lpar;Suffix Automaton&comma;SAM&rpar;学习笔记

    前言 后缀自动机是一个强大的数据结构,能够解决很多字符串相关的(String-related)问题. 例如:他可以查询一个字符串在另一个字符串中出现的所有子串,以及查询一个字符串中本质不同的字符串的个 ...

  7. 【文文殿下】&lbrack;BZOJ3277&rsqb; 串

    Description 字符串是oi界常考的问题.现在给定你n个字符串,询问每个字符串有多少子串(不包括空串)是所有n个字符串中 至少k个字符串的子串(注意包括本身) Input 第一行两个整数n,k ...

  8. 【文文殿下】 &lbrack;SDOI2016&rsqb;生成魔咒

    字符集大小为1e9.............使用 map 吧 统计本质不同的子串个数是SAM的经典应用之一 本质不同的子串个数其实就是\(\sum max(x)-min(x)+1\) 所以我们新建结点 ...

  9. &lbrack;文文殿下&rsqb;基本的DP技巧

    . 二进制状态压缩动态规划 对于某些情况,如果题目中所给的限制数目比较小,我们可以尝试状态压缩动态规划.例如,题目中给出数据范围\(n<=20\),这个一般情况下是一个状压DP的提示. 状态压缩 ...

随机推荐

  1. Oracle -&gt&semi;&gt&semi; 连续聚合

    select id, grp_factor, sum (id) over( partition by grp_factor order by id rows between unbounded pre ...

  2. BPDU与PortFast

    启用了BPDU Guard特性的端口在收到BPDU的时候会使端口进入err-disable状态,从而避免桥接环路.一般BPDU Guard是和PortFast结合使用,在端口上启用了PortFast之 ...

  3. CSS样式----浮动(图文详解)

    标准文档流 宏观地讲,我们的web页面和photoshop等设计软件有本质的区别:web页面的制作,是个"流",必须从上而下,像"织毛衣".而设计软件,想往哪里 ...

  4. Kafka基本知识回顾及复制

    Producers发布记录到集群,集群维护这些记录并且将记录分发给Consumers. 在Kafka中,最关键的抽象是topic.Producers发布记录到一个topic,Consumers订阅一个 ...

  5. 使用Spring Aop自定义注解实现自动记录日志

    百度加自己琢磨,以下亲测有效,所以写下来记录,也方便自己回顾浏览加深印象之类,有什么问题可以评论一起解决,不完整之处也请大佬指正,一起进步哈哈(1)首先配置文件: <!-- 声明自动为sprin ...

  6. linux下可执行bin程序提示not found&sol;no such file or directory&sol;not executable

    我们经常在执行二进制bin程序时,会遇到提示not found/no such file or directory/not executable等错误信息,在什么情况下会出现这种问题呢,我们一起罗列下 ...

  7. Python 数据结构与算法—— 快排

    1. 先从待排序的数组中找出一个数作为基准数(取第一个数即可),然后将原来的数组划分成两部分:小于基准数的左子数组和大于等于基准数的右子数组.然后对这两个子数组再递归重复上述过程,直到两个子数组的所有 ...

  8. PS合成以及分解GIF

    http://jingyan.baidu.com/article/3052f5a1c91f0497f31f862a.html 百度上的这个说明很详细了 这里就简单注明一下: PS 时间轴:用来创建动画 ...

  9. 解决PHP在Windows IIS 上传的图片无法访问的问题

    最近在做一个网站项目遇到了一个很奇怪的问题,现记录下来希望可以帮助到其他的朋友   问题描述: 最近公司刚刚在香港购买了一个Windows Server 2008 服务器用于将一个客户的N个php网站 ...

  10. 深度可分离卷积结构(depthwise separable convolution)计算复杂度分析

    https://zhuanlan.zhihu.com/p/28186857 这个例子说明了什么叫做空间可分离卷积,这种方法并不应用在深度学习中,只是用来帮你理解这种结构. 在神经网络中,我们通常会使用 ...