本文共 840 字,大约阅读时间需要 2 分钟。
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 372 Solved: 195 [ ][ ][ ] Description
Byteasar 想在墙上涂一段很长的字符,他为了做这件事从字符的前面一段中截取了一段作为模版. 然后将模版重复喷涂到相应的位置后就得到了他想要的字符序列.一个字符可以被喷涂很多次,但是一个位置不能喷涂不同的字符.做一个模版很费工夫,所以他想要模版的长度尽量小,求最小长度是多少.拿样例来说 ababbababbabababbabababbababbaba , 模版为前8个字符ababbaba, 喷涂的过程为: ababbababbabababbabababbababbaba
Input
输入一行最多不超过500 000 个最少1个小写字符.
Output
Sample Input
ababbababbabababbabababbababbaba
Sample Output
想到这题就很简单了,建起来就过了,感觉网上很多题解都很不错,讲的特别详细,我就偷个懒啦
至于为什么还要用链表,其实这是为了优化,并且这个优化非常好想到
#include #include #include #include using namespace std;vector G[500005];char str[500005];int len, fail[500005], son[500005], L[500005], R[500005];void Sech(int u, int p){ int i, v; if(u!=0) { R[L[u]] = R[u]; L[R[u]] = L[u]; len = max(len, R[u]-L[u]); } for(i=0;i
转载地址:http://aqmgf.baihongyu.com/