网站开发ceac证,果洛营销网站建设哪家好,信息系统开发计划,吉林seo外包正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP3435 大意
一个字符串#xff0c;对于每个前缀#xff0c;求复制一份放在末尾可以覆盖整个前缀的前缀#xff0c;求所有的长度和。 解题思路
这道题如果暴力的话很简单#xff0c;对于每个前缀每…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP3435 大意
一个字符串对于每个前缀求复制一份放在末尾可以覆盖整个前缀的前缀求所有的长度和。 解题思路
这道题如果暴力的话很简单对于每个前缀每次往前跳如果不可以覆盖了就下一个。 但是这样会被卡成O(n2)O(n2)O(n^2) 所有我们可以加一个优化我们找一个最短的然后总长度减去最短的就是最长的。我们就可以每次改变next的值让他直接指向最短的然后就可以O(n)O(n)O(n)解决问题 code
#includecstdio
using namespace std;
int n,next[1000011];
char s[1000011];
long long ans;
int main()
{scanf(%d,n);scanf(%s,s);for(int i1,j0;in;i){while(j(s[i]!s[j])) jnext[j];j(s[i]s[j]);next[i1]j;}//匹配指针int j;for(int i1;in;i){ji;while(next[j]) jnext[j];//跳转if(next[i]!0)next[i]j;//记忆化ansi-j;//统计答案}printf(%lld,ans);
}
