• 周二. 10 月 8th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

另一种保证单次插入回文自动机复杂度的做法

admin

11 月 28, 2021

对于插入一个字符串,普通回文自动机复杂度是均摊的。
对于单次插入复杂度有证明的回文自动机插入,
(sum)为字符集大小,翁文涛的论文里提到了单次插入(O(sum))的记忆化,从理论上来说,可以通过主席树优化到(O(logsum)),但是代码量就增加了,而且对于26的字符集,这样写应该会变慢吧。
翻金策字符串算法选讲的时候,偶然发现了一个浅显的结论,回文串的border等价于它的后缀回文串。
那么这就好办了,直接利用border的性质,将暴力往上跳找fa改为一次跳一个等差数列找fa就好了。

int p=-1;
while (r-T[la].len-1<l||s[r-T[la].len-1]!=s[r]){
	if (p!=T[la].d){
		p=T[la].d;
		la=T[la].fa;
	}
	else la=T[T[la].df].fa;
}

其中(T[la].d)为他和他父亲(len)的差值,(T[la].df)为他所在(len)等差数列的祖先,由border的性质,这样单次插入最多跳(log(n))次,同时不影响总的均摊复杂度。虽然单次插入复杂度不如论文中的算法,但是不需要维护过多其他信息,只需要维护十分有用的等差数列就可以了。
这样,如果回文自动机上的转移边用hash存储,就可以得到一个单次插入(O(log(n))),插入字符串均摊复杂度(O(n)),空间(O(n))的做法。

发表回复