并不对劲的bzoj3277
2024-10-07 21:01:12
陈年老坑
题意大概是有n个字符串,要求出每一个字符串的所有子串(不包括空串)在所有字符串(包括自身)中出现次数不少于k的有多少个。n,k,字符串总长<=100000。
如果只有一个串的话,非常好办,直接把它建成后缀自动机就行了。
那么不止一个串该怎么办呢?想必是也可以用后缀自动机解决的。这时就要建出一棵Trie树的后缀自动机。
这就是广义呕吐之光后缀自动机
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define maxn 200005
using namespace std;
int n,k;
long long c[maxn];
long long ans[maxn];
struct data {
long long son[maxn][26],link[maxn],step[maxn],last,cnt,t[maxn],size[maxn],tp[maxn];
data() {last=cnt=1;}
void extend(int x,int id) {
int p=last,np=last=++cnt;step[np]=step[p]+1;t[np]=id;
while(p&&!son[p][x]) son[p][x]=np,p=link[p];
if(!p) link[np]=1;
else {
int q=son[p][x];
if(step[q]==step[p]+1) link[np]=q;
else {
int nq=++cnt;
memcpy(son[nq],son[q],sizeof(son[q]));
step[nq]=step[p]+1;
link[nq]=link[q];link[np]=link[q]=nq;size[nq]=size[q];tp[nq]=tp[q];
while(p&&son[p][x]==q) son[p][x]=nq,p=link[p];
}
}
for(int i=np;i&&tp[i]!=id;i=link[i]) size[i]++,tp[i]=id;
}
}sam;
int head[maxn],sum;
struct edge {
int to,next;
}e[maxn];
void add(int u,int v) {e[sum].to=v;e[sum].next=head[u];head[u]=sum++;}
char s[maxn];
void dfs(int x) {
c[x]+=c[sam.link[x]];ans[sam.t[x]]+=c[x];
for(int i=head[x];i>=0;i=e[i].next) dfs(e[i].to);
}
int main() {
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
scanf("%s",s+1);
int len=strlen(s+1);sam.last=1;
for(int j=1;j<=len;j++) sam.extend(s[j]-'a',i);
}
for(int i=2;i<=sam.cnt;i++) {
add(sam.link[i],i);
if(sam.size[i]>=k) c[i]=sam.step[i]-sam.step[sam.link[i]];
}
dfs(1);
for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
}
/*
3 2
abaac
bba
bbacb
*/
宣传一波电教XX,欢迎加入。
最新文章
- STM32的入侵检测是干什么用的
- JSP入门
- SQL Server 2008 存储过程,带事务的存储过程(创建存储过程,删除存储过程,修改存储过
- HDU 2007
- Python安装pandas
- 【HDU4632 Palindrome subsequence】区间dp
- 《Linux内核分析》第七周 读书笔记
- Spring-事物传播行为
- Zend Studio 错误集锦[PHP]
- linux的命令(1)
- codeforces 601A The Two Routes(最短路 flody)
- 判断脚本,图片,CSS,iframe等是否加载完成
- Redis - 发布/订阅模式
- crontab 基本用法
- HTTP常见的状态码
- python3-day1(基础总结)
- 解决window.navigator.geolocation.getCurrentPosition在IOS10系统中无法进行地理定位问题
- akoj-1148-小光棍数
- Oracle最新的Sql笔试题及答案
- Python全栈开发记录_第七篇(模块_time_datetime_random_os_sys_hashlib_logging_configparser_re)
热门文章
- Laya 项目解耦
- asp.net mvc数据验证
- hdu6215 Brute Force Sorting(模拟)
- java的异常与记录日志
- 洛谷 P1731 [NOI1999]生日蛋糕
- Mac BOOK PRO U盘安装windows7、8及8.1
- Java实现拖拽上传
- Hadoop在window上运行 user=Administrator, access=WRITE, inode=";hadoop";
- Visual Studio VS如何卸载Visual assistant
- Hashmap在JDK8中的提升