一开始有一空串,n次操作,每次在串末尾加入一个字符问最小循环节。要求在线与可持久化。
如果只是在线的话那是很简单的,答案是!!$i-fail[i]$,其中$fail[i]$是KMP中的失配函数。
但如果可持久化的话:
一、复杂度难保,因为过程不连贯,没法用普通KMP那种复杂度的证明。
二、给出的字符串实际上形成了一个树结构,需要找到每个字符是谁。
问题二用个倍增搞定。重点是问题一。
一直往前跳的过程中,如果某时匹配到了,那就可以结束跳的过程;那如果没匹配到接着往前跳:
1、$2*fail[j]<j$,直接$j=fail[j]$;
2、$2*fail[j]>=j$,此时前缀j的后$j-fail[j]$个字符形成了这个前缀串的循环节,那如果在循环节里一直跳跳跳,往前跳一次又会遇到相同的字符,也就是在循环节里面跳的话会一直遇到一样的字符,直到$j mod fail[j]$处。
上面两种情况,j都至少缩小一半,所以一次匹配的最坏复杂度变成了log(n)。于是两个log完美通过。