[bzoj2806][Ctsc2012]Cheat(后缀自动机(SAM)+二分答案+单调队列优化dp)
2024-09-04 23:27:01
偷懒直接把bzoj的网页内容ctrlcv过来了
2806: [Ctsc2012]Cheat
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 1943 Solved: 1004
[Submit][Status][Discuss]
Description
Input
第一行两个整数N,M表示待检查的作文数量,和小强的标准作文库
的行数
接下来M行的01串,表示标准作文库
接下来N行的01串,表示N篇作文
Output
N行,每行一个整数,表示这篇作文的Lo 值。
Sample Input
1 2
10110
000001110
1011001100
10110
000001110
1011001100
Sample Output
4
HINT
输入文件不超过1100000字节
注意:题目有改动,可识别的长度不小于90%即可,而不是大于90%
所谓少于$1.1*10^6$就是总输入字符数少于这个数...
果然CTSC出的题水平够高
专门爆踩SAM只学了板子不懂各个元素含义和应用的菜鸡(像我这样的就是了)
随便把模式串扔进广义SAM里
答案L0具有单调性
所以二分答案
接下来考虑$O(n)$求出最长匹配长度
$O(n)$的话...只能dp了啊
在SAM上跑字符串匹配求出每一位的最长向前匹配长度$f[i]$
用$dp[i]$表示到i位置匹配了多少字符
之后有dp方程
$dp[i]=max(dp[i-1],max(dp[j=(i-f[i]) to (i-L0)]+i-j))$
对于$dp[j]-j$,$O(n^2)$单调队列优化变成$O(n)$
本题完结
#include<cstdio> #include<cstring> #include<queue> using std::queue; ; char sin[N]; int nn,nm,n; template<typename tp>tp max(tp a,tp b){return a>b?a:b;} struct sam { ],len,pre; }s[N<<]; struct Sakuya_Brando { int size,fin; Sakuya_Brando(){size=;} void insert(int ch) { int npx,npy,lpx,lpy; if(s[fin].tranc[ch]) { lpx=fin,lpy=s[fin].tranc[ch]; ) fin=lpy; else { npy=++size; s[npy]=s[lpy]; s[npy].len=s[lpx].len+; s[lpy].pre=npy; while(s[lpx].tranc[ch]==lpy) { s[lpx].tranc[ch]=npy; lpx=s[lpx].pre; } fin=npy; } return; } npx=++size; s[npx].len=s[fin].len+; for(lpx=fin;lpx&&!s[lpx].tranc[ch];lpx=s[lpx].pre) s[lpx].tranc[ch]=npx; ; else { lpy=s[lpx].tranc[ch]; ) s[npx].pre=lpy; else { npy=++size; s[npy]=s[lpy]; s[npy].len=s[lpx].len+; s[lpy].pre=s[npx].pre=npy; while(s[lpx].tranc[ch]==lpy) { s[lpx].tranc[ch]=npy; lpx=s[lpx].pre; } } } fin=npx; } void ins(char *str,int len) { fin=; len=strlen(str); ;i<len;i++) insert(str[i]-'); } }sakuya; int f[N]; int dp[N]; struct stack { int v,id; stack(){} stack(int a,int b){v=a,id=b;} }sta[N]; int he,ta; void bao0(char *str,int len) { ,tmp=; ;i<len;i++) { '; if(s[px].tranc[ch]) tmp++,px=s[px].tranc[ch]; else { while(px&&!s[px].tranc[ch]) px=s[px].pre; ,px=; ,px=s[px].tranc[ch]; } f[i]=tmp; } } void noi(char *str,int len) { ;i<len;i++) f[i]=; } bool check(char *str,int ll,int len) { he=,ta=; ; ;j<len;i++,j++) { dp[i]=dp[i-]; while(he<=ta&&sta[he].id<i-f[j]) he++; while(he<=ta&&sta[ta].v<=dp[i-ll]-(i-ll)) ta--; sta[++ta]=stack(dp[i-ll]-(i-ll),i-ll); while(he<=ta&&sta[he].id<i-f[j]) he++; if(he<=ta) dp[i]=max(dp[i],i+sta[he].v); } mxx=dp[len]; ;i<=len;i++) dp[i]=; >=len*) ; ; } int main() { scanf("%d%d",&nn,&nm); ;i<=nm;i++) { scanf("%s",sin); n=strlen(sin); sakuya.ins(sin,n); } ;i<=nn;i++) { scanf("%s",sin); n=strlen(sin); bao0(sin,n); ,r0=n; while(l0<r0) { )>>; if(check(sin,mid,n)) l0=mid; ; } noi(sin,n); printf("%d\n",l0); } ; }
最新文章
- CSS基础篇之了解CSS和它的基本属性
- codevs1183 泥泞的道路
- unity panel删除drawcall失败导致的残留影像
- Web的形式发布静态文件
- 【莫比乌斯反演】关于Mobius反演与lcm的一些关系与问题简化(BZOJ 2154 crash的数字表格&;&;BZOJ 2693 jzptab)
- 【HDOJ】4210 Su-domino-ku
- Android -------- 网络访问数据
- 使用Java7提供Fork/Join框架
- [进程管理]Load和CPU利用率是如何算出来的
- centos 6安装 H3C iNode 上网客户端
- Win10下VirtualBox安装流程
- node学习: package.json
- U盘出现很多.exe的文件处理方案
- 洛谷 P3159(BZOJ 2668)[CQOI2012]交换棋子
- [转]mysql变量使用总结
- 机器学习之深入理解SVM
- CSS兼容IE Firefox问题与解决方法
- ElasticSearch client API
- 2018软工实践—Beta冲刺(3)
- (转)解决WinDbg调试Dump文件不同环境mscordacwks.dll版本问题
热门文章
- Bootstrap 垂直(默认)表单
- Pascal之计算小系统
- CF915E Physical Education Lessons(珂朵莉树)
- ssh 公钥登录远程主机
- Python之Linux下的virtualenv&;&;virtualenvwrapper
- /bin,/sbin,/usr/sbin,/usr/bin 目录之简单区别
- urllib的高级用法
- 转 ORACLE-016:ora-01720 授权选项对于&#39;xxxx&#39;不存在
- JDK集合框架--综述
- Android 在代码中安装 APK 文件