资源描述：
《基于位运算的最长公共子串算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、IOI2006国家集训队作业：研究报告浙江唐文斌基于位运算的最长公共子串算法浙江唐文斌[摘要]本文来自于参考文献[1]。本文描述了一个对于确定有限字符集的基于位运算的最长公共子串算法。该算法在普通计算机上运行效率明显高于常规的动态算法。其时间复杂度为。其中w表示我们在w位的整数上进行位操作。[问题介绍]最长公共子串（Longest-common-subsequence,LCS）问题，是求两个字符串A和B的公共子串的最大可能长度。例如，字符集S={’A’,’C’,’G’,’T’}，’GCTAT’和’CGATTA’的最大公共子串（以下简称LCS）为’GTT’，其长度为3。在这里定义
2、一些变量:A,B分别是两个给定的串。S为A、B串所涉及的字符集。[常规动态规划算法]设L[i,j]等于A[1..i],B[1..j]的LCS.则有L[i,j]=1+L[i-1,j-1]如果(A[i]=B[j])Max(L[i-1,j],L[i,j-1])其他复杂度为O(
3、A
4、*
5、B
6、)[基于位运算的动态规划算法]根据上面的动态规划算法，状态函数L具有如下性质：L[i-1,j-1]≤L[i,j-1],L[i-1,j]≤L[i,j]
7、L[i,j]-L[i-1,j-1]
8、≤1对于L的每一行，相邻的两个元素的最多只相差1。这样一来，我们就可以用一个二进制的矩阵描述出L:()IOI200
9、6国家集训队作业：研究报告浙江唐文斌#bits90001100010111111
10、TstringB90100100010111111
11、T80010001000111111
12、C70000100010011111
13、T-Row[11]71000000100011111
14、A-Row[10]71000010000011111
15、G60000010100001111
16、A50000000100001111
17、A50000100000001111
18、T40000000010000111
19、T30000000000100011
20、C31000000000010001
21、G20000000100000100
22、
23、A10000000000000100
24、T_________________________________.matrixMijStringA:GTCTTACATCCGTTCG这里，我们将串A从右往左写，串B从下往上写。Row[i]中的1的个数总是和Row[i-1]中的1的个数一样多或者恰好多一个。串A和串B的LCS即为最上面一行Row[
25、B
26、]中1的个数。字符比较串表这里我们定义一组称为字符比较串的二进制串。分别是字符集中的每一个字符与串A的比较结果(相同为1，不同为0)。A：GTCTTACATCCGTTCG‘A’-string:0000010100000000‘C’-stri
27、ng:0010001001100010‘G’-string:1000000000010001‘T’-string:0101100010001100预先计算这个字符比较串表，时间复杂度为O(
28、S
29、*
30、A
31、)。对于一个确定的字符集，时间复杂度为O(
32、A
33、)。对于一个不确定的字符集，最坏情况为O(
34、A
35、*
36、B
37、)。如果字符集较小，
38、S
39、<<
40、B
41、，预处理的时间复杂度可以被忽略。矩阵M为了计算Row[i]，我们需要用到字符比较串表中的B[i]-string。以Row[10]到Row[11]为例，我们来研究如何计算出Row[i]。下面是Row[10],以及B[10]-string(‘T’
42、-string).按照Row[10]中的1分隔：Row[10]:1000000100011111T-string:0101100010001100每一段都是从Row[i-1]IOI2006国家集训队作业：研究报告浙江唐文斌的一个1的位开始往右延伸，直到下一个位置是1或者串结束。如果Row[i-1]的最左边的位置上是0，那么最左边的一段从B[i]-string的最左边的1的位置开始延伸直到下一个1。Row[i]的构成方式很简单：就是对于每一段，都是选择Row[i-1]或者B[i]-string最右边的1所在位置为1，其他的为0。如果这一段Row[i-1]和B[i]-string都
43、是0，那么Row[i]这一段也为0。‘T’-stringOrRow[10]:11011*0011*001*1*1*1*1*Row[11]:0000100010011111*表示了进行或操作之后每一段最右边的1附带一提，你可以假定在每个串的最左边（位置
44、A
45、+1）存在一个1，这样可以方便处理最左边一段全为0的情况。不过对于本算法并没有这个必要。在Row[i-1]中的一个1的位置，代表了A中的一个最短前缀与B[1..i-1]的LCS达到了该长度。引进B[i]，最好的方法当然是在前面的最短基础上加
