• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

P3426-[POI2005]SZA-Template【KMP】

admin

11月 28, 2021

正题

题目链接:https://www.luogu.com.cn/problem/P3426


题目大意

给出一个长度为(n)的字符串(s),求一个长度最小的字符串(t)使得(s)所有(t)(t)匹配的位置能覆盖串(s)

(1leq nleq 5 imes 10^5)


解题思路

首先答案肯定是原串的一个(border),设(f_i)表示前缀(s_{1sim i})的答案。

考虑如何转移,首先(f_i)至多是(i),然后考虑如果有一个串(t)能够覆盖(s_{1sim nxt_i})那么才有可能能覆盖(s_{1sim i})。(因为如果覆盖大于(nxt_i)显然不可能覆盖整个串,不然就至少需要覆盖到(s_{1sim nxt_i}))。

考虑什么时候(f_i)能够取到(f_{nxt_i})。首先我们可以表示出(s_{1,nxt_i})假设我们上次覆盖的位置是(jin[nxt_i,i]),那么需要有(f_{j}=f_{nxt_i})(即取到同一个(border)),然后要求(jgeq i-nxt_i)(这样就可以用(s_{1,nxt_i})覆盖剩下的)。

时间复杂度(O(n))


code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+10;
int n,f[N],nxt[N],ls[N];
char s[N];
int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=2,j=0;i<=n;i++){
		while(j&&s[j+1]!=s[i])j=nxt[j];
		j+=(s[i]==s[j+1]);nxt[i]=j;
	}
	for(int i=1;i<=n;i++){
		f[i]=i;
		if(i-ls[f[nxt[i]]]<=nxt[i])
			f[i]=f[nxt[i]];
		ls[f[i]]=i;
	}
	printf("%d
",f[n]);
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。