兔子与兔子

兔子与兔子
这题的话很好解,先预处理一下再暴力求值。
记我们选取的DNA序列为S,根据我们刚才提到的字符串Hash算法,设F[l]表示前缀子串S[1 ~ i]的Hash值,有F=[F-1]*131+(S[i]-"a"+1)于是可以得到任一区间[l,r]Hash值为F|r]-F|l-1]*131^{r-l+1}。当两个区间的Hash值相同时,我们就认为对应的两个子串相等。整个算法的时间复杂度为O(|S|+Q)

发表评论

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