BZOJ_2099_[Usaco2010 Dec]Letter 恐吓信_后缀自动机+贪心
2024-08-30 16:47:17
BZOJ_2099_[Usaco2010 Dec]Letter 恐吓信_后缀自动机
Description
FJ刚刚和邻居发生了一场可怕的争吵,他咽不下这口气,决定佚名发给他的邻居 一封脏话连篇的信。他有无限张完全相同的已经打印好的信件,都包含 N个字母(1 <= N <= 50,000)。他想剪出其中一些并且粘帖成一个很长的字母串。 FJ太懒了,他想用最少的次数裁剪信件。他有一把举世无双的剪刀,他可以从 一封信中只剪一刀剪出连续一段。同样,剪一刀可以得到整个完整的字符串。 他想知道他最少需要剪多少刀从而获得这封M个字母的长信? 保证这总是可能的。 考虑下面38个字母的信: THEQUICKBROWNFOXDO GJUMPSOVERTHELAZYDOG 以及FJ想要获得的9个字母的信: FOXDOG DOG 以上是为了读入方便,实际上这两封信就是: THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG FOXDOGDOG 由于FOXDOG已经存在了,FJ可以剪一刀得到FOXDOG。还剩下一个DOG,FJ可以选择 其中任何一个DOG剪下来。 因此,他一共要剪2刀。
Input
* 第一行: 两个空格分隔的整数: N, M * 第2..?行: 一些行包含N个字母,FJ原来拥有的信,每行不会超过80个字母。 * 第?...?行: 一些行包含M个字母,FJ想要写的信,每行不会超过80个字母。
Output
* 第1行: FJ获得他想要写的信所需要切的最少次数。
Sample Input
38 9
THEQUICKBROWNFOXDO
GJUMPSOVERTHELAZYDOG
FOXDOG
DOG
THEQUICKBROWNFOXDO
GJUMPSOVERTHELAZYDOG
FOXDOG
DOG
Sample Output
2
对第一个串建立后缀自动机,用第二个串去匹配。
每次找最长的能匹配的子串即可。
由于每次都选出一个子串,所以这个贪心是对的。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50050
using namespace std;
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int ch[N<<1][26],dep[N<<1],fa[N<<1],cnt=1,lst=1,lw,ls;
char w[N],s[N];
void insert(int x) {
int p=lst,np=++cnt,q,nq;
lst=np; dep[np]=dep[p]+1;
for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=np;
if(!p) fa[np]=1;
else {
q=ch[p][x];
if(dep[q]==dep[p]+1) fa[np]=q;
else {
fa[nq=++cnt]=fa[q];
dep[nq]=dep[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[q]=fa[np]=nq;
for(;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq;
}
}
}
int main() {
scanf("%d%d",&lw,&ls);
int i,tot=0;
while(1) {
char c=nc(); while(c<'A'||c>'Z') c=nc();
while(c>='A'&&c<='Z') w[++tot]=c,c=nc();
if(tot==lw) break;
}
tot=0;
while(1) {
char c=nc(); while(c<'A'||c>'Z') c=nc();
while(c>='A'&&c<='Z') s[++tot]=c,c=nc();
if(tot==ls) break;
}
// printf("%s\n%s\n",w+1,s+1);
for(i=1;i<=lw;i++) insert(w[i]-'A');
int ans=0,now=1,p;
while(now<=ls) {
p=1;
while(ch[p][s[now]-'A']) p=ch[p][s[now]-'A'],now++;
ans++;
}
printf("%d\n",ans);
}
最新文章
- 读取全球ip获取用户地区
- 取消vs2013在代码中的Reference数量功能
- 03-Java String字符串详解
- arithmetic-slices-ii-subsequence(太难了)
- android应用崩溃的调试方法(c++ lib so文件库崩溃)
- IOS开发之NSObject协议类方法说明
- php实例-正则获取网站音频地址的实例(Listen to this 1)
- What is Observer and Observable and when we used these?
- [补档][Jxoi2012] 奇怪的道路
- 源码剖析Django REST framework的请求生命周期
- jQuery-AutoComplete自动提示简单实现
- Springmvc导出Excel(maven)
- Python库资源大全
- unity3d 射线的原理,基础用法
- 44.scrapy爬取链家网站二手房信息-2
- you-get
- SharePoint Visio Graphics Service-PowerShell
- 【.Net】水晶报表CrystalReport粗浅入门
- 支撑大规模公有云的Kubernetes改进与优化 (2)
- [Database] MongoDB 副本集配置
热门文章
- java使用反射的好处
- ACDream:1210:Chinese Girls&#39; Amusement【水题】
- jvm参数设置 -vmargs -Xms128M -Xmx512M -XX:PermSize=64M -XX:MaxPermSize=128M
- j_spring_security_check 404错误
- 弹飞绵羊(bzoj 2002)
- [NOIP2003] 提高组 洛谷P1041 传染病控制
- 如何改变linux系统的只读文件的权限
- BZOJ3926 (后缀自动机)
- HDU 6437 最(大) 小费用最大流
- HDU 3966