两道题，问了N多人，没结果，再问一下看看

THEBEST

to bioinfor:

这是我要到的一个例子的标准答案，如果这个能运行出来的话，那就证明你的程序没有问题了。

不能这么讲的,这只不过是一个很小的特例,我把main改成:

1. int main()
   
2. {
   
3.     string testString("ACGTGCGATCACAGGCCGTGCAGAGACTGACGATCAGACGACGTGACAGGCCGTGCAGAGACTGACGATCAG");
   
4.    
   
5.    srand(time(0));     //应该放在这里(其它某些地方也可以),居然犯这种错误.:p
   
6. //   string testString;
   
7. //   RandString(testString);
   
8.    FindSameStr(testString);
   
9. //  FindSameReverseStr(testString);   
   
10. }

复制代码

把MaxLen改成72就是你给出的字符串的总长度.
结果如下:

The Same String in the Source String:

"ACAGGCCGTGCAGAGACTGACGATCAG"
       Length:  27
The Start Pos:  11  46  



Source String:
ACGTGCGATCACAGGCCGTGCAGAGACTGACGATCAGACGACGTGACAGGCCGTGCAGAGACTGACGATCAG

可以看到,结果与你给出的一样的,但错误是觉得有的.而且应该在总字符串长度10000以内都不会发现有错,这个程序还运行的相当的好,当你把最大长度设为10*10000的时候你就可以看到问题的存在,此BUG还不知道怎么回事来着.

THEBEST

而且应该在总字符串长度10000以内都不会发现有错,这个程序还运行的相当的好,

当然我说的是一种概率情况而不是在你巧妙的安排字符串的情况下,更严格的讲是:当不会出现三个同样字符字串时就不会出现问题,而在10000以内产生三个长度至少为10的同样的子串概率很低,把总长度提高10倍就可以看到产生了问题.

lightspeed

THEBEST兄，　我用　awk 写了一个，　想对比一下与　C++ 处理速度上
的差距．　请去这里：
http://bbs.chinaunix.net/forum/viewtopic.php?t=464277&show_type=&start=15&sid=1dc92d81c4a3a4a8269c3f17a5d5e30f

下载 10000 个字符的数据文件．（为显示我作了fold 处理，　你在把它恢复成单行），　然后查找所有不重叠的串长为　10 - 30 的重复串，
计算一下时间．

yuxh

这样是不是就可以了呢

1. #include <stdio.h>;
   
2. #include <stdlib.h>;
   
3. #include <string.h>;
   
4. #include <time.h>;
   
5. 
   
6. #define MAXSIZE 100
   
7. #define MINMATCH 5
   
8. char strUnit[] = {'A', 'C', 'G', 'T'};
   
9. 
   
10. int GenQueue(char *strQueue) {
    
11.     time_t  ck;
    
12.     int     nQueueSize,i;
    
13. 
    
14.     if(strQueue == NULL) return 0;
    
15.     memset(strQueue, 0, MAXSIZE);
    
16. 
    
17.     ck = time(NULL);
    
18.     srand(ck);
    
19.     nQueueSize = rand() % MAXSIZE;
    
20. 
    
21.     for(i = 0; i < nQueueSize; i++) {
    
22.         strQueue[i] = strUnit[rand() % 4];
    
23.     }
    
24.     return nQueueSize;
    
25. }
    
26. 
    
27. int MatchVerted(char *strQueue, int nQueueSize) {
    
28.     char *pQueue, strMatch[MAXSIZE / 2 + 1];
    
29.     int  i, nMatchLen, nBegin, nFlag, nPosition;
    
30. 
    
31.     printf("\nVerted Repeat:\n");
    
32. 
    
33.     for(nBegin = MINMATCH; nBegin < nQueueSize - MINMATCH; nBegin++) {
    
34.         pQueue = strQueue + nBegin;
    
35.         nMatchLen = 0;
    
36.         nFlag = 0;
    
37.         for(i = 0; i <= nQueueSize - nBegin; i++) {
    
38.             if(strQueue[i] == pQueue[i]) {
    
39.                 if(nFlag == 0) {
    
40.                     nFlag = 1;
    
41.                     nPosition = i;
    
42.                 }
    
43.                 strMatch[nMatchLen++] = strQueue[i];
    
44.                 if(nMatchLen >;= nBegin) {
    
45.                     strMatch[nMatchLen] = 0;
    
46.                     printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, nPosition + nBegin);
    
47.                     nFlag = 0;
    
48.                     nPosition = 0;
    
49.                     nMatchLen = 0;
    
50.                 }
    
51.             }
    
52.             else {
    
53.                 if(nFlag == 1) {
    
54.                     if(nMatchLen >;= MINMATCH) {
    
55.                         strMatch[nMatchLen] = 0;
    
56.                         printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, nPosition + nBegin);
    
57.                     }
    
58.                     nFlag = 0;
    
59.                     nPosition = 0;
    
60.                     nMatchLen = 0;
    
61.                 }
    
62.             }
    
63.         }
    
64.     }
    
65. }
    
66. 
    
67. int MatchInverted(char *strQueue, int nQueueSize) {
    
68.     char *pQueue, strMatch[MAXSIZE / 2 + 1];
    
69.     int  i, nMatchLen, nBegin, nFlag, nPosition;
    
70. 
    
71.     printf("\nInverted Repeat:\n");
    
72. 
    
73.     for(nBegin = 0; nBegin < nQueueSize - 2 * MINMATCH; nBegin++) {
    
74.         pQueue = strQueue + nQueueSize - 1 - nBegin;
    
75.         nMatchLen = 0;
    
76.         nFlag = 0;
    
77.         for(i = 0; i < (nQueueSize - nBegin) / 2; i++, pQueue--) {
    
78.             if(strQueue[i] == *pQueue) {
    
79.                 if(nFlag == 0) {
    
80.                     nFlag = 1;
    
81.                     nPosition = i;
    
82.                 }
    
83.                 strMatch[nMatchLen++] = strQueue[i];
    
84.             }
    
85.             else {
    
86.                 if(nFlag == 1) {
    
87.                     if(nMatchLen >;= MINMATCH) {
    
88.                         strMatch[nMatchLen] = 0;
    
89.                         printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, pQueue - strQueue + 1);
    
90.                     }
    
91.                     nFlag = 0;
    
92.                     nPosition = 0;
    
93.                     nMatchLen = 0;
    
94.                 }
    
95.             }
    
96.         }
    
97.         if(nMatchLen >;= MINMATCH) {
    
98.             strMatch[nMatchLen] = 0;
    
99.             printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, pQueue - strQueue + 1);
    
100.         }
     
101.     }
     
102. }
     
103. 
     
104. int main(void) {
     
105.     char strQueue[MAXSIZE];
     
106.     int nQueueSize;
     
107. 
     
108.     nQueueSize = GenQueue(strQueue);
     
109.     printf("String:\n%s\n", strQueue);
     
110. 
     
111.     MatchVerted(strQueue, nQueueSize);
     
112.     MatchInverted(strQueue, nQueueSize);
     
113. }
     
114. 
     

复制代码

THEBEST

to lightspeed老大:

我用　awk 写了一个，　想对比一下与　C++ 处理速度上
的差距．　请去这里：

我不太明白你的意思,我不懂AWK,我用C++写的在处理上没有优化,方法也很臭.所以我认为写的很不好.而且还不正确(有BUG的).

下载 10000 个字符的数据文件．（为显示我作了fold 处理，　你在把它恢复成单行），　然后查找所有不重叠的串长为　10 - 30 的重复串， 计算一下时间．

为什么是10-30?大于10就是了.(题目如此要求的),所以不重叠?我处理的是考虑了重叠方式,如果不重叠会处理的更少情况,所以速度也有所改善.你顺便处理一下10*10000个源字符串并最小长度为10(没有最大长度)的重复字符串,看看速度.
你可以直接运行我的程序,改一下存放文件的C:\\result.txt就可以了.我现在没有LINUX/UNIX,执行不了你的程序.
你的程序完全正确吗?我觉得很难验证.

to:yuxh     
你的程序好像很好也很快(毕竟是C),但我不知你是否处理了所有的情况和符合题目要求,至少我在测试你的长度为10000,100000,1000000,长度的字符串时结果都没有超过两个重复的字符串的,这应该是不正确的,从概率上讲不会不超过两个的.所以我觉得你的程序还有情况未考虑清楚.我没认真看程序只是看了一下运行结果.

主任的水平确实让人敬佩，但我觉得主任可能没有考虑延伸的问题：如AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAA

这个序列没有>;10的重复，如果有的话也只能是本身，如果不延伸的话，它会有很多个重复，从10开始以1个步长移动。呵呵，一家之言，也可能题目给的不清楚。

这样结果不是你给出的吧?那样就不是题目的意思了.反正这个结果是找出最大长度的重复字符串.


唉,这里没人讨论这个问题,SHELL那里人还较多.

yuxh

我的算法和你们不一样
我把字符串当成两个一样的串来考虑，一个串固定，另一个串划动(象拉链一样)，每一个次都取最大匹配串。。。
这样比较清楚，不用考虑很多复杂的东西，但效率不是很高，o(n*n)

yuxh

重复的情况应该是可以发现的
我的程序里串长是随机的，而且出来的结果很多，不是按照重复的排列，所以不好找
下面这个串
ACGTGCGATCACAGGCCGTGCAGAGACTGACGATCAGACGACGTGACAGGCCGTGCAGAGACTGACGATCAGACGTGCGATCACAGGCCGTGCAGAGACTGACGATCAGACGACGTGACAGGCCGTGCAGAGACTGAC
GATCAG
(楼主给的例子，重复了一份)，得到的结果是：
String:
ACGTGCGATCACAGGCCGTGCAGAGACTGACGATCAGACGACGTGACAGGCCGTGCAGAGACTGACGATCAGACGTGCGA
TCACAGGCCGTGCAGAGACTGACGATCAGACGACGTGACAGGCCGTGCAGAGACTGACGATCAG

Verted Repeat:
Repeat:ACAGGCCGTGCAGAGACTGACGATCAGACG, Size: 30, Start Positioins:10, 45
Repeat:ACAGGCCGTGCAGAGACTGACGATCAG, Size: 27, Start Positioins:82, 117
Repeat:ACAGGCCGTGCAGAGACTGACGATCAGACG, Size: 30, Start Positioins:45, 82
Repeat:ACGTGCGATCACAGGCCGTGCAGAGACTGACGATCAGACGACGTGACAGGCCGTGCAGAGACTGACGATCAG,
Size: 72, Start Positioins:0, 72
Repeat:ACAGGCCGTGCAGAGACTGACGATCAG, Size: 27, Start Positioins:10, 117

Inverted Repeat:

THEBEST

对于一个已知的基因序列片段如何在数据库中找出与之相近的记录，并标识出该片段
在记录中的位置，是Blast中最关键的部分。由于Blast数据库中含有成千上万条基因
序列记录，而每一条序列记录又含有成千上万个碱基，这些碱基以一定的编码方式存
储在数据库文件之中，所以这种检索操作也是Blast中最为耗时的操作。

在Blast进行检索时，首先需要将数据库名称、需检索的基因序列数据以及以何种方
式进行检索通知Blast，在获得这些参数之后，Blast将需检索的序列数据读人一个
Bioseq的结构中，将数据库中所有的记录采用MAP方式映象到内存中，然后从数据库
的第一条记录开始到最后一条记录逐条进行比较。在这种比较的过程中，Blast采用
了一种窗口算法来进行这种匹配。这种算法描述如下：
第一步，对匹配基因序列数据进行计算。我们假定匹配序列如下（采用核酸基因序列）：
>;test
AATAATAAAATAGGGCGTGC
则对应的核酸基因序列编码（Encode）如下：
00 00 11 00 00 11 00 00 00 00 11 00 10 10 10 01 10 11 10 01
定义一个16比特大小的窗口（Window），16比特大小表示从窗口来看一个二进制串，
只能看到该串的一个连续的16bits子串。窗口可以在二进制串上左右移动，每次移
动步长为1byte，窗口的值为二进制子串的值，窗口的位置为窗口最后一位在二进
制串上的位置。对于一个确定的二进制串和窗口来说，窗口的每一个位置都对应一
个16bits的二进制整数值。下表计算出Encode上Window的所有窗口位置和相应的窗口值：
Position of Window Value of Window Binary String of Window
8 3120 0000110000110000
9 12480 0011000011000000
10 49920 1100001100000000
11 3075 0000110000000011
12 12300 0011000000001100
13 49202 1100000000110010
14 202 0000000011001010
15 810 0000001100101010
16 3241 0000110010101001
17 12966 0011001010100110
18 51867 1100101010011011
19 10862 0010101001101110
20 43449 1010100110111001

第二步，对数据库中的每一个记录序列数据定义同样的窗口，在匹配时顺序计算其
窗口值，如果数据库序列数据的某一窗口值与匹配序列的窗口值列表中的某一项相
等，则比较序列数据的前后部分，如果前后都相等，则找出了一个符合条件的子串，
否则窗口在数据库序列数据中后移16bits，再顺序计算其窗口值。假定数据库的一
个记录序列数据（核酸序列数据）如下：
>;Database Sequence
ACTTTCAATAATAAAATAGGGCGTGCAACT
则对应的核酸基因序列编码（Encodebase）如下：
00 01 11 11 11 01 00 00 11 00 00 11 00 00 00 00
11 00 10 10 10 01 10 11 10 01 00 00 01 00 00 01
定义如同匹配串的窗口（windowbase），开始计算窗口在位置8时的窗口值为2036，
没有一个匹配串的窗口值与之相等；windowbase窗口下移16bits，再计算位置为16的
窗口值为12480，他和匹配串窗口位置9的窗口值相等，这时比较前后剩下的序列数据
发现该数据库序列数据包含一个与待匹配序列完全相同的序列片段。如此类推直到找
出所有满足条件的记录。


具体你可以看一下http://www.bioinfo.org.cn/computer/blastand.htm

但我不是按这个办法来的.这样效率应该是比较高的.

我把字符串当成两个一样的串来考虑，一个串固定，另一个串划动(象拉链一样)，每一个次都取最大匹配串。。。

你的似乎差不多.

我的程序里串长是随机的，而且出来的结果很多，不是按照重复的排列，所以不好找

嗯,一开始没仔细看,没发现.sorry.

longyjb

高手真多。。。。。。。。。。

lightspeed

原帖由 "THEBEST" 发表：
我不太明白你的意思,我不懂AWK,我用C++写的在处理上没有优化,方法也很臭.所以我认为写的很不好.而且还不正确(有BUG的).
引用:
下载 10000 个字符的数据文件．（为显示我作了fold 处理，　你在把它恢复成单行），　然后查找所有不重叠的串长为　10 - 30 的重复串， 计算一下时间．
为什么是10-30?大于10就是了.(题目如此要求的),所以不重叠?我处理的是考虑了重叠方式,如果不重叠会处理的更少情况,所以速度也有所改善.你顺便处理一下10*10000个源字符串并最小长度为10(没有最大长度)的重复字符串,看看速度.
你可以直接运行我的程序,改一下存放文件的C:\\result.txt就可以了.我现在没有LINUX/UNIX,执行不了你的程序.
你的程序完全正确吗?我觉得很难验证.icon_smile.gif

1. 经过与出题人交流， 此题有如下条件：
  
1) 查找最长重复匹配串，先到先得
2) 匹配串不能重叠
3) 每个匹配串必须包括全部 ACGT 四个字符。（这是才是有效的基因片断）， 所以 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 不算重复匹配串

真实的 DNA 文件， 重复匹配串的最大长度一般小于 100。
比如， 我用的 data1 (10000 字符, 正序重复匹配串的最大长度是 46, 逆序是 15）
data2 (100000 字符, 正序重复匹配串的最大长度是 43）
所以我希望你能用我的 data1 来在你的机器下测一下你的程序所花的时间。（因我没有编译器）

我的程序不能说完全正确 (最新版本)， 但到目前为止没有发现问题。
前面我说的测试 10 - 30 的长度， 不用理会， 测试 >;= 10 的就可以了.

2.  data1 (10000 字符) 的结果

CPU:  1.2G  P3,  Memory 384M, OS  UWIN 3.2,  AWK

正序匹配测试： 1 min 45 sec

1. 
   
2. 
   
3. Repeat: TGAGGTCAGGAGTTCAAGACCAGCCTGGCCAACATGGTGAAACCCC, Size: 46, Start Positions: 2679,2992
   
4. Repeat: TTGGCTGGGCACAGTGGCTCACGCCTGTAATCC, Size: 33, Start Positions: 1086,5893
   
5. Repeat: TGGCCAACATGGTGAAACCCCGTCTCTA, Size: 28, Start Positions: 5983,8614
   
6. Repeat: CCTGTAATCCCAGCACTTTGGGAGGC, Size: 26, Start Positions: 1613,2948
   
7. Repeat: CGGGCATGGTGGCTCACGCTTGTAAT, Size: 26, Start Positions: 2617,8526
   
8. Repeat: CAGCACTTTGGGAGGCTGAGGCAGG, Size: 25, Start Positions: 5926,8554
   
9. Repeat: GAACTCCTGACCTCAGGTGATCC, Size: 23, Start Positions: 3913,9062
   
10. Repeat: CGTGCCTGTAATCCCAGCTACT, Size: 22, Start Positions: 1241,8671
    
11. Repeat: TGAGGCAGGAGAATTGCTTGAA, Size: 22, Start Positions: 1271,6075
    
12. Repeat: GGGAGGCTGAGGTGGGTGGAT, Size: 21, Start Positions: 329,2654
    
13. Repeat: GAGGTTGTAGTGAGCCGAGAT, Size: 21, Start Positions: 1805,2832
    
14. Repeat: GGAGGTGGAGGTTGCAGTGA, Size: 20, Start Positions: 502,8727
    
15. Repeat: ACTCCAGCCTGGGCGACAGA, Size: 20, Start Positions: 541,1336
    
16. Repeat: GTGCCACTGCACTCCAGCCT, Size: 20, Start Positions: 2854,6130
    
17. Repeat: CTAAAAATACAAAAATTAG, Size: 19, Start Positions: 1708,8642
    
18. Repeat: AGCTACTTGGGAGGCTGAG, Size: 19, Start Positions: 2784,3093
    
19. Repeat: AAAAATACAAAAATTAGCC, Size: 19, Start Positions: 3046,6013
    
20. Repeat: AGGAGAATCACTTGAACC, Size: 18, Start Positions: 1778,8707
    
21. Repeat: CCCAGGCTGGAGTGCAAT, Size: 18, Start Positions: 3732,8883
    
22. Repeat: AAAGTGCTGGGATTACAG, Size: 18, Start Positions: 4558,9101
    
23. Repeat: ACTGCACTCCAGCCTGG, Size: 17, Start Positions: 1832,8753
    
24. Repeat: TCGCTTGAACCCGGGAG, Size: 17, Start Positions: 2812,3121
    
25. Repeat: TGGAGTTTTGCTCTTGT, Size: 17, Start Positions: 3713,8864
    
26. Repeat: GCCTTGGCCTCCCAAA, Size: 16, Start Positions: 1460,3940
    
27. Repeat: TATTTTTAGTAGAGAC, Size: 16, Start Positions: 4473,9015
    
28. Repeat: CCACCTCGCCTGGCT, Size: 15, Start Positions: 208,8993
    
29. Repeat: TAAACAAGGACTTTT, Size: 15, Start Positions: 1510,1556
    
30. Repeat: GGGTTTCTCCATGTT, Size: 15, Start Positions: 4490,9032
    
31. Repeat: AGACTCCATCTCAA, Size: 14, Start Positions: 2887,8781
    
32. Repeat: CTGCCTCAGCCTCC, Size: 14, Start Positions: 3802,8953
    
33. Repeat: GATTACAGGCATGC, Size: 14, Start Positions: 3827,8978
    
34. Repeat: TGTGGTGGTGCA, Size: 12, Start Positions: 436,1732
    
35. Repeat: ACAATGCTGTAA, Size: 12, Start Positions: 847,9825
    
36. Repeat: ACCCTGTCTCTA, Size: 12, Start Positions: 1194,5426
    
37. Repeat: TGAGGTCAGGAG, Size: 12, Start Positions: 5958,8588
    
38. Repeat: GCCTGTAATCC, Size: 11, Start Positions: 309,3081
    
39. Repeat: CAGCCTGGCCA, Size: 11, Start Positions: 374,1173
    
40. Repeat: GGGAGGCTGAG, Size: 11, Start Positions: 469,1128
    
41. Repeat: AGGCTGGTCTC, Size: 11, Start Positions: 1436,9051
    
42. Repeat: GTGTTTCTAAC, Size: 11, Start Positions: 2256,7173
    
43. Repeat: ATGAACAAGGG, Size: 11, Start Positions: 7604,9373
    
44. Repeat: AAGCAATTCTC, Size: 11, Start Positions: 8435,8942
    
45. Repeat: TTCTTTTTGA, Size: 10, Start Positions: 65,4308
    
46. Repeat: CTGTGAATAT, Size: 10, Start Positions: 260,6206
    
47. Repeat: CCCAGCTACT, Size: 10, Start Positions: 458,6057
    
48. Repeat: GATTTTCTAT, Size: 10, Start Positions: 633,9283
    
49. Repeat: GCTGTCATTT, Size: 10, Start Positions: 652,5261
    
50. Repeat: ATTAGTTTTC, Size: 10, Start Positions: 738,7084
    
51. Repeat: AAGTTTCAAG, Size: 10, Start Positions: 928,5153
    
52. Repeat: TTAGTTCTCA, Size: 10, Start Positions: 1955,6839
    
53. Repeat: TCAGCCAGAT, Size: 10, Start Positions: 1988,9888
    
54. Repeat: ATTTGCTTTT, Size: 10, Start Positions: 2246,9636
    
55. Repeat: TGAGCTCTTA, Size: 10, Start Positions: 3565,9590
    
56. Repeat: GCCCACATTA, Size: 10, Start Positions: 7007,8318
    
57. 
    

复制代码

逆序匹配测试： 1 min 7 sec

1. 
   
2. Reverted Repeat: AGTTTTTCTTTTTTT, Size: 15, Start Positions: 674,4303
   
3. Reverted Repeat: TCATTCATGGTA, Size: 12, Start Positions: 4999,9542
   
4. Reverted Repeat: TTCTCAGACTAA, Size: 12, Start Positions: 6843,7896
   
5. Reverted Repeat: AGGTGGGCGGA, Size: 11, Start Positions: 1641,2976
   
6. Reverted Repeat: GTCTCTTAAAA, Size: 11, Start Positions: 2591,8498
   
7. Reverted Repeat: TTGAGGTGACA, Size: 11, Start Positions: 5358,5856
   
8. Reverted Repeat: ACAGAATAAAA, Size: 11, Start Positions: 6222,6567
   
9. Reverted Repeat: ACTAGAGCTTG, Size: 11, Start Positions: 7340,8599
   
10. Reverted Repeat: GTTTTCTTAA, Size: 10, Start Positions: 230,8448
    
11. Reverted Repeat: TTTACTTTAG, Size: 10, Start Positions: 611,1360
    
12. Reverted Repeat: TACAAAGAAC, Size: 10, Start Positions: 871,2576
    
13. Reverted Repeat: GTTCTCAACT, Size: 10, Start Positions: 882,2497
    
14. Reverted Repeat: GTGAAACCCT, Size: 10, Start Positions: 1189,1469,4554
    
15. Reverted Repeat: AAGGACTTTT, Size: 10, Start Positions: 1515,2225
    
16. Reverted Repeat: CTTTTTCTGA, Size: 10, Start Positions: 1545,2382
    
17. Reverted Repeat: CAATTTGATC, Size: 10, Start Positions: 2094,4775
    
18. Reverted Repeat: TCAAAAAAGA, Size: 10, Start Positions: 2897,5675
    
19. Reverted Repeat: GTGACAACAG, Size: 10, Start Positions: 3172,4730
    
20. Reverted Repeat: ATTTAATCGT, Size: 10, Start Positions: 3597,9181
    
21. Reverted Repeat: AATATCTTTG, Size: 10, Start Positions: 5550,7952
    
22. Reverted Repeat: CCTGGGAAGG, Size: 10, Start Positions: 5563,9524
    
23. Reverted Repeat: TCTCAAATAG, Size: 10, Start Positions: 5620,9293
    
24. Reverted Repeat: AGTATTATCA, Size: 10, Start Positions: 5650,7393
    
25. Reverted Repeat: CAATAAATGG, Size: 10, Start Positions: 8800,9810
    
26. Reverted Repeat: TTGTACGTAT, Size: 10, Start Positions: 9563,9578
    

复制代码

3.  data2 (100000 字符) 的结果

当长度增加到 100000 时， 速度变的很慢， 我只测了正序， 而且没有完全
完成， 但可以估计时间。

由于存在的重复匹配串的最大长度很小， 我采用二分查找首先找到重复匹配串的最大长度
然后再循环至最小长度。 下面结果前面的

9 50002 0
9 25005 0
.

就是显示查找的过程。 找到重复匹配串的最大长度为 43 用时 67 min.
然后， 从 43 循环至 10.  每个长度用时约 5 min

总时间大约为 67 + 34 * 5 =  237 min  也就是大约 4 小时。

1. 
   
2. 9 50002 0
   
3. 9 25005 0
   
4. 9 12507 0
   
5. 9 6258 0
   
6. 9 3133 0
   
7. 9 1571 0
   
8. 9 790 0
   
9. 9 399 0
   
10. 9 204 0
    
11. 9 106 0
    
12. 9 57 1
    
13. 33 57 0
    
14. 33 45 1
    
15. 39 45 1
    
16. 42 45 1
    
17. 43 45 0
    
18. 
    
19. 
    
20. Repeat: ATTGGATCATTGATCTAATCCAACCACATAACTATAATTACAG, Size: 43, Start Positions: 25161,25204
    
21. Repeat: TCGGCCTCCCAAAGTGCTGGGATTACAGGCGTGAGCCACCG, Size: 41, Start Positions: 26357,75092
    
22. Repeat: AGTCTTGCTCTGTCGCCCAGGCTGGAGTGCAGTGGCGCG, Size: 39, Start Positions: 31148,69805
    
23. .
    
24. .
    
25. 
    

复制代码