可以上传高清图片的网站并做外链,合肥装饰公司前十名,网站3级营销是怎么做的,佛山企业网站建设咨询正题
题目链接:https://www.luogu.com.cn/problem/P3426 题目大意
给出一个长度为nnn的字符串sss#xff0c;求一个长度最小的字符串ttt使得sss所有ttt和ttt匹配的位置能覆盖串sss。 1≤n≤51051\leq n\leq 5\times 10^51≤n≤5105 解题思路
首先答案肯定是原串的一个borde…正题
题目链接:https://www.luogu.com.cn/problem/P3426 题目大意
给出一个长度为nnn的字符串sss求一个长度最小的字符串ttt使得sss所有ttt和ttt匹配的位置能覆盖串sss。
1≤n≤5×1051\leq n\leq 5\times 10^51≤n≤5×105 解题思路
首先答案肯定是原串的一个borderborderborder设fif_ifi表示前缀s1∼is_{1\sim i}s1∼i的答案。
考虑如何转移首先fif_ifi至多是iii然后考虑如果有一个串ttt能够覆盖s1∼nxtis_{1\sim nxt_i}s1∼nxti那么才有可能能覆盖s1∼is_{1\sim i}s1∼i。因为如果覆盖大于nxtinxt_inxti显然不可能覆盖整个串不然就至少需要覆盖到s1∼nxtis_{1\sim nxt_i}s1∼nxti。
考虑什么时候fif_ifi能够取到fnxtif_{nxt_i}fnxti。首先我们可以表示出s1,nxtis_{1,nxt_i}s1,nxti假设我们上次覆盖的位置是j∈[nxti,i]j\in[nxt_i,i]j∈[nxti,i]那么需要有fjfnxtif_{j}f_{nxt_i}fjfnxti即取到同一个borderborderborder然后要求j≥i−nxtij\geq i-nxt_ij≥i−nxti这样就可以用s1,nxtis_{1,nxt_i}s1,nxti覆盖剩下的。
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N5e510;
int n,f[N],nxt[N],ls[N];
char s[N];
int main()
{scanf(%s,s1);nstrlen(s1);for(int i2,j0;in;i){while(js[j1]!s[i])jnxt[j];j(s[i]s[j1]);nxt[i]j;}for(int i1;in;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;
}
