HDU 6194 string string string(后缀自动机)
2024-08-25 12:13:43
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3238
【题目大意】
给出一个字符串求其出现恰好k次的子串数量
【题解】
对串建立AC自动机,所有right值为k的节点的value值的和就是答案
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=200010;
char s[N];
struct SAM{
int p,q,np,nq,cnt,lst,a[N][26],l[N],f[N],tot;
int Tr(char c){return c-'a';}
int val(int c){return l[c]-l[f[c]];}
SAM(){cnt=0;lst=++cnt;}
void Initialize(){
memset(l,0,sizeof(int)*(cnt+1));
memset(f,0,sizeof(int)*(cnt+1));
for(int i=0;i<=cnt;i++)for(int j=0;j<26;j++)a[i][j]=0;
cnt=0;lst=++cnt;
}
void extend(int c){
p=lst;np=lst=++cnt;l[np]=l[p]+1;
while(!a[p][c]&&p)a[p][c]=np,p=f[p];
if(!p){f[np]=1;}
else{
q=a[p][c];
if(l[p]+1==l[q])f[np]=q;
else{
nq=++cnt;l[nq]=l[p]+1;
memcpy(a[nq],a[q],sizeof(a[q]));
f[nq]=f[q]; f[np]=f[q]=nq;
while(a[p][c]==q)a[p][c]=nq,p=f[p];
}
}
}
int b[N],x[N],r[N];
void build(){
scanf("%s",s+1);
int len=strlen(s+1);
for(int i=1;i<=len;i++)extend(Tr(s[i]));
memset(r,0,sizeof(int)*(cnt+1));
memset(b,0,sizeof(int)*(cnt+1));
for(int i=1;i<=cnt;i++)b[l[i]]++;
for(int i=1;i<=len;i++)b[i]+=b[i-1];
for(int i=1;i<=cnt;i++)x[b[l[i]]--]=i;
for(int i=p=1;i<=len;i++){p=a[p][Tr(s[i])];r[p]++;}
for(int i=cnt;i;i--)r[f[x[i]]]+=r[x[i]];
}
void solve(){
int ans=0,k;
scanf("%d",&k);
build();
for(int i=1;i<=cnt;i++)if(r[x[i]]==k)ans+=val(x[i]);
printf("%d\n",ans);
}
}sam;
int T;
int main(){
scanf("%d",&T);
while(T--){
sam.Initialize();
sam.solve();
}return 0;
}
最新文章
- Linux学习笔记(17) Shell编程之基础
- ArcGIS中添加进自定义的ttf字符标记符号
- 网页数据采集 - 系列之Flash数据采集
- 分布式文件系统 - FastDFS
- 向Oracle中插入记录时,出现“Oracle.DataAccess.Client.OracleException ORA-00933 ”错误
- sql server触发器的例子
- FolderBrowserDialog(文件夹浏览对话框)
- Node.js初级
- Android4.3 蓝牙BLE初步
- 【Xamarin挖墙脚系列:时刻下载最新的Mac环境下的Xamarin安装包】
- mac中Eclipse的快捷键
- Git 初学
- ionic笔记
- Java8 新特性 | 如何风骚走位防止空指针异常
- NoSQL入门
- Original Autel MaxiSys Pro MS908P support 2 Year Free Update Online
- php把网络图片转Base64编码。
- 总结下Mysql分表分库的策略及应用
- Java并发程序设计(一) 基础概念
- zookeeper之 zkServer.sh命令、zkCli.sh命令、四字命令
热门文章
- 工具推荐:ATSCAN,功能强大的Perl脚本扫描器
- weight decay(权值衰减)、momentum(冲量)和normalization
- python时序数据分析--以示例说明
- pip安装遇到问题
- mysql命令gruop by报错this is incompatible with sql_mode=only_full_group_by
- jQuery之字体大小的设置
- 深度解析eclipse控制台
- UFLDL 教程学习笔记(三)
- 使用Appium 测试微信小程序和微信公众号方法
- Kafka ACL使用实战(单机版)