[TyvjP1515] 子串统计 [luoguP2408] 不同子串个数(后缀数组)
2024-08-27 16:17:28
经典题
统计一个字符串中不同子串的个数
一个字符串中的所有子串就是所有后缀的前缀
先求出后缀数组,求出后缀数组中相邻两后缀的 lcp
那么按照后缀数组中的顺序遍历求解
每一个后缀 suffix(sa[i]) 对于答案的贡献为 len - sa[i] - height[i]
len - sa[i] 为当前后缀的长度,也就是当前后缀所有前缀的个数(字符串从 0 开始)
height[i] 就是相邻两后缀 lcp,因为有可能会有相同前缀,而相同前缀在前面已经计算过了
为什么只需要 height 数组,而不用把任意两后缀的 lcp 求出来呢?
因为所有后缀已经按照字典序排序了,也就是说,sa[i] 和 sa[i - 1] 的 lcp 即为 sa[i] 和 sa[0 ~ i - 1] 的所有 lcp 的最大值。
——代码(Tyvj)
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 200001
#define LL long long LL ans;
int len, m = ;
int buc[N], x[N], y[N], sa[N], rank[N], height[N];
char s[N]; inline void build_sa()
{
int i, k, p;
for(i = ; i < m; i++) buc[i] = ;
for(i = ; i < len; i++) buc[x[i] = s[i]]++;
for(i = ; i < m; i++) buc[i] += buc[i - ];
for(i = len - ; i >= ; i--) sa[--buc[x[i]]] = i;
for(k = ; k <= len; k <<= )
{
p = ;
for(i = len - ; i >= len - k; i--) y[p++] = i;
for(i = ; i < len; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(i = ; i < m; i++) buc[i] = ;
for(i = ; i < len; i++) buc[x[y[i]]]++;
for(i = ; i < m; i++) buc[i] += buc[i - ];
for(i = len - ; i >= ; i--) sa[--buc[x[y[i]]]] = y[i];
std::swap(x, y);
p = , x[sa[]] = ;
for(i = ; i < len; i++)
x[sa[i]] = y[sa[i - ]] == y[sa[i]] && y[sa[i - ] + k] == y[sa[i] + k] ? p - : p++;
if(p >= len) break;
m = p;
}
} inline void build_height()
{
int i, j, k = ;
for(i = ; i < len; i++) rank[sa[i]] = i;
for(i = ; i < len; i++)
{
if(!rank[i]) continue;
if(k) k--;
j = sa[rank[i] - ];
while(s[i + k] == s[j + k] && i + k < len && j + k < len) k++;
height[rank[i]] = k;
}
} int main()
{
int i;
scanf("%d", &len);
getchar();
for(i = ; i < len; i++)
{
s[i] = getchar();
if((i + ) % == ) getchar();
}
build_sa();
build_height();
for(i = ; i < len; i++) ans += (LL)(len - sa[i] - height[i]);
printf("%lld\n", ans);
return ;
}
洛谷那题好像数据有点问题。
最新文章
- Sharepoint学习笔记—习题系列--70-576习题解析 -(Q69-Q71)
- Java 中的转义字符
- centos 安装flash插件
- intellij idea 如何更改编辑器文本字体和大小
- [ios][opengles]opengles纹理贴图
- HDU5829 NTT
- [JSOI2008] 完美的对称
- Jenkins+Maven+Git CI环境搭建手册
- 【转】2D动画:view的Matrix
- 理解RunLoop
- Django 1.10中文文档—第一个Django应用Part1
- 对获取config文件的appSettings节点简单封装
- PHP正则提取HTML中img的url值
- 让Java的反射跑快点
- C#获取本地磁盘信息【转载】
- JAVA 8 主要新特性 ----------------(五)Lambda方法引用与构造器引用
- mysql插入报主键冲突,解决方法主键索引重新排序
- (转)VS2010反编译dll之后存在的resource修改为resx
- python(leetcode)-350两个数组的交集
- 通用漏洞评估方法CVSS3.0简表