博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
后缀数组 --- HDU 3518 Boring counting
阅读量:5758 次
发布时间:2019-06-18

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

 Boring counting

Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=3518


 

Mean: 

给你一个字符串,求:至少出现了两次(无重叠)的子串的种类数。

analyse:

后缀数组中height数组的运用,一般这个数组用得很少。

总体思路:分组统计的思想:将相同前缀的后缀分在一个组,然后对于1到len/2的每一个固定长度进行统计ans。

首先我们先求一遍后缀数组,并把height数组求出来。height数组代表的含义是:字典序相邻(即rank数组相邻)的两个后缀的最长公共前缀的长度。

由于子串不能重叠,那么就可以确定出子串长度的取值范围:1~len/2。(维护sa[]的最大值和最小值是为了判断排名相邻两个字符串的距离是否大于k,只有大于k才能保证不重叠)。

接下来我们对1~len/2的每一个固定长度进行统计该长度的子串有多少种,一路累加即得答案。

关键是要理解使用height数组进行分组统计的过程。

Time complexity: O(nlogn)

 

Source code: 

/** this code is made by crazyacking* Verdict: Accepted* Submission Date: 2015-05-09-21.22* Time: 0MS* Memory: 137KB*/#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long#define ULL unsigned long longusing namespace std;const int MAXN=1010;//以下为倍增算法求后缀数组int wa[MAXN],wb[MAXN],wv[MAXN],Ws[MAXN];int cmp(int *r,int a,int b,int l){ return r[a]==r[b]&&r[a+l]==r[b+l];}void da(const char *r,int *sa,int n,int m) //{ int i,j,p,*x=wa,*y=wb,*t; for(i=0;i
=0;i--) sa[--Ws[x[i]]]=i; for(j=1,p=1;p
=j) y[p++]=sa[i]-j; for(i=0;i
=0;i--) sa[--Ws[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i
=k) maxx=max(maxx,max(sa[i-1],sa[i])),minn=min(minn,min(sa[i-1],sa[i])); else { if(maxx-minn>=k) ans++; maxx=0,minn=INT_MAX; } } if(maxx-minn>=k)ans++; return ans;}int main(){ while(~scanf("%s",str) && strcmp(str,"#")!=0) { int len=strlen(str); /**< 传入参数:str,sa,len+1,ASCII_MAX+1 */ da(str,sa,len+1,130); /**< str,sa,len */ calheight(str,sa,len); LL ans=0; for(int i=1;i<=len/2;++i) ans+=solve(i,len); cout<
<
View Code

 

转载地址:http://xepkx.baihongyu.com/

你可能感兴趣的文章
openstack
查看>>
线程进程间通信机制
查看>>
galera mysql 多主复制启动顺序及命令
查看>>
Glibc辅助运行库 (C RunTime Library): crt0.o,crt1.o,crti.o crtn.o,crtbegin.o crtend.o
查看>>
毛玻璃效果
查看>>
mysql常用命令
查看>>
郑捷《机器学习算法原理与编程实践》学习笔记(第七章 预测技术与哲学)7.1 线性系统的预测...
查看>>
Partial Sum
查看>>
JS prototype 属性
查看>>
中位数性质——数列各个数到中位数的距离和最小
查看>>
排序算法 & 迷宫的深度, 广度优先
查看>>
eclipse里报:An internal error occurred during: "Building workspace". Java heap space(内存溢出)...
查看>>
51Nod 1091:线段的重叠(贪心)
查看>>
《将博客搬至CSDN》
查看>>
五大常用算法之四:回溯法
查看>>
Niagara物联网框架机制一(笔记)
查看>>
Sonar rule for multithread
查看>>
AC自动机学习笔记
查看>>
NO27 定时任务
查看>>
使用 try-catch
查看>>