【日常小测】相似子串

题目大意

给定一棵$n(n \le 10^5)$的无根树,每条边上有一个字符
定义$str_{u,v}$为从$u$走到$v$,将边上的字符按顺序写下来得到的字符串
给定$m(m \le 10^5)$个询问,每一次询问会定义$k_i$种形如$a,b$这样的等价关系,意义为将所有的$a,b$字符视为同一个字符(关系具有传递性)
对于每一个询问还会给定$u_1,v_1,u_2,v_2$四个点,请你回答$str_{u_1,v_1}$与$str_{u_2,v_2}$是否至多有一个位置不匹配

解题报告

这种奇怪的匹配题目除了$FFT$之外,似乎只能$Hash$了吧?

我们先来考虑没有等价类,且是一条链的情况

定义$Hash$函数$f_{i,u,v}$为对于第$i$种字符来讲,$str_{u,v}$的$Hash$值
更进一步,$f_{i,u,v}=\sum\limits_{j=u}^{v}{[char_j=i] \cdot G^{j-u+1}}$
那么这两个字符串的$Hash$值只能在两种字符下不同,且这两种字符差的$G$的次幂相等

考虑快速求得$Hash$值,这个很简单,做一个前缀和就好
考虑快速求的差值对应的$G$的次幂,这个我们先预处理一下,然后扔到一个$map$里去就可以了
至此我们已经能在$O(|\sum|+\log n)$的时间复杂度内回答单个询问了

现在考虑加入等价类,这个我们可以将整个等价类的$Hash$值加起来一起比较就可以了
至于不是链的情况,那我们求个到根前缀和就能够解决问题啦!
至此我们已经在$O(n \log n + m (|\sum| + \log n))$的时间复杂度内解决了这个问题

3 thoughts to “【日常小测】相似子串”

  1. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point. You definitely know what youre talking about, why waste your intelligence on just posting videos to your weblog when you could be giving us something informative to read?

  2. Hello! I’ve been reading your blog for a long time now and finally got the courage to go ahead and give you a shout out from Lubbock Texas! Just wanted to mention keep up the fantastic job!

发表评论

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