请用c++解决以下问题题目描述加里敦大学的生物研究所发现了决定人喜不喜欢吃藕的基因序列 �S有这个序列的碱基序列就会表现出喜欢吃藕的性状但是研究人员发现对碱基序列 �S任意修改其中不超过 33 个碱基依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 �0S 0 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 �0S 0 上有多少个连续子串可能是该基因即有

算法1

(暴力枚举) $O(Tn^2)$

对每个位置暴力考虑它到后面每个位置的子串是否与S相似即可。

时间复杂度

设n是S的长度，则总时间复杂度是O(Tn^2)。

参考文献

暂无

C++ 代码

算法2

(滑动窗口) $O(Tn)$

对于每个位置i，设j是以i为起点的S的长度，滑动窗口的同时维护两个哈希表，分别表示当前窗口与S的差别不超过3的位置集合，和超过3的位置集合。每次滑动窗口，如果新加入的位置与S的差别不超过3，则把它加入差别不超过3的位置集合，否则加入超过3的位置集合。如果新加入的位置使得差别超过了3，则需要把窗口左端点右移，同时把哈希表中对应的位置移除。

时间复杂度

设n是S的长度，则总时间复杂度是O(Tn)。

参考文献

暂无

C++ 代码