cogs1709. [SPOJ 705] 不同的子串(后缀数组
2024-09-01 06:28:35
http://cogs.pro:8080/cogs/problem/problem.php?pid=vyziQkWaP
题意:给定一个字符串,计算其不同的子串个数。
思路:ans=总共子串个数-相同的个数,相同个数就是height[]之和,总共字串个数是。。
长度为1:len,长度为2:len-1...总共(len*(len-1))/2
#include<bits/stdc++.h>
using namespace std;
#define MAXN 50010
#define LL long long
int Ws[MAXN],sa[MAXN],wa[MAXN],wb[MAXN],wv[MAXN],Rank[MAXN],height[MAXN];
char str[MAXN];
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&&(r[a+l]==r[b+l]);}
void DA(char *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++)Ws[i]=0;
for(i=0;i<n;i++)Ws[x[i]=r[i]]++;
for(i=0;i<m;i++)Ws[i]+=Ws[i-1];
for(i=n-1;i>=0;i--)sa[--Ws[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=0;i<n;i++)wv[i]=x[y[i]];
for(i=0;i<m;i++)Ws[i]=0;
for(i=0;i<n;i++)Ws[wv[i]]++;
for(i=0;i<m;i++)Ws[i]+=Ws[i-1];
for(i=n-1;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<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void calheight(int n)
{
int i,j,k=0;
for(i=1;i<=n;i++)Rank[sa[i]]=i;
for(i=0;i<n;height[Rank[i++]]=k)
for(k?k--:0,j=sa[Rank[i]-1];str[i+k]==str[j+k];k++);
}
int main()
{
freopen("subst1.in","r",stdin);
freopen("subst1.out","w",stdout);
int lstr,i;
LL ans=0;
scanf("%s",str);
lstr=strlen(str);
str[lstr+1]=0;
DA(str,sa,lstr+1,256);
calheight(lstr);
ans=((LL)(lstr+1)*lstr)/2;
for(i=2;i<=lstr;i++)ans-=(LL)height[i];
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
最新文章
- (译)JavaScript内存泄露
- S5P4418 uboot 分析
- android 点滴记录 ICCID IMSI IMEI MEID 关系 和 区别,相关参数在什么情况下可以获取...
- 鸟哥的Linux私房菜学习笔记(1)
- POJ 1011 sticks 搜索
- Publisher/Subscriber 订阅-发布模式
- Educational Codeforces Round 17F Tree nesting
- html5中新增的元素和废除的元素
- 夜神模拟器调试web APP
- Git常用的操作
- 2018 CCPC网络赛 几道数学题
- IAR project build with command line
- Day3 /2-4.10!一天水完毕设,焦虑略减,flag不能倒!
- js创建并下载文件
- IDEA 在使用的过程中字符间距变大的问题
- Azure SQL Database (26) 使用Query Store对Azure SQL Database监控
- maven install 打包 报错 Cannot run program ";gpg.exe";: CreateProcess error
- 用 Vue 改造 Bootstrap,渐进提升项目框架[转]
- 使用rewrite 让php 实现类似asp.net 的IHttpModule 进行带参数js文件的参数获取
- paxos ---学习笔记
热门文章
- Mysql优化(出自官方文档) - 第五篇
- 提交bug的标准及书写规范
- HashMap、Hash Table、ConcurrentHashMap
- 有容云-PPT | 当微服务遇见容器
- oracle 正确删除归档日志,并清除 V$ARCHIVED_LOG 数据
- 论文阅读 | Falcon: Balancing Interactive Latency and Resolution Sensitivity for Scalable Linked Visualizations
- 一个基于TCP/IP的服务器与客户端通讯的小项目(超详细版)
- 【POJ - 2431】Expedition(优先队列)
- Netty学习(四)-TCP粘包和拆包
- Linux文件及目录管理