• 周四. 5月 30th, 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))的做法。

《另一种保证单次插入回文自动机复杂度的做法》有2个想法
  1. Undeniably believe that which you stated. Your favorite justification seemed to be on the net the simplest thing to be aware of.
    I say to you, I certainly get irked while people
    think about worries that they just don’t know about. You managed to hit
    the nail upon the top as well as defined out the whole thing without having side-effects , people could take a signal.
    Will likely be back to get more. Thanks I saw similar here:
    Ecommerce

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注