既见君子

同济医学生的起落落落落人生记录

[BZOJ1461]字符串的匹配

题目大意:给出a串和b串,求出a串中有多少个子串和b相等,这里相等的定义是i位置的数在这个区间里的排名是一样的。

题解:(1)考虑对于排名来说,如果满足i位置排名相等,于是再加一个i+1的位置的数,如果排名也相等,那就说明这个数对于之前的区间里的每个数的影响都是一样的,所以本质依旧相同。那么我们就考虑用kmp和树状数组来维护这样一个过程。

1.树状数组是用来查排名的。(排名既要查<也要查<=,因为假设原序列排序完毕之后是12 44,比较排名的两个值是3,4,只查<的话明显是一样的,而如果比较的两个值是2,3,那么只查<=查出来是一样的,但是他们由此带来的对原序列的影响却都是不一样的,因为一个值只能影响比它大的值,所以我们必须在比较的时候也要把值相等的拿出来比较比较)

2.求nxt的时候注意跳nxt的时候需要把那些“变短”的东西的影响给删除。

//感觉现在还是处于迷迷糊糊的状态,这个排名没有后效性还是没有理解透彻。

之前一直有一个不太明白的地方是当a[i]..a[i+m-1]与b[1]..b[m]本质相同而m+1的时候不一样了b会沿着nxt跳,对于a来说就会砍掉前面一节“跳过的长度”,为什么剩下的依然是满足条件的呢。因为a[i]..a[i+m-1]与b[1]..b[m]本质一样,那么我们任意的dia一部分出来也是一样的(就是剩下的后半部分是一定本质一样的,而求nxt的时候我们保证了b[1]..b[fail]与这一段本质是一样的,所以利用等式的传递性就可以得到上面那部分依然本质一样)

(2)hash的做法

首先暴力求到第一个区间的hash值记为ans,用排名来hash,然后把这些位置的真实值的值域线段树上的位置存下这个数到底×了base的多少次方。

考虑当区间移动的时候,我可以知道左端应该“出局”的数的排名。然后把所有值比他大的数相当于排名都要-1,但我们存下了那些base^i的和,直接ans减掉就相当于-1了。然后在线段树上单点修改这个位置。对于右端点应该加入的数也是差不多的处理方法。线段树需要做的就是支持:1.得到区间合2.区间乘3.单点修改。

//好方啊我理解kmp理解了辣么久然而居然hash可以暴力乱搞哼气死我了。

//只能用“线段树代码长常熟大”来安慰自己了。

最后贴上几乎和标程一样的代码(谁叫我是边看代码边理解的ovo)

http://paste.ubuntu.net/15340954/


评论
©既见君子
Powered by LOFTER