【JZOJ4876】基因突变

发布于 2016-11-14  418 次阅读


Description

邪恶的707刚刚从白垩纪穿越回来,心中产生了一个念头:我要统治人类!
但是统治人类是很庞大且复杂的一个工程,707尝试了洗脑,催眠,以及武装镇压都没能成功地统治人类,于是她决定从科学上对人类的基因进行研究从而达到他的目的。
707获取了人类的基因信息并尝试对基因进行实验。他发现可以把人类的基因看做一个只包含小写字母的字符串,并定义从头开始任意长度的基因为“源头基因”人类身上与源头基因完全匹配的片段越多,这个人就越容易被控制。于是707就开始了他邪恶的计划……
作为人类卫士的射手ZMiG自然不会让707得逞,他决定拯救人类,现在他拿到了其中一个人被改造后的基因,他想请你统计一下它的基因中究竟有多少基因片段是可以与源头基因相匹配的

Input

输入一个只包含小写字母的字符串S

Output

输出一个整数,代表可以与源头基因相匹配的基因片段数量。

Sample Input

【样例输入1】
aaba

【样例输入2】
niconiconi

Sample Output

【样例输出1】
6

【样例解释1】
这六个片段分别为(1,1),(1,2),(1,3),(1,4),(2,2),(4,4)

【样例输出2】
18

Data Constraint

对于30% 的数据,|S|<= 200
对于60% 的数据,|S|<= 2000
对于100%的数据,|S|<= 10^6

题目分析:相当于对于每个前缀求有多少个字符串和他相等 可以先求出 KMP 的 nxt 数组,然后对于一个位置,每跳一次 nxt 就说明多了一个合法的 匹配。一个暴力方法是直接从每个节点开始跳统计答案。显然我们可以用 f[i]表示以 i 为 结尾有多少组这样的匹配,然后可以发现 f[i]=f[nxt[i]]+1,这样 O(N)扫一遍就可以了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
typedef long long LL;

char s[1000005];
LL n,next[1000005],f[1000005],ans;
inline void kmp(){
	int j=0;
	Fork (i,2,n){
		while (j>0&&s[j+1]!=s[i]) j=next[j];
		if (s[i]==s[j+1]) j++;
		next[i]=j;
	}
}
int main(){
	freopen("gene.in","r",stdin);
	freopen("gene.out","w",stdout);
	n=strlen(gets(s+1));
	kmp();
	For (i,n)
	f[i]=f[next[i]]+1,ans+=f[i];
	printf("%lld",ans); 
}

「知我罪我,其惟春秋」