【JZOJ4876】【NOIP2016提高A组集训第10场11.8】基因突变
2024-09-06 13:38:20
题目描述
邪恶的707刚刚从白垩纪穿越回来,心中产生了一个念头:我要统治人类!
但是统治人类是很庞大且复杂的一个工程,707尝试了洗脑,催眠,以及武装镇压都没能成功地统治人类,于是她决定从科学上对人类的基因进行研究从而达到他的目的。
707获取了人类的基因信息并尝试对基因进行实验。他发现可以把人类的基因看做一个只包含小写字母的字符串,并定义从头开始任意长度的基因为“源头基因”人类身上与源头基因完全匹配的片段越多,这个人就越容易被控制。于是707就开始了他邪恶的计划……
作为人类卫士的射手ZMiG自然不会让707得逞,他决定拯救人类,现在他拿到了其中一个人被改造后的基因,他想请你统计一下它的基因中究竟有多少基因片段是可以与源头基因相匹配的
数据范围
对于30% 的数据,|S|<= 200
对于60% 的数据,|S|<= 2000
对于100%的数据,|S|<= 10^6
解法
KMP加路径压缩。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="gene.in";
const char* fout="gene.out";
const int inf=0x7fffffff;
const int maxn=1000008;
int n,i,j,k;
char a[maxn];
int fail[maxn],de[maxn];
ll ans;
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%s",a+1);
n=strlen(a+1);
de[1]=1;
j=0;
for (i=2;i<=n;i++){
while (j && a[j+1]!=a[i]) j=fail[j];
if (a[j+1]==a[i]) j++;
fail[i]=j;
ans+=(de[i]=de[j]+1)-1;
}
cout << ans+n << endl;
return 0;
}
最新文章
- linux安装php
- ios 实现自定义状态栏StatusBar 和 导航栏navigationBar 的状态和颜色
- C++快速入门系列教程
- jsp实现回车登录
- Sharepoint 2010 工作流启动时处理出错
- 使用Adobe Edge Inspect在各种设备中轻松测试同一页面
- CountDownLatch,CyclicBarrier,Semaphore
- [学习笔记]ESXI学习记录
- EntityFramework走马观花之CRUD(上)
- UVa 10917 A Walk Through the Forest
- 在Xshell中上传下载文件到本地(linux中从多次ssh登录的dbserver里面的文件夹)
- 利用ADO让普通人用excel读取oracle数据库表的通用办法
- zxing 如何识别反转二维码
- Java_Object
- zabbix异常信息修改已确认,为未确认
- Azure DevOps Server/Team Foundation Server
- python的可变对象与不可变对象
- Openvswitch手册(3): sFlow, netFlow
- python之路——13
- linux公钥和私钥生成
热门文章
- 隐藏和显示<;td>;
- --1.plsql中学习job
- LA5713 Qin Shi Huang&#39;s National Road System
- TCP/TP:DNS区域(Zone)
- c++新特性实验(3)声明与定义:constexpr
- 【python之路23】递归
- LUOGU P3435 [POI2006]OKR-Periods of Words
- 前端(Node.js)(2)-- Node.js开发环境配置
- js的模块化写法
- 关于python的字典操作