CF873F Forbidden Indices 后缀自动机+水题
2024-09-02 22:03:19
刷刷水~
Code:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200005
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str1[N],str2[N];
int tot,last,n,c[N<<1],rk[N<<1];
struct Node
{
int ch[26],f,len,cnt;
}t[N<<1];
void extend(int c,int flag)
{
int np=++tot,p=last;
last=np,t[np].len=t[p].len+1;
for(;p&&!t[p].ch[c];p=t[p].f) t[p].ch[c]=np;
if(!p) t[np].f=1;
else
{
int q=t[p].ch[c];
if(t[q].len==t[p].len+1) t[np].f=q;
else
{
int nq=++tot;
t[nq].len=t[p].len+1;
t[nq].f=t[q].f,t[q].f=t[np].f=nq;
memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch));
for(;p&&t[p].ch[c]==q;p=t[p].f) t[p].ch[c]=nq;
}
}
t[np].cnt=flag;
}
int main()
{
int i,j;
long long answer=0;
// setIO("input");
scanf("%d%s%s",&n,str1+1,str2+1);
for(last=tot=i=1;i<=n;++i) extend(str1[i]-'a',str2[i]=='0'?1:0);
for(i=1;i<=tot;++i) ++c[t[i].len];
for(i=1;i<=tot;++i) c[i]+=c[i-1];
for(i=1;i<=tot;++i) rk[c[t[i].len]--]=i;
for(i=tot;i>=1;--i)
{
int p,ff;
p=rk[i],ff=t[p].f;
answer=max(answer,(long long)t[p].len*t[p].cnt);
t[ff].cnt+=t[p].cnt;
}
printf("%lld\n",answer);
return 0;
}
最新文章
- [Hadoop in Action] 第2章 初识Hadoop
- Python 面向对象 中高级
- sql常见的面试题
- 在服务器端将XML转换成HTML
- 每日Scrum--No.4
- ubuntu更换源后报错:W: GPG error: (转载)
- HDU 5638 Toposort 线段树+贪心
- windows MySQL 5+ 服务手动安装
- PAT-013 L1-013. 计算阶乘和
- Android开发技巧——自定义控件之增加状态
- Bootstrap -- 插件: 按钮状态、折叠样式、轮播样式
- 第八届 蓝桥杯 7、正则问题 dfs
- C++ Opencv Mat类型使用的几个注意事项及自写函数实现Laplace图像锐化
- Python 简单soket例子
- undo空间满的处理方法(含undo的学习与相关解释)
- Ubuntu 之 atom 安装以及 常用配置
- 11: python中的轻量级定时任务调度库:schedule
- 文件系统--fs(读)--fs.read
- 强化学习中的无模型 基于值函数的 Q-Learning 和 Sarsa 学习
- JAVA WEB ------ 文件下载及导出数据到office Execl表格
热门文章
- Elasticsearch-如何控制存储和索引文档(_source、_all、返回源文档的某些字段)
- [xpath] 定位中starts-with、contains和text()的用法
- Python学习【day04】- Python基础(集合、函数)
- linux yum安装过程终止方法
- Java 条件语句 if else
- 解决:IDE编译报错:Dangling metacharacter
- 虚拟机无法启动,提示:无法打开内核功能扩展“com.vmware.kext.vmci”: 无此文件或目录
- ccs之经典布局(一)(水平垂直居中)
- JS通过sort(),和reverse()正序和倒序
- 数据库命令行工具USQL、mycli、litecli、pgcli