博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu_3518_Boring counting(后缀数组)
阅读量:4879 次
发布时间:2019-06-11

本文共 1236 字,大约阅读时间需要 4 分钟。

题目链接:

题意:

给你一个字符串,让你找不重叠且出现大于1次以上的字串个数

题解:

后缀数组height数组的应用,我们枚举字串的长度,然后将height数组分段,符合条件就ans++

为什么要这样做,因为height数组存的是相邻排名后缀的最大前缀数,如果height的值大于等于我们枚举的长度len,

那么有可能这一段存在有两个以上的该长度的字串,然后我们统计这个段的开头长度l和结束长度r,如果r-l>=len,说明这段必有

大于一个以上的该长度的相同子串,因为我们每次都是枚举len,按len分的段,所以不会重复。

1 #include
2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 namespace suffixarray{ 6 #define FN(n) for(int i=0;i
=0;i--)sa[--c[x[i]]]=i;12 for(int k=1,p;p=0,k<=n;k=p>=n?N:k<<1,m=p){13 for(int i=n-k;i
=k)y[p++]=sa[i]-k;15 FN(m)c[i]=0;FN(n)c[x[y[i]]]++;FN(m)c[i+1]+=c[i];16 for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];17 swap(x,y),p=1,x[sa[0]]=0;18 for(int i=1;i
b)a=b;}28 inline void upu(int &a,int b){
if(a
=i)upd(l,sa[j]),upu(r,sa[j]);43 else44 {45 if(r-l>=i)ans++;46 l=r=sa[j];47 }48 }49 if(r-l>=i)ans++;50 }51 printf("%d\n",ans);52 }53 return 0;54 }
View Code

 

转载于:https://www.cnblogs.com/bin-gege/p/5744647.html

你可能感兴趣的文章
统计学习-朴素贝叶斯法
查看>>
学习进度17
查看>>
编译原理——算符优先分析文法(附源代码)
查看>>
jboss的启动过程
查看>>
渲染部分
查看>>
力扣——所有可能的路径
查看>>
关于VS项目平台的x86,x64,Any CPU以及Debug和Release的区别
查看>>
解密module_init幕后的故事
查看>>
9个移动网站优化的最佳实践
查看>>
李昌镐:苍老的青春(转载) 韩国围棋职业棋手
查看>>
JPA 使用报Named query not found错误
查看>>
FTP命令使用详解
查看>>
walmart weekly sales
查看>>
面试题07_用两个栈实现队列——剑指offer系列
查看>>
cocos2d-x3.2中加入Android手机震动
查看>>
css3处理sprite背景图压缩来解决H5网页在手机浏览器下图标模糊的问题
查看>>
温故而知新练习3
查看>>
【转】iOS应用崩溃日志分析
查看>>
EtherCAT Slave 入门教程 - 邮箱服务(1)
查看>>
java基础------抽象类
查看>>