CTSC2012 熟悉的文章 广义后缀自动机_单调队列
2024-08-21 15:14:40
没啥难的,主要是单调队列忘了咋求了QAQ...
Code:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 2200000+10
#define N 2
using namespace std;
char str[maxn],ss[maxn];
int str_len,ss_len,n,m,que[maxn];
int tot,last,dis[maxn],f[maxn],ch[maxn][N],mx[maxn],F[maxn];
void init(){last=tot=1; }
void ins(int c){
int p=last,np=++tot; last=np,dis[np]=dis[p]+1;
while(p&&!ch[p][c]) ch[p][c]=np,p=f[p];
if(!p) f[np]=1;
else {
int q=ch[p][c];
if(dis[q]==dis[p]+1) f[np]=q;
else{
int nq=++tot;
dis[nq]=dis[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
f[nq]=f[q],f[np]=f[q]=nq;
while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p];
}
}
} int check(int len){
int hd=1,tl=0;
for(int i=1;i<=len;++i) F[i]=0;
for(int i=len;i<=str_len;++i) {
int j=i-len;
while(hd <=tl && F[que[tl]]-que[tl]<=F[j]-j) --tl;
que[++tl]=j;
while(hd<=tl&&que[hd]<i-mx[i]) ++hd;
if(hd>tl) F[i]=F[i-1];
else F[i]=max(F[i-1],F[que[hd]]+i-que[hd]);
}
if(10*F[str_len]>=9*str_len) return 1;
return 0;
}
void solve(){
scanf("%s",str+1),str_len=strlen(str+1);
int p=1,cur=0;
for(int i=1;i<=str_len;++i) {
int c=str[i]-'0';
while(p && !ch[p][c]) p=f[p],cur=dis[p];
if(!p) {p=1,cur=0;}
else p=ch[p][c],cur+=1;
mx[i]=cur;
}
int l=1,r=str_len,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) { ans=mid,l=mid+1; }
else r=mid-1;
}
printf("%d\n",ans);
}
int main(){
//setIO("input");
scanf("%d%d",&n,&m),init();
for(int i=1;i<=m;++i)
{
scanf("%s",ss+1),ss_len=strlen(ss+1),last=1;
for(int j=1;j<=ss_len;++j) ins(ss[j]-'0');
}
for(int i=1;i<=n;++i) solve();
return 0;
}
最新文章
- CI框架3
- JavaScript Date 对象
- Redis自定义动态字符串(sds)模块(一)
- POJ-2726-Holiday Hotel
- A Framework for Programme Management
- Oracle分析函数的项目实践实例
- MSP430的看门狗常见用法以及中断函数的书写方法
- 专访雷水果国:离1.5K至18K 一个程序猿5每年的成长之路
- 通过jquery来实现文本框和下拉框动态添加效果,能根据自己的需求来自定义最多允许添加数量,实用的jquery动态添加文本框特效
- JS学习三(函数)
- oracle赋值问题(将同一表中某一字段赋值给另外一个字段的语句)
- python笔记:#013#高级变量类型
- Linux系统下zookeeper的安装和配置
- baiduMap &; MapV 简单demo
- [转]CentOS7利用systemctl添加自定义系统服务
- 如何将字符串格式的对象转换成真正的js对象?
- 大数据系列之分布式计算批处理引擎MapReduce实践-排序
- iOS 11 使用方法替换(Method Swizzling),去掉导航栏返回按钮的文字
- 最新JAVA编程题全集(50题及答案)
- 工业标准接口OPC Server