正题

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

题目大意

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

\(1\leq n\leq 5\times 10^5\)

解题思路

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

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

考虑什么时候\(f_i\)能够取到\(f_{nxt_i}\)。首先我们可以表示出\(s_{1,nxt_i}\)假设我们上次覆盖的位置是\(j\in[nxt_i,i]\)，那么需要有\(f_{j}=f_{nxt_i}\)（即取到同一个\(border\)），然后要求\(j\geq 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\n",f[n]);

	return 0;

}

巴特西

P3426-[POI2005]SZA-Template【KMP】

正题

题目大意

解题思路

code

最新文章

热门文章