Chinaunix

标题: 两道题，问了N多人，没结果，再问一下看看 [打印本页]

作者: bioinfor 时间: 2004-12-10 16:29
标题: 两道题，问了N多人，没结果，再问一下看看
1) Write a program to identify all the repetitive patterns in a string of
charaters (INPUT).  The string is only composed of A,C,G,T characters.  The
maximum length of string is 10000.  The minimum length of repeat is 10
characters. Output: position, size, and patterns.  Here is an example:
1)写一个程序，识别字符串中所有的重复片段(重复模式)，字符串由A，C，G，T组成，字符串最长为10000，随机产生。重复的片段最小是10个符串。输出：位置，大小，和片段。如下：
String:
TAAAAACTCGGGGT AAAAACTCGGGGAAAA
Repeat:
Repeat: AAAAACTCGGGG, Size: 12, Start Positions: 2, 15

解释：如这就就有两个重复(空格格开了)：T  AAAAACTCGGGG  T AAAAACTCGGGG AAAA
这两个重复位置分别在字符串的2和15位，大小为12

2) Write a program to identify all the INVERTED repetitive patterns (e.g.
TAACCG =>; GCCAAT) in a string of character (INPUT).  The string is only
composed of A,C,G,T characters.  The maximum length of string is 10000.  The
minimum length of repeat is 10 characters. Output: position, size, and
patterns. Here is an example:

写一个程序识别所有的反向重复，如TAACCG =>; GCCAAT，也就是前面的反过来就是后面的字符串。和上面一样，字符串最长为10000，随机产生，最小反向重复片段为10，输出位置，大小，和片段，如下：
String:
CAAAAACGAGGGGTTTGGGGAGCAAAAA
Inverted Repeat:
Inverted Repeat: AAAAACGAGGGG, Size: 12, Start Positions: 17, 2

解释：如上面，C  AAAAACGAGGGG  TTT GGGGAGCAAAAA
AAAAACGAGGGG和GGGGAGCAAAAA分别是反向重复，分别在2和17位上，大小为12。

作者: brilliantcn 时间: 2004-12-10 16:58
标题: 两道题，问了N多人，没结果，再问一下看看
求源程序吗？

作者: aero 时间: 2004-12-10 17:01
标题: 两道题，问了N多人，没结果，再问一下看看
^_^，又发帖子啦。下午闲的时候写了一个。这样做是犯规的，可是，最近没啥写的，看书又累了，挺郁闷的，随手抓过来就写了，当练习发泄了。班长见谅啊。

#include <stdio.h>;
#include <stdlib.h>;
#include <assert.h>;
#include <string.h>;
#include <time.h>;
#define MAX 100
#define TRUE 1
#define FALSE 0
#define INVERTIED
typedef int BOOL;
void make_queue(char *src);
BOOL str_check(char *str);
void do_vertied(char *src, char *str);
void do_invertied(char *src, char *str);
void str_change(char *str, char *tmp);
int main(void) {
char src[MAX], str[MAX];
BOOL flag;
make_queue(src);
printf("source queue: %s\n", src);
printf("input a string to search: ");
scanf("%s", str);
flag = str_check(str);
while (flag == FALSE) {
printf("Please input string with A, C, G or T!\n");
scanf("%s", str);
flag = str_check(str);
}
#ifdef VERTIED
do_vertied(src, str);
#else
do_invertied(src, str);
#endif
exit(0);
}
/*
* check the string input to show wether the string is comfortable.
*
*/
BOOL str_check(char *str) {
char ch;
int i;
assert(str != NULL);
i = 0;
ch = str[i++];
while (ch != '\0') {
switch (ch) {
case 'A' :
case 'C' :
case 'G' :
case 'T' :
break;
default :
return FALSE;
}
ch = str[i++];
}
return TRUE;
}
/*
* to make a comfortable source string.
*
*/
void make_queue(char *src) {
char tmp[4], *s;
time_t t;
int random, tip, size, i, pos;
assert(src != NULL);
memset(src, 0x00, MAX);
// init the tmp array.
tmp[0] = 'A';
tmp[1] = 'C';
tmp[2] = 'G';
tmp[3] = 'T';
// init the random seed.
t = time(NULL);
srand((unsigned int)t);
// make a temp space to store the source string.
tip = RAND_MAX%MAX; // to make balance to every number < 1000.
random = rand();
if (random >; tip) {
size = random%MAX;
s = (char *)calloc(size, sizeof(char));
if (s == NULL) {
perror("make_queue, s malloc");
exit(1);
}
}
// fill the store space.
tip = RAND_MAX%4;
i = 0;
while (i < size) {
random = rand();
if (random >; tip) {
pos = random%4;
s[i++] = tmp[pos];
}
}
// s ==>;>; src.
strcpy(src, s);
free(s);
return ;
}
/*
* to find the vertied string in the source.
*
*/
void do_vertied(char *src, char *str) {
char *pos;
int position[MAX], size, count, i;
assert((src != NULL) && (str != NULL));
size = strlen(str);
memset(position, 0x00, MAX*sizeof(int));
#ifdef VERTIED
printf("vertied string: %s, ", str);
#else
{
char *tmp;
tmp = strdup(str);
str_change(str, tmp);
printf("invertied string: %s, ", tmp);
free(tmp);
}
#endif
printf("size: %d, ", size);
count = 0;
i = 0;
pos = strstr(src, str);
if (pos == NULL) {
printf("no string in the source!\n");
return ;
}
while (pos != NULL) {
count++;
position[i++] = pos - src + 1;
pos = strstr(pos + size, str);
}
printf("position: ");
i = 0;
while (position[i] >; 0) {
printf("%d, ", position[i++]);
}
printf("\n");
return ;
}
/*
* to find the invertied string in the source.
*
*/
void do_invertied(char *src, char *str) {
char *tmp;
tmp = (char *)malloc(strlen(str));
if (tmp == NULL) {
perror("do_invertied, tmp malloc");
exit(1);
}
str_change(str, tmp);
do_vertied(src, tmp);
return ;
}
/*
* to change the sequence of the str string .
*
*/
void str_change(char *str, char *tmp) {
int len, i;
len = strlen(str);
for (i = 0; i < len; i++){
tmp[len-i-1] = str[i];
}
tmp[len] = '\0';
}

复制代码

作者: twen345 时间: 2004-12-10 17:29
标题: 两道题，问了N多人，没结果，再问一下看看
aero真是强人，pfpf！

作者: xhl 时间: 2004-12-10 19:37
标题: 两道题，问了N多人，没结果，再问一下看看
超过 4 亿个整数按照二进制方式存放到到一个文件中，对所有整数按照大小排序并保存到新文件中
========================================

写个 M 进制到 N 进制转换程序（'0'-'9'表示 0-9，大写 'A'-'Z' 表示 10-35）。假定 M<36，N<36，只做整数部分。

========================================

最近面了很多家公司。。。
我觉得这两到题还是比较有难度的。。。。

作者: sainux 时间: 2004-12-11 09:00
标题: 两道题，问了N多人，没结果，再问一下看看
还是C这边的大侠比较狠,呵呵~~~

作者: kj501 时间: 2004-12-11 09:23
标题: 两道题，问了N多人，没结果，再问一下看看

原帖由 "xhl" 发表：
超过 4 亿个整数按照二进制方式存放到到一个文件中，对所有整数按照大小排序并保存到新文件中

用hash最方便。

作者: THEBEST 时间: 2004-12-11 12:45
标题: 两道题，问了N多人，没结果，再问一下看看
to aero:
这个程序似乎不符合要求,楼主是要随机产生一个10000长度的字符串,然后自动查找所有同一样的字符串的开始位置.我想了一下,觉得处理起来不难(只是一些细节容易出错),但效率嘛....

作者: cellar 时间: 2004-12-11 13:04
标题: 两道题，问了N多人，没结果，再问一下看看
有意思，效率应该不是问题，楼主的问题一看就知道是搞基因工程的，搞基因工程的都有大型机的：）

作者: bioinfor 时间: 2004-12-11 19:45
标题: 两道题，问了N多人，没结果，再问一下看看

原帖由 "THEBEST" 发表：
to aero:
这个程序似乎不符合要求,楼主是要随机产生一个10000长度的字符串,然后自动查找所有同一样的字符串的开始位置.我想了一下,觉得处理起来不难(只是一些细节容易出错),但效率嘛....

呵呵，是有点不一样，其实我觉得这个程序写出来要好好验证，因为有很多人为想不到的因素。其实这个程序要用几百条代码写出来好象不是很容易，一家之言。

作者: THEBEST 时间: 2004-12-11 21:20
标题: 两道题，问了N多人，没结果，再问一下看看
需要那么多吗?不觉得,明天写出来,但测试到底是否完全正确就不知道有什么办法了.

作者: aero 时间: 2004-12-12 10:10
标题: 两道题，问了N多人，没结果，再问一下看看

原帖由 "THEBEST" 发表：
to aero:
这个程序似乎不符合要求,楼主是要随机产生一个10000长度的字符串,然后自动查找所有同一样的字符串的开始位置.我想了一下,觉得处理起来不难(只是一些细节容易出错),但效率嘛....

呵呵，我的字符串的长度也是随机的了<100。要是固定10000长度的，其实更好生成。不过，作业题至于嘛？而且，怎么往屏幕上打啊？

作者: THEBEST 时间: 2004-12-12 21:39
标题: 两道题，问了N多人，没结果，再问一下看看
写了一下,但还有问题,随机生成的全是一样的字符呢?当然这样情况并不是不能存在,总的讲,程序还有是问题,只是一个思路而矣.

#include <iostream>;
#include <fstream>;
#include <string>;
#include <vector>;
#include <map>;
#include <set>;
#include <ctime>;
#include <cstdlib>;
#include <algorithm>;
#include <exception>;
using namespace std;
const int SizeMax=10000;
char RandChar();
void RandString(string &s);
void OutputStatics(ofstream &out,
const string &s,const map<string,vector<int>; >; &sameStr);
void FindSameStr(const string &s, string::size_type minLen = 10);
void FindSameReverseStr(const string &s,string::size_type minLen = 10);
int main()
{
ofstream test("C:\\test.txt");
string testString;
RandString(testString);
test << testString << endl;
FindSameStr(testString);
// FindSameReverseStr(testString);
cin.get();
}
char RandChar()
{
srand(time(0));
switch(rand()%4)
{
case 0: return 'A';
break;
case 1: return 'C';
break;
case 2: return 'G';
break;
case 3: return 'T';
break;
default:
cout << "Error and Exit Prog\n" << endl;
exit(-1);
}
}
void RandString(string &s) {
for (int i=0; i<SizeMax; ++i)
s.push_back(RandChar());
}
void OutputStatics(ofstream &out,
const string &s,const map<string,vector<int>; >; &sameStr)
{
out << "Source String:\n" << s << "\n\n" << endl;
map<string,vector<int>; >;::const_iterator iter = sameStr.begin();
out << "The Same String in the Source String:\n" << endl;
while (iter != sameStr.end())
{
out << iter->;first << " Length: " << (iter->;first).size() << endl
<< "The Start Pos: ";
for (vector<int>;::const_iterator vi = (iter->;second).begin();
vi != (iter->;second).end(); ++vi)
out << *vi << " ";
out << endl;
}
}
void FindSameStr(const string &s, string::size_type minLen)
{
string::size_type idx = 0, maxLen = minLen, pos = 0;
map<string,vector<int>; >; mvs;
set<string>; SetStr;
string tempFound, moreLenFound, Found;
while (1) //重要:前面的字符串没有同样的时候还需要找后面的,直到最后一个可能的字符串
{
tempFound = string(s,idx,minLen);
//只要能找到一个同样的就行
while ( (s.find(tempFound,idx+tempFound.length())) != string::npos)
{
Found = moreLenFound = tempFound;
//是否存在更长的同样的字符串
while (1)
{
moreLenFound.push_back(s[idx + maxLen++ - 1]);
//再也找不到更长的字符串了
if (s.find(moreLenFound,idx + maxLen) == string::npos)
{
SetStr.insert(Found);
idx += (maxLen - minLen);
maxLen = minLen;
break;
}
Found = moreLenFound; //保存最长同样的字符串
}
}
if ( (++idx + minLen) == SizeMax )
break;
}
//处理SetStr中的字符串,找到所有共同的字符串的起点
for (set<string>;::iterator iter = SetStr.begin(); iter != SetStr.end(); ++iter)
{
pos = 0;
while( (pos = s.find(*iter),pos) != string::npos)
{
mvs[*iter].push_back(pos);
pos += (*iter).size();
}
}
ofstream coutstr("C:\\sourceStr.txt");
OutputStatics(coutstr,s,mvs); //可以直接输出到cout上
}
void FindSameReverseStr(const string &s,string::size_type minLen)
{
//在适当的地方把被查找字符串反转一下,和上面的一样处理,也可以来个bool参数
}

复制代码

作者: THEBEST 时间: 2004-12-12 21:43
标题: 两道题，问了N多人，没结果，再问一下看看
楼主,还没看你发的那个就写了一下,效率很低.

作者: eagerly1 时间: 2004-12-12 22:19
标题: 两道题，问了N多人，没结果，再问一下看看
我不认为以上2位的程序已经完美,楼主的意见呢

作者: THEBEST 时间: 2004-12-12 22:35
标题: 两道题，问了N多人，没结果，再问一下看看
[quote]原帖由 "eagerly1"]我不认为以上2位的程序已经完美,楼主的意见呢[/quote 发表：

我说了我的程序是有错的

更谈不上完美.

明天再改改.

作者: eagerly1 时间: 2004-12-12 22:59
标题: 两道题，问了N多人，没结果，再问一下看看

原帖由 "THEBEST" 发表：

我说了我的程序是有错的更谈不上完美. 明天再改改.

虽然我写不出这样的程序,但我愿意在这里看到详细而深入的讨论.
学习大家,包括你的敬业精神.

作者: bioinfor 时间: 2004-12-13 21:56
标题: 两道题，问了N多人，没结果，再问一下看看
[quote]原帖由 "eagerly1"]我不认为以上2位的程序已经完美,楼主的意见呢[/quote 发表：

我个人认为已经很不错了，只是这两个题主要是考算法而不是语法，所以我个人认为如果不搞算法的人能做到这样已经很不容易了，至少我根本达不到这种高度。

作者: THEBEST 时间: 2004-12-13 22:31
标题: 两道题，问了N多人，没结果，再问一下看看
程序终于调试好了,但存在一些必需说明的问题:
1>;我机子性能不好,产生10000长度也不知道结果到底是否正确.
2>;我用10位最大长度及至少4位一样长度的相等的字符串试了结果是正确的.
3>;希望帮忙测试一下.
4>;

2 C:\ProTemp\FindSameStr.cpp:128 [Warning] no newline at end of file

复制代码

这个问题到底是什么引起的?如何解决.好像运气不好就会有,看到有警告不爽.

5>;程序效率很低,还可以改进很多.但需要时间.
6>;为什么随机数都是一样的?程序哪里错了,在产生随机数上.
7>;代码如下:

#include <iostream>;
#include <fstream>;
#include <string>;
#include <vector>;
#include <map>;
#include <set>;
#include <ctime>;
#include <cstdlib>;
#include <algorithm>;
#include <exception>;
using namespace std;
const int SizeMax=1000; //测试时改成自己想要的最大长度原串
char RandChar();
void RandString(string &s);
void OutputStatics(ofstream &out,
const string &s,const map<string,vector<int>; >; &sameStr);
void FindSameStr(const string &s, string::size_type minLen = 10);
void FindSameReverseStr(const string &s,string::size_type minLen = 10);
int main()
{
ofstream test("C:\\test.txt");
string testString;
RandString(testString);
test << testString << endl;
FindSameStr(testString); //测试时改成最小同样串长度,默认是10
// FindSameReverseStr(testString);
cin.get();
}
char RandChar()
{
srand(time(0));
switch(rand()%4)
{
case 0: return 'A';
break;
case 1: return 'C';
break;
case 2: return 'G';
break;
case 3: return 'T';
break;
default:
cout << "Error and Exit Prog\n" << endl;
exit(-1);
}
}
void RandString(string &s) {
for (int i=0; i<SizeMax; ++i)
s.push_back(RandChar());
}
void OutputStatics(ofstream &out,
const string &s,const map<string,vector<int>; >; &sameStr)
{
out << "Source String:\n" << s << "\n\n" << endl;
map<string,vector<int>; >;::const_iterator iter = sameStr.begin(),
iter_end = sameStr.end();
out << "The Same String in the Source String:\n" << endl;
while ( iter != iter_end)
{
out << iter->;first << " Length: " << (iter->;first).size() << endl
<< "The Start Pos: ";
for (vector<int>;::const_iterator vi = (iter->;second).begin();
vi != (iter->;second).end(); ++vi)
out << *vi << " ";
out << endl << endl;
++iter;
}
}
void FindSameStr(const string &s, string::size_type minLen)
{
string::size_type idx = 0, maxLen = minLen, pos = 0;
map<string,vector<int>; >; mvs;
set<string>; SetStr;
string tempFound, moreLenFound, Found;
while (1) //重要:前面的字符串没有同样的时候还需要找后面的,直到最后一个可能的字符串
{
tempFound = string(s,idx,minLen);
//只要能找到一个同样的就行,注意是从该被找字符串之后开始找
while ( (s.find(tempFound,idx+tempFound.length())) != string::npos)
{
Found = moreLenFound = tempFound;
//是否存在更长的同样的字符串
while (1)
{
moreLenFound.push_back(s[idx + maxLen++ - 1]);
//再也找不到更长的字符串了
if (s.find(moreLenFound,idx + maxLen) == string::npos)
{
SetStr.insert(Found);
idx += (maxLen - minLen);
maxLen = minLen;
tempFound = string(s,idx,minLen); //构造好下一个被找字符串
break;
}
Found = moreLenFound; //保存最长同样的字符串
}
}
if ( (++idx + 2*minLen) >; SizeMax )
break;
}
//处理SetStr中的字符串,找到所有共同的字符串的起点
for (set<string>;::iterator iter = SetStr.begin(); iter != SetStr.end(); ++iter)
{
pos = 0;
while( (pos = s.find(*iter,pos)) != string::npos)
{
mvs[*iter].push_back(pos);
pos += (*iter).size();
if(pos >;= SizeMax)
break;
}
}
ofstream coutstr("C:\\sourceStr.txt");
OutputStatics(coutstr,s,mvs); //可以直接输出到cout上
}
void FindSameReverseStr(const string &s,string::size_type minLen)
{
//在适当的地方把被查找字符串反转一下,和上面的一样处理,也可以来个bool参数
}

复制代码

下面的我用的10,4测试后的结果:

Source String:
AAAAAAAAAA

The Same String in the Source String:

AAAA Length:  4
The Start Pos:  0  4

AAAAA Length:  5
The Start Pos:  0  5

作者: THEBEST 时间: 2004-12-13 22:37
标题: 两道题，问了N多人，没结果，再问一下看看

原帖由 "bioinfor" 发表：

我个人认为已经很不错了，只是这两个题主要是考算法而不是语法，所以我个人认为如果不搞算法的人能做到这样已经很不容易了，至少我根本达不到这种高度。

如果光是学语法我觉得没多大意思.我觉得关键还是看如何解决问题,一种用某种语言来解决实际问题的思路,但这题有很多需要考虑的细节,我一开始也没想到,调试程序时发现很多地方需要控制.个人看法.

作者: THEBEST 时间: 2004-12-13 22:51
标题: 两道题，问了N多人，没结果，再问一下看看
啊,发现程序处理有误.明天再改.是应该保存一下第一次找到的位置然后再在最后全部查找的时候从这个位置开始找而不是都从第0个位置往后找,这样会出现大重复序列中出现小重复序列.今天没时间了.对不起了........

作者: bioinfor 时间: 2004-12-13 22:56
标题: 两道题，问了N多人，没结果，再问一下看看
[quote]原帖由 "THEBEST"]啊,发现程序处理有误.明天再改.是应该保存一下第一次找到的位置然后再在最后全部查找的时候从这个位置开始找而不是都从第0个位置往后找,这样会出现大重复序列中出现小重复序列.今天没时间了.对不起了........[/quote 发表：

THEBEST兄，你能考虑到这一点就证明你已经很厉害了，至少快接近正确了，呵呵，我相信你一定可以的!

BTW，THEBEST兄你是不是看错了，序列是小于10000，重复的序列要至少大于10啊，你测试的怎么是10个长，重复的是4和5呢？还是你只是拿短的片段测试了一下？

作者: THEBEST 时间: 2004-12-14 08:24
标题: 两道题，问了N多人，没结果，再问一下看看
今天起了个大早,不过还是比较失望....
to bioinfor :
我知道,我前面程序里说明了要真正符合你的要求要改两个数据,我只是用这个短的来测试一下的.再发一个有一个问题未处理的情况:

#include <iostream>;
#include <fstream>;
#include <string>;
#include <vector>;
#include <map>;
#include <set>;
#include <ctime>;
#include <cstdlib>;
#include <algorithm>;
#include <utility>;
using namespace std;
const int SizeMax=10000;
char RandChar();
void RandString(string &);
void OutputStatics(ofstream &,const string &,const map<string,vector<int>; >; &);
void FindSameStr(const string &, string::size_type = 10);
void FindSameReverseStr(const string &,string::size_type = 10);
int main()
{
srand(time(0)); //应该放在这里(其它某些地方也可以),居然犯这种错误.:p
string testString;
RandString(testString);
FindSameStr(testString);
// FindSameReverseStr(testString);
}
char RandChar()
{
// srand(time(0)); //因为每次"种子一样"的话产生的第一个随机数就是一样
switch(rand()%4)
{
case 0: return 'A';
case 1: return 'C';
case 2: return 'G';
case 3: return 'T';
default:
cout << "Error and Exit Prog\n" << endl;
exit(-1);
}
}
void RandString(string &s)
{
for (int i=0; i<SizeMax; ++i)
s.push_back(RandChar());
}
void OutputStatics(ofstream &out,
const string &s,const map<string,vector<int>; >; &sameStr)
{
out << "Source String:\n" << s << "\n\n" << endl;
map<string,vector<int>; >;::const_iterator iter = sameStr.begin(),
iter_end = sameStr.end();
out << "The Same String in the Source String:\n" << endl;
while ( iter != iter_end) //不能直接简写为iter++,下面用到iter->;first
{
out << "\"" << iter->;first << "\"" << endl
<< " Length: " << (iter->;first).size() << endl
<< "The Start Pos: ";
for (vector<int>;::const_iterator vi = (iter->;second).begin();
vi != (iter->;second).end(); ++vi)
out << *vi + 1 << " "; //不以0(以1)为字符位置的开始
out << '\n' << endl;
++iter;
}
}
void FindSameStr(const string &s, string::size_type minLen)
{
string::size_type idx = 0, pos = 0, maxLen = minLen;
set<pair<string,string::size_type>; >; SetStr; //元素为字符串与开始查找的位置对
string tempFound, moreLenFound, Found;
while (1) //重要:前面的字符串没有同样的时候还需要找后面的,直到最后一个可能的字符串
{
tempFound = string(s,idx,minLen);
//只要能找到一个同样的就行,注意是从该被找字符串之后开始找
while ( (s.find(tempFound,idx+1)) != string::npos)
{
Found = moreLenFound = tempFound;
//是否存在更长的同样的字符串
while (1)
{
moreLenFound.push_back(s[idx + maxLen++ - 1]);
//再也找不到更长的字符串了
if (s.find(moreLenFound,idx + maxLen - minLen) == string::npos)
{
SetStr.insert(make_pair(Found,idx));
idx += (maxLen - minLen);
maxLen = minLen;
tempFound = string(s,idx,minLen); //构造好下一个被找字符串
break;
}
Found = moreLenFound; //保存最长同样的字符串
}
}
if ( (++idx + 2*minLen) >; SizeMax )
break;
}
map<string,vector<int>; >; mvs;
//处理SetStr中的字符串,找到所有共同的字符串的起点
for (set<pair<string,string::size_type>; >;::iterator iter = SetStr.begin();
iter != SetStr.end(); ++iter)
{
pos = iter->;second; //不是从0开始找而是从被查找字符串的开始位置开始找
while( (pos = s.find((*iter).first,pos)) != string::npos)
{
mvs[(*iter).first].push_back(pos);
if((pos++) >;= SizeMax)
break;
}
}
ofstream coutstr("C:\\result.txt");
OutputStatics(coutstr,s,mvs); //可以直接输出到cout上
}
void FindSameReverseStr(const string &s,string::size_type minLen)
{
//在适当的地方把被查找字符串反转一下,和上面的一样处理,也可以来个bool参数
}

复制代码

我运行一次后的情况如下:

Source String:
TAGCAGCAGGTTTACGGACACCCTCCTCTCGGCTACTGCTAGTGACGGGGCGCTGCGAGGCGCAGACGGCAAGGTTCTAGCCAAACGTATGCATCGATATTTTGAGAGAGAACGGGGCCTCCTTCCTACAGAAACGTGGATGGGACGATAAAGAAGGAGATTGGATTGCCAAAGCAACATTGTGAGCAAATAAACAGGCATATGGTCATACGGTCGCATCTCCATGGGATGAGTGGCGTAAACCCGTTTGGATGCGAGGCCTGAAGGCCCTTTGTCGCACAACCCCTAGACACGTGTCTGCACGAGACGGCCGGAATAGCTAGTATGGGAAGTCTAGAAGGGGGTTCGTAGGGGGGGAGGAGCATGACTTGGCCGACAGGTCCGTCAGTTAATATATAGCTAGTGGGATCTACGACGGCGTCTTGGGGATCCAACATTCACGCAACGTTCATGGCACACTGTTATCTGTGATTTATAACCTGGTCCGGACCGCACTATTACAGGCTTCAACGACTAGAACTTCAGCGATAGGTCATTAGAGCTGTCGGGCACGAGTTTTCCGTCACCCCAGGCGTGCATTGCATCCACGGTGAGTTATGATATGCCACAATCAAAGAGGGCGACGACTTATCGTCCGATTGGGAGGATAGAAGTGACAGGCCTTATTCAATCCCTGTGTATTACTAGTTGGGTATTGGCAACCGTTTCGGCTGTTAGTAATCAGTCGTCCAGATAGTGGCCATAGTAGGGTCATCGGGCCTAAGCCCGATTATCCCCTCGTGACAGATCCTCGTAAAAACAGGAAAGACTGACGGCGTGAGTCCAGAATCATGTAAATTCCGACAAGAGCGCGATTTAGTACGCGGCCTATGACTTAGTGAGCTGAAGGGAACTCCAGACCCTCAAGACCGAAATCCTCTCAGTAGGCACGTGAGCATCATCTAGATTGACCAGCCACACGCGAGCCTAGGGGGCAGGCGTACATAAAACAATGCGGGAGACGGTACAAGTCTAACGCCTGGCGCGTAAGGGATAAAGGTCAGAGCTGCTCTCAATCATGCAATACGCGCCCTTCTAGCCAAGGCTCAATCCGCCGATAAGCCGAAGTCGTGTCATGGTAAATACCGGCCTCGGTTGTCTCACAGCTTATTTTTGTAAGTCTTCAATTTATAACGTGGCATAAGTACTGCGGCATTTGAGCTACGCTTCGCCTGTAGGCTGCCGGCATGGGAGTTGTATCAGCTCATCTTCTGCAAGTCGTGTGCCCTACTAAGGATACGCCTTCTTGTTTGCTAACGCCTGGATGTTGACGGCTATTCGTAGGACAAATATGCCGTGAATCGCCTTCATTTACCTATCACTCCTTACTCTAATCTGGATACAGCCATCGTTACCAAAGCTAGGTGCCCAACTTCGCCACTTTGCATTTTTGGTCGTCTGGTTTCTGTGCCCGACTACCGGGCCGGCCTGGTCACCGCGGTCGATCACGAAGATCCGCCCCTTGTTAATTCGAAACAAACCCGGATGTGTTCACCCGTTTGTATCAGCGTTCGTTGAGGGGGAGAACATGAGATTCGTCGGATAGATGTTCGGAGGCTTGTGAGGCCCAGCGGCAGTGATCAATTGCATAGTAAGGGGTGCCCCAGTAGGCAGTTGTTCCGCTTAATGGCAAGTCCGCTCAAAGGCCGTCAAGTCTCGGTCACATGTAGCCCATCTGGTTAGCCTGCCCCAAGCGCCAAGTCCCCCGGAGAGAAGAGGGAGTACTCGAGGTCCGGACAAACCCGCAAGCGCCGGTTTACTAAGTTACGTCGTGGCTCCGGCAGGATCCGGCACGCTTTCTTACGCGCGGGAATGAGAGCTATTGTTCGAGTACCACACCGGGACCCAGGGTCCGGGCAGGGTTACTCCCTATTGAACCCCGCCACATTTGTGCAAATAACGAGGATACCCATACATACCCAGATGGGTTGGCCTAGCGCCTGAAATTTGCGCGTTTTAGCCGTCACGTGGGTGCGCGTAGAAGCAACCCAAGCAGGGGACTCCTGAGCTCTGACTAGACCCATTATAATGACACTCTTTCCACTTGGTCACACGATACACTCCGCAGGCACTCCGTGCCATACCGATGGATTGGCCGTGCAGCCACCATTAGCAGACTGCTCCCATCCACTTAATTACTGATTCTAAGCGATCACTCGAGCATTCTGTTATTATCGGTGGCTTAGATGCAGAGGCCTTTTACGCGCGAAGCATAACCTACAACAACTCGTGGGTTAAGTTGGACGGGCGTACTAGCCGGATCGCTTTGCGAACAAAGCGAACGAAGATTACCATTTGCGCCCAGATACTCTTCCTACACTAGAAGGGATCTAATACGGCACCGAATGCAACTGTCGGGTCGTTAGTTGCATGATGGCGACTGCGAAGGTTCATGCTTGGAAGCGACAGATCGAACCGGTAACCAGTGTTAATTAACCAAGCTAACAAGAGCCTTGGTGCAGCGAGGTCTACCAAGCCATAGTTATGCAGTTCCCACCTTAGAATGGGTAGCAATTCAGGCAGTGGTCCACTGTGACCTCCCTTCGAGACTACTGGTTCGCTGAGAAGGGCGAGGCTAAGGACTCACACGCGTGTGATTCTGCGTGCGGGATGATAAACATCAGGCAAAGTGGTAAGCGGTATCCCGTGCTTCGCCGAAGGTTCCTTCCAGTCTTGGATTACGAATGAAACGTCCCTACCCCCGACGCCTTCCTAATGCGTTCCTTTGCAATCCTGCTGAGTCCCGTTGCTATTCGATGCGGGAGATATGATGAAGCACACTAGCGCTAAGGGGCTGTTTGATAATTAAATTCAATAGCAGGTCGAGCTACCTTGAAGTAGGACCATAACAGTCAACAACCCGGCGAGTTAGTGTGGTAAGCTAGCTGTGCAGAGTACGTAAGCAATCTCAACCTATGGCAGTGATAACTCGTTAGAAGTAGTACCCTGAGCCATGGCGATGGCCTAAAGGTCTCTTCAAATTACACACCGAGCAACTAAGGTGTGGCCCTAAAATCGCGACCTGACATCCGCCTACACTGCCGGCTCTGTCTATGATTCTATCGCCATGTCTCTATAGTCCGATGACTGAGGACCTTAGGGAGGCCGGTGATCTCTTTTAGCATCCATACTCGATGCTCTATGTAGATTCACCCGTTCTGGATAATTTGCCTCCCTATGTGTCAAGCCGGCCTCGAGCTGGGCCATGTTGTAAGGCAGCCTATTCTGATCTGGTGCAGCCAGGCGCGTTTCTATAAGAGAGAGTTCTAAGCTGATGGTGGTGCAGGGACGACCGAGTCCCGTTATCAACTGGGGTTGTCAGGAGTTTGAGTACCGCGGTGAGCTGGAAGAGTCATTAGATCTGCCATCTGAACATGCCTAAGCGGTCAACGGCTGCGTCAGAATGCCTCACGGACACCCGTGTGGTGTATCGTTGGCCTACACGGATCGAAACGTTTTTAAATAGATCATATCGCCTAGCCCCTTCTCATATAGGCTTTCGACTCCCGAGTCGACCTTTCCGGACATGTACCTACCCAGCTAGACAAAGTGGGGATTACGAGGCGTCACGATTGGTTTCACGACTCTCTACCTTCGCCAACAGGAGTAGTCTGATCAATCTCGTCCTGTCTCCGCCGGTCACTTTCAGCTTTCTCCACATCCGAGAACCATGTCTAGCGATCTAAGGGGTTCCTAAGCAACGGCCTTACATAAACTTCAGCGATAAGCGGCCGCCAAGCCTCTCCGGAACTCTAACGATATAGACATTGACGTCTTTACTGTCATTTTTGAATCTGACGAGTAATATTAGTCCATTCAAGATACACGGAGGCAAGGGGGAGATCATAAATACTAAAAGAAGACCATGAAGCGACTACTGCGATAGTAACGACATACGTATCGTGCGTCATCCGGAATATCGTTAATCAGGGCCACTTACATAGCATTAACGATTACCAAGAGCAACGCCAGCTGCTCCCAACATAGCCGCCTAAAATCTATCCCACCGTCGCGTGCCGGTCTGAGACAATACCGTTGCGTTTCGAATTGGATCGGAGGAAACATTGTAGCGACGTTCAATTCTGGGTTCCGAACATCGTGGGTAGATACGAAAAGGATGGCGTCGATATGTTAACTATGGAAATCTGGTAGAAGGGAGGGGGATGTCGCATAGAAGGGGTTGTCAGATATACAGGAGTGATTTTTTTTAATTACTGTCACAGGGGCAAGTCCATGGTCGGCGCCGCAGTGTTTCTACATGACGGGGTCTGACGCTCCGGCGAACAGCTTAGTTTAGTGTACGGGATCAGAGATAATCGCAGGGGTGACGACAGATCCACCTGAGGGTGCCCGACGTACCTTAGATCAATGAAGCTTTGACAGCCTATTGGACGGCAGCCCCTCGCCTTGAACGTAGGGCACTCGTCTCCACATCCGGGCTTTGCTGTAAATACCTTGGAGGCCTAGTATTCGGATCTAGTTGGTGAGTTGTTTGAAGGCCGGTCTTGCTCATGACAAATGGTCCTCGGATTAGCGTGAAGCACCCCCTACGATCCGGTCGGAGCTCGATTATGTGAATCAAGGGTGACAATGAAGCCGAATTTATATCTAGACAATAACTCAACGAGTATAAAGCGGATTGCAGATATTCCGCGCACATTAGCTTGCACTTGGGGGTTATCTTCAAGCTAACCCACCAAGGCGGCGACAATGCGACGAGTCTGGTCATCTCCTCCAATTGGCTAGAAATTGGAGCCGGGAGCCATCATATTCAACGGTGATACTGGAGGACAGATTCTGTTTATATATACTCGCACCCTGAGGTAGATTATCTTAGCTCTTAGGCAGATTAAGCCGACATATCAGTGCTTTTCCATGGACGGACCGCCCCGTAGCAGGACGCTCCTAATTGTAAGTGTGGCATTTTGGGCGAGTAATATGGTTGTTTAAAGTTAGACAGCGCGCTGTCTGCACGTTGCGTGTGTATACGTCCCTCACGAGCGCGTTAACGCCGGCGGTATTCAGCGCGCTGGGATATATAAAACTGCCGCTAGCTCCCGGCCGCAACTTTTATGATATGTAACGACCCCTACGTTAAGAGGAGGGTCATCCCCGCCGTGTCCGCCTGGGCTGACACCAGTTAGCTCTTGAAGGTAAATGATGTGCCGCACAAATACTGAGGAAGGCTGCTAACCTGCTATAGGTGAACGCAGATCTGTTCGCAAGGCGAACGTGCCGCCTTGGCGACGTATTCACTCCGTGACTGGCCGTACCATCTAAGTGAACTTGCCCAATGAGTCATCATGCTCGATTTTCGGTTAATGGAAGTCTCACCGTCTCGCGGGATTTTACCCATTTCCACGTTCCGTCTCTTGAGCACGGGCGACCCGAACAGACCGTGACAAAGGTCCAAGACGCCTATGGAACTATACCCAGGAATGGCATTTACATTGATCAACCGCTGTAGGTTGAGTCAGGAATCGCCAGGGAACTCTTACCCCCGATACCGCCCCATGCGCTCAGCCGTTACGGATAACCCGCCGCGCGGAAGACACCGTAAAGCGTTGACGAAGGCCTATAACGCTAAGCGGGTCCCGGTTGTAGCCAAGGCCACCACAGATGCGCGAGCCGGCATCTACTCCGACATACAAGTTCATGACCGAAACGCTAGCAGAGGGTTTAGCCCCTATGACTCGGGCCCGAACGATTTGCGAAACAGAATGACGCTATTCGCGAGTGGATAAGCCAAAAGAAAAGCTAACGGCAGGTTGTGGCCTCGCCGTGTAAGTTACCGAAGCGGGCTTAACTGCAGCATTCGCGAACCTAGGGTTTCAGGGGATGGCTGTTGTGACCTTATCACAGCGTGTTCGCATGCGGACTATCGTGCTATGCAGAGCGGTACCAGTGACCTCATATCAGGGATCGTTAGATGAAATGAGACAGCTCACACCAGGACTCATGACTTCGGTCTTATGGGCTGTCTGGAGGGACACGGGTGTCCCTAGAGCATTGGCAACGTAAATTAGAATGGTCGGCCCACGACCCTACAATGTCGTGAACACACGTGGTAGTTGCGCATCCGACCACCACGACGCGCAGATACGTGTCCAACTAACGTGACTCGGTCTCCCTGCCTGAGTCACCTGACCTTCCTTGATAAGGAGTTCGCCTAGGAATAACGCCTAGGCCGCAAATGGGTGTTTTTAGTGGAGCTATTGTGAAGTACGGTGCAAAACAAGCCCAAGTTCCCGGGCCGCGATTTATCGGCGAGTGTTGGAAAGCGCCGTCTAGCCCAACTTAATACACTCCCCAGACGACTTTCCTGCCGAGCCGCCGTAGACATTGCCGTTTCATTCACGGTGCCCCCTAGAAAAGGGATATACTGAAACGAAACTATCATGCTACCGAACTCTCTAGGGACCATGGTCTAGGCAGCCTGTGTCATATATTTAGATAGCCAGGGGGGATTGATTAAGATCACCCCGCAGGGATGTCCTCGCTGGCATGTCCTACTGTCTGGCCCTGATTTAAACTCCTCCGGCTTGCGCCCATAGATGTACTTGTGGCGTAGTACTGATTTACTGCGCCTCATCGTTCCCACCAAGACATCAGCGTGGTACAGGAACCTGCTCTACGAGGGATAGCAAATGAAGTAACAGAGTCTAGTAGTCAGCAGTTGATATGTGACGTTGACAGACAACTACGTATTTACGTTGCCTACGAAACATATGGAGCCTGAACAAAACCCAGAAGGAGTCACTGCTAACCCATGGGAACAAGGTCTACCCATGCCATTACACAGGCCCAGGGGGCTACTACCTGATTTGCACGACCGATCGGTGCAAGGTTACCCCTGACAGACGTTTCTGTCGGTTCATTCCTCGCGTTACTCCTGGGGTTACACCTGCAATGATCATAACTTATGAAATAGACCACTCGTAAGTATAGTTGCGTGTTCCCATACACCTCCCAATTTCGTAGTATACTGCCCGAGTTATTGGTCTCCTTAGTTTATGGCCTTTTTACCGACCTGTACGTGGCGGTTTTGTTCACCCTGAGCCCCCCCACATACGGATCGAATTTGAGCTCTAACGCCAGGAGGCACGTACGCAGCTTTCAGGGGATAGTGACCAAAGCGCGTTACCGCTGAGCACTCATAGAATGGGGATGTTAGTATAACCGTTTAAGTGGGATGACGACCGCGTCTCACCGCTGCTTCAAAGAATTCAGTGCTTCAGAGCTAGCTATCGGGAGGAAGGCTAGGTTCCAAGGCACAGGGAAGGCCCTCGGTTTGAGGTGCGGATAGAAGCGCACGCCCCAACCAGTAGGAAGGGTGTTAAAGACGATCAGACCGGATTTCTACTATTGCGTCCGGCCATCCCTTGAAGTCCTGCCCCCAAGGTGTGGACTGGAAAGGCAGATGCGCGTAAGTTCAACACTTTGACACTCAGCCACTTGTGGACAGGAGTCTGGTCGCGTGACCTTAAACTTGGCAGGCGGGGAAGTCCTACGCATTCTCCCTTGATAGAGCACGAGAGACTACATCGGTGCGTATTAGCAGCGCAAGTTGGCCCCTTATTCTAGCCTATGTTTTCCTGTATGCCGTTATCGTATGCCGGGATGATGGTTTTAAGAGGCCTGCGGTGGAGTGAAGCGTTAAATGATGGATCTTAGCTGCCTAACTCCCGGTCTAGATTGAGTGTAGCCGGGTCACAGCGGTAATCCACGCTGCCAATTTTCGTATCTTTATAGGTTGGCACTTAAGTCATGTCGGACAACTAGTTTCCCACGTTTCAAATGTACCTCTCTCAATCGCTCCGCATCCAGCCCGGGACGATAGCTGGAGGATGGGTGTGAAAGCTCAACGTCAAGTAAAAAACGGCCGACTACCTTGGTGCCGTATGTGGTGTGAAAGGAATTCCCCTTTTTTGTAGCCTTATGTACGACGTATTTGGACACCTTCTTACAGCCTCAAGTGGATGGTTGGTGTACGCCGCCCGCTGTCGAGTGACGAAGCTTTCGAGCCATAGTAGCAAACCTGACCGAAATATAGTCCTTATTCACAGCGGCTCCATTTAATTCGCGCGCCTGGGTAGAACAGGGGTGTATTGAAGGGTTATCCGGGAGTCGGTACGTCGCTAATGTTGAATTTGGAGGCATTAGTAAGTCCACCCTTTACTGATACATATAAGGGGGTATTCCGCTCCTACAGTGAGAACCTGTGTCGTAGCGCTCACATTGGTGGCCTGTAAAACCCTGATAAGTAGCTGTTGAGGACTATTCCGCGTCCGGCAATCGCCCTGGTCATTGGAAGTGTACCCACACCAGTTCAAAACCGGCGCGAATACCTAGTGCTTTGTTGACTTCTCACTGATTTCGGTCCTTAAGACACTGACTCCCGCTCCACTCGGGGGCATTGGGCTCGCGTGTTGATAAGGTATCACCCAACGCGAGGGCGGAGTATAAGACAGTAGAGAACACAATTATCTCATTTAACGTATTGACCGCTGGTCTGCCTACAGTCTCTATACCTATGCGCATACGTGATCTGAACCGATCTTGGTCGAGACGATATAGCGGTACTAGACGTCTAAGCGATTGGCAATAGTAACATCATCCGTTACGCTTAAGGACGGCCTACGCCTGGTGTTTCGGACAAGGCGTCTCGGTGCAGTCCGTTTGACTATGGGAGCTTCGGCCTTTGACAGAACCCTGTGCTTAAAGTGAACTATCGTGGACTGGAACTTTCCCAAGATTGTGATATTCGGCTGCTGACCACCAATCAAAAGTGATAGGCTACGGGACGCAAAAGTGTCGGTGTCGCAAGTATAATGTTGAGAGCGGTTGAGCGCGATGCGTTGTATGCTTGTCGTCGATTTAGTGATCCGCCGCGGGCTCTTTTACATTATTATAGCTTGTTCTAGCATGAATATTACCTGAACTCAATTCATCATTGCATTTATGCCCAACTGCTCTATGACATGGCTACACAATGAGAGATCCGGTGAGGACAAATACGCGATCCTCGAAACCGGCATGGGCTTCGCGATGATGTAATCCGGAATTAGGCCGGTCGAAATCTCGATGAATACCAACTCAGATGGAGGCGATGACCGCTATGTGCTTATACGCTATGTCAAGCACTCTCTGACCTCGTTGTTTGGGAGCAAGAATCTCTGGCCATCTTTCCAAGTAGCGAACTTCAGGGGAAGTGGCGTCCGTATAGTACAATCGAGTGCTTGTCGGTGCTTACTATCGACACACCGCAATACTTAGCGTTCTCTGTACGCTCCCGGTCGGACCAGCTGACGATTTTGCGAGCATCCTAGAGCGAGGCGAAAGTACAATATCCCATTGTTAGAGCGAACTAGCATATCAGAATAAACTGTAGCATTCACGCACTCATTGTCTCTAAAGTGAAATATTTCCAGTCACGCGCCCCATAGCGTAGAGAAATGGGATGTCCCTCACTCGACTCTCTTATAGTTCGGACATAAATGTCCCTTCAACCGTATCGACCACCGCCCGGCGAACTGCTCAAGCCGTCCCAGTACCCTAATAAAAGACTCACAGACCCAATAACCGCACTTAACCTTAGCTGCCCTTGGTTCATTAGACGCGAAAGAAAGTTTCGCGCTTCAAAATACTCCCCTGCCGCTACTCTCTAAGCGGAACGTCCTGCAGGCTTCATTATGGGAAGGTCAACATTCATCCGATAGTTGGAACCCACTCAGGATAAGTAGTCCAGTCGCCCGTTTTTAGGAATTGCGGAAGGGGCGCCTGAGTACTTACCTCAGACCTCGACTCACGAAGTTCGGAGATAGACTCGTTCATATTTTGCGCACTCTGAGCACGTTGGGCTTTAGACCGAATGGCGAATCTGTCTTTATAATTTTAACCTCACCTAGCGAATCTAGAATTCGGGCAATAAACGTGCTCTTCATACGTAATTGGACAAGTC

The Same String in the Source String:

"AACTTCAGCG"
   Length:  10
The Start Pos:  518  3753

"ACCCTGAGCCC"
   Length:  11
The Start Pos:  7091

"ACGGACACCC"
   Length:  10
The Start Pos:  14  3450

"ACGGATCGAA"
   Length:  10
The Start Pos:  3482  7110

"ACTTCAGCGA"
   Length:  10
The Start Pos:  519  3754

"AGGACAAATA"
   Length:  10
The Start Pos:  1322  9047

"ATGCGGGAGA"
   Length:  10
The Start Pos:  992  2796

"CAGATGCGCG"
   Length:  10
The Start Pos:  5656  7457

"CAGCGCGCTGG"
   Length:  11
The Start Pos:  5062

"CATTCACGCA"
   Length:  10
The Start Pos:  435  9431

"CCGGCATGGG"
   Length:  10
The Start Pos:  1222  9071

"CGAGTAATAT"
   Length:  10
The Start Pos:  3838  4970

"CTAACGCCTGG"
   Length:  11
The Start Pos:  1012  1293

"CTTAGCTGCCCT"
   Length:  12
The Start Pos:  9633

"CTTCAGCGAT"
   Length:  10
The Start Pos:  520  3755

"GAGCTATTGT"
   Length:  10
The Start Pos:  1856  6249

"GAGGAAGGCT"
   Length:  10
The Start Pos:  5218  7291

"GAGTCCCGTT"
   Length:  10
The Start Pos:  2778  3334

"GAGTCTGGTC"
   Length:  10
The Start Pos:  4757  7505

"GCCATAGTAG"
   Length:  10
The Start Pos:  739  8063

"GGGGTTGTCA"
   Length:  10
The Start Pos:  3351  4216

"GGGTTGTCAG"
   Length:  10
The Start Pos:  3352  4217

"GGTGTGAAAGG"
   Length:  11
The Start Pos:  7945

"GTGGACTGGAA"
   Length:  11
The Start Pos:  7443  8773

"TAGCCAAGGCC"
   Length:  11
The Start Pos:  5641

"TCCACATCCGG"
   Length:  11
The Start Pos:  4467

"TCTAAGCGATT"
   Length:  11
The Start Pos:  8629

"TCTAGATTGA"
   Length:  10
The Start Pos:  941  7729

"TCTCCACATCC"
   Length:  11
The Start Pos:  3692  4465

"TGTCTGCACG"
   Length:  10
The Start Pos:  295  5005

"TTAATTACTG"
   Length:  10
The Start Pos:  2171  4247

"TTATGATATG"
   Length:  10
The Start Pos:  595  5110

"TTCACCCGTT"
   Length:  10
The Start Pos:  1530  3188

"TTCAGCGATAAG"
   Length:  12
The Start Pos:  3756

"TTCAGGGGAT"
   Length:  10
The Start Pos:  5870  7155

"TTCTAGCCAA"
   Length:  10
The Start Pos:  75  1073

"TTGTATCAGC"
   Length:  10
The Start Pos:  1234  1539

"TTTCAGGGGA"
   Length:  10
The Start Pos:  5869  7154

可以看到,大超过10位时出现错误,也就是更长的重复字符串的处理有还不正确,(估计是哪个pos搞错了,

)

说明两点:
1>;输出顺序与查找到的顺序不同.
因为我用的是set,又防止会出现重复查找问题,但set又会自动排序,但也可以用普通容器,但最后要先排序再唯一,但我觉得效率差不多,可能后者更好.毕竟从10000的长度来看重复的数据没多少.

所以效率不会低.

2>;考虑特殊情况.
以10位长度及至少4位相同字符串时为例,如果源字符串为AAAAAAAAAA
那么找到的结果将是

输出的下标我从1而非0开始的)
AAAAA 1 6
AAAA 3 7
这样是否是大重复字符串里出现小重复字符串呢?我认为看你怎么看了,或者题目再给更清楚一点也行.
a)我认为不是:因为第二个重复串的开始及未尾位置也就是3,6并不在第一个大重复字符串的区间内,也就是1,5之内,所以不是大中包含小的.
b)可以认为是:如果你明确要求两个任何重复字符串不能有重叠那么这里可以算是子重复字符串了,毕竟这样也合理,不过这倒是可以更容易也更高效的处理了,只为pos的跨度更大.

而前面处理的情况更多些.

希望晚上再找出那个BUG.

我用记事本验证了一下,能找到的基本上是正确的(除了那个有BUG的更长的串),就不知道有没有重复串没找到的情况.

作者: THEBEST 时间: 2004-12-14 08:26
标题: 两道题，问了N多人，没结果，再问一下看看
有些BUG已清除,在程序中都给了注释.但那个警告还不知道是怎么回事,希望哪位兄弟帮忙指点一下.谢谢了.
to 楼主:我还没看你发的那个,所以没有新的想法.只是按照我一开始想的走下去了.等这个版本做好了再看看你给的那个会不会有更好的处理办法.

作者: assiss 时间: 2004-12-14 09:15
标题: 两道题，问了N多人，没结果，再问一下看看
你用的是什么IDE？
MINGW DEVELOP STUDIO？
如果是，那只需要在每个代码文件的最后加一个空行就OK了。

作者: THEBEST 时间: 2004-12-14 09:18
标题: 两道题，问了N多人，没结果，再问一下看看
谢谢,用的是dev-c++,但不知道为什么.

Put a newline at the end of the file.

... Or you could always apply this patch (generated against release 3.3.3,
so may need a little fuzz to fit into whatever version you're using), and
then use the flag -Wno-eof-newline to disable the warning....

算是一个BUG吧?我用的是3.3.1

作者: THEBEST 时间: 2004-12-14 09:48
标题: 两道题，问了N多人，没结果，再问一下看看
好了,终于知道找这种BUG是多么痛苦的事.它是逻辑上的而不是语言处理上的问题,所以你跟踪是没有用的,只能靠实例来分析,我打出了很多信息综合起来才发现了这个BUG,其实就是一个maxLen++ -1 ,应该是maxLen++.就因为这个,找了快一个多小时.

不管现在的版本是否正确,但至少我还没发现哪里有不正常的情况.希望哪位能发现就告诉一下.

#include <iostream>;
#include <fstream>;
#include <string>;
#include <vector>;
#include <map>;
#include <set>;
#include <ctime>;
#include <cstdlib>;
#include <algorithm>;
#include <utility>;
using namespace std;
const int SizeMax=10000;
char RandChar();
void RandString(string &);
void OutputStatics(ofstream &,const string &,const map<string,vector<int>; >; &);
void FindSameStr(const string &, string::size_type = 10);
void FindSameReverseStr(const string &,string::size_type = 10);
int main()
{
srand(time(0)); //应该放在这里(其它某些地方也可以),居然犯这种错误.:p
string testString;
RandString(testString);
FindSameStr(testString);
// FindSameReverseStr(testString);
}
char RandChar()
{
// srand(time(0)); //因为每次"种子一样"的话产生的第一个随机数就是一样
switch(rand()%4)
{
case 0: return 'A';
case 1: return 'C';
case 2: return 'G';
case 3: return 'T';
default:
cout << "Error and Exit Prog\n" << endl;
exit(-1);
}
}
void RandString(string &s)
{
for (int i=0; i<SizeMax; ++i)
s.push_back(RandChar());
}
void OutputStatics(ofstream &out,
const string &s,const map<string,vector<int>; >; &sameStr)
{
map<string,vector<int>; >;::const_iterator iter = sameStr.begin(), iter_end = sameStr.end();
out << "The Same String in the Source String:\n" << endl;
while ( iter != iter_end) //不能直接简写为iter++,下面用到iter->;first
{
out << "\"" << iter->;first << "\"" << endl
<< " Length: " << (iter->;first).size() << endl
<< "The Start Pos: ";
for (vector<int>;::const_iterator vi = (iter->;second).begin();
vi != (iter->;second).end(); ++vi)
out << *vi + 1 << " "; //不以0(以1)为字符位置的开始
out << '\n' << endl;
++iter;
}
out << "\n\nSource String:\n" << s << "\n\n" << endl;
//为了方便查看(验证)结果,就把源串放在文件后面.
}
void FindSameStr(const string &s, string::size_type minLen)
{
string::size_type idx = 0, pos = 0, maxLen = minLen;
set<pair<string,string::size_type>; >; SetStr; //元素为字符串与开始查找的位置对
string tempFound, moreLenFound, Found;
while (1) //重要:前面的字符串没有同样的时候还需要找后面的,直到最后一个可能的字符串
{
tempFound = string(s,idx,minLen);
//只要能找到一个同样的就行,注意是从该被找字符串之后开始找
while ( (s.find(tempFound,idx+1)) != string::npos)
{
Found = moreLenFound = tempFound;
//是否存在更长的同样的字符串
while (1)
{
moreLenFound.push_back(s[idx + maxLen++]);
//再也找不到更长的字符串了
if(s.find(moreLenFound,idx + 1) == string::npos)
{
SetStr.insert(make_pair(Found,idx));
idx += (maxLen - minLen);
maxLen = minLen;
tempFound = string(s,idx,minLen); //构造好下一个被找字符串
break;
}
Found = moreLenFound; //保存最长同样的字符串
}
}
if ( (++idx + 2*minLen) >; SizeMax )
break;
}
map<string,vector<int>; >; mvs;
//处理SetStr中的字符串,找到所有共同的字符串的起点
for (set<pair<string,string::size_type>; >;::iterator iter = SetStr.begin();
iter != SetStr.end(); ++iter)
{
pos = iter->;second; //不是从0开始找而是从被查找字符串的开始位置开始找
while( (pos = s.find((*iter).first,pos)) != string::npos)
{
mvs[(*iter).first].push_back(pos);
if((pos++) >;= SizeMax)
break;
}
}
ofstream coutstr("C:\\result.txt");
OutputStatics(coutstr,s,mvs); //可以直接输出到cout上
}
void FindSameReverseStr(const string &s,string::size_type minLen)
{
//在适当的地方把被查找字符串反转一下,和上面的一样处理,也可以来个bool参数
}

复制代码

运行结果如下:

The Same String in the Source String:

"ACTGTGCAAC"
   Length:  10
The Start Pos:  1936  2275

"AGAAAGACGG"
   Length:  10
The Start Pos:  5288  6068

"AGAAGTGAAA"
   Length:  10
The Start Pos:  8578  9238

"AGAATGTGAC"
   Length:  10
The Start Pos:  8275  8559

"AGTCCCAGCA"
   Length:  10
The Start Pos:  5036  6622

"AGTTTTTACA"
   Length:  10
The Start Pos:  1178  4526

"CAAGAATCTT"
   Length:  10
The Start Pos:  1036  2537

"CAATACTGTAA"
   Length:  11
The Start Pos:  4996  5213

"CAGTTGACCA"
   Length:  10
The Start Pos:  2047  4579

"CATTAGTTCC"
   Length:  10
The Start Pos:  533  2793

"CCCTGTAAGT"
   Length:  10
The Start Pos:  2441  4074

"CTAGTGCCCA"
   Length:  10
The Start Pos:  7676  8264

"CTCGTGAACA"
   Length:  10
The Start Pos:  291  4039

"CTGGAAGCGC"
   Length:  10
The Start Pos:  5577  6157

"CTGGAGAACG"
   Length:  10
The Start Pos:  2159  5338

"CTGGATACGGC"
   Length:  11
The Start Pos:  684  8492

"GCGAAGTTGG"
   Length:  10
The Start Pos:  1106  1406

"GCGTTTATCT"
   Length:  10
The Start Pos:  4614  7139

"GGGCCCGCCT"
   Length:  10
The Start Pos:  406  5890

"GGTTGAAAAC"
   Length:  10
The Start Pos:  6122  8812

"GTAAACAGCG"
   Length:  10
The Start Pos:  5003  7599

"GTACTCTGCC"
   Length:  10
The Start Pos:  7920  8022

"GTAGTAGGGG"
   Length:  10
The Start Pos:  3142  4853

"GTGCTACTGA"
   Length:  10
The Start Pos:  4457  9701

"GTGGCTGGCG"
   Length:  10
The Start Pos:  2211  7080

"TCCGTCTCCG"
   Length:  10
The Start Pos:  6790  9434

"TCTATCCGTC"
   Length:  10
The Start Pos:  3350  6786

"TGAATCATAC"
   Length:  10
The Start Pos:  2391  8115

"TGGACTCATCG"
   Length:  11
The Start Pos:  8729  8952

"TTGCTGGTCT"
   Length:  10
The Start Pos:  3828  9511

Source String:
ATAGCTACTACGAAGGGGCGGTTCTGGCGCAGGGAATGTATTAGCATCGCGAAACAATAGTTGGCCAATGTGCAGGCTAGCCACTGCTAGAAAAAAATGTTTAACTTTAAATCATATAGCGTTCTACAGCAACCACTTGAGAAGCTGCATCTGCCTGGCACTGTTACCTCACATTGCGCATTGTACCCAAGGACCCTTTACCAGACGAACGGGAAACTTACACCTTACATTTCTTATGCTATGGGCATTTCTATCGGACTGAACTTCGCCTTCGAATACGTAAGTCATCCCTCGTGAACATAAACAGCGTAAGATGCGGTATGGACATGATTTCGTCGAACTACGCACGCATTTATCAGTTCCGTCTTCATCGAGGCATGGAGCTATTAAGGCAACCTTCCCTCTGGGCCCGCCTAGCCCTCTCGATCTCTTGTTTGATCATGTACAACCCCTTGTATTCACGTGAATGTCAAACACTAGCCCTAGGACTTCAACCTCCGTAGGTGGCCCACACGATCACACCGGGATTGTTCATTAGTTCCTCACTTGGACCCCGATGTATCGTGTTTAGCTAGTACAAGTCAATAACTACATATTCATAATTAGCGTATAACAGATGCCCCTCAATCAGGTCTGCTTGTTCGGAAATAGTAGGTGAACTAGCACCCCTAATGCGGTGCCTCCTGGATACGGCATTGTATCGGTCCCTACGACTTACGTATGAGTTAACGACTGTTACGCCGGCTGGATGTCTAGTGTATCAAGTTATGGCTTACAACCTTCAGGGCGCGACACAGCTTTAAGTGATGTGCGGAGTGCTCCCTAAAACTGTTTGGACGCCTGATCGGACCTGGTCCTGCTACCTACAGGCGGCAAACATCTCCTAGTCTTGATATTGACCTGGGCACTCCGGGCGGTGAGCGAACGTAAAACCAGATACGAGCAATACGAAGATGTGTCACCCTAACTGGGACTGCTAGGTAAAGAACGCTAGGACACTCAGTCCTCTCTCAACTACGGTAGTCTTGAAACCTCCAAGAATCTTGACCGTCTGGCGAGGCCCCTATTTGGCGACTTAATCCTAGGGTGCAAGTTGGGTCCGAAAGCGAAGTTGGTCCCTTCACCGTCATCTGGTTCTCTGAGATATTTTCAACTAAGAAAGTGGAAATATGCCTTCAGTTTTTACACCTTGGGGCGCGGCCATCTCGCTATTTCTCCCCTATATACCACTGTGTTGGCATGCAGCTAGCGTCGCACAGCCATTCGCCCGTCAAACTGATTAATCCAACCCCCCACTTCCAGGGGAGGAGCGATTGGCCATCTCCCTACTCAATTGGCGTACGAGTGGAGAGAGAGTAGCTTCCGCCGCACCTGGGTCGGTTAAGCTTCGCTCTGAAACACCTTCGCGAAGTTGGGTGCAGTATAGAGAATGAATGGCCTCTTTACCGCCCGCTGTGGGGCAGTCCCATTTCTCCCGAGGGCATACTCACCAGGTATTGAGAGCATTCGCCGCACGGGACTAACCACAAAGTAATGGCCAGTCAGACATGCCCTAACTCTTGATGGCATTCCTCGGAGATGCCTAGACGGGGAGCTGTGACCAAGACTCGCGCGCTTACAATCATTATGTGCTGCGCAGAATCGTTATCTTGTACCATGAAGGTATCGGCAACTTGCGTCACCGTTTCTATCGAGGGATAAGATAAAGCACATTACACTCATGGGACTACCCGCCCGTTGACTCGATGTCAATAATGTAGGGTAGAATCACTGACTCGTCGGTTATACCCGCAGGCTACAGTCAATGGATTGGTTATATATGAGGGGCCCTACTACAATGTCAGAGCCCGAGAGGAATGGAGGATCGTTATAGGGAGCAGAGACAATTGGTTACTTGCGCGTTTGGAAGACCGAGATGTACGACCAGCATCTACGACTGTGCAACATACGTGTGGGTAGTTTGGACCCATGAATATTGTTGCTGCCCCGCAACCGCACTAAACTTCCATCCTGGGGAAAGTTAACAAATTCCTAGATAACAGGAGTCAGTTGACCATCCACATGTAGATACCACCAAGAACGAAGCTTGACTCAACGTATCCTCGGTCGCGAACAAGCTCACTACGCCGTGTAGTAGCTTGGTGGTGTGGCGAAAAAACTGGAGAACGAGGAGCACCCTAATATGATCTACGCCATGAATAAAGAACGATGTGGCTGGCGATCGCATGAAAAGAACGCCATCCCGCTTAGCTACAACTTATATAGGGTTGCTGTACTGTGCAACTCGTCCAATGGACGAGTCATCAATCTCATAGTGCATCAGTCATTCTTCCTTCACCAAAACTCGGTTGACGATTAGCTTGCTTGATTGTATAGGCAATATTCAGGGATGAATCATACGTAACTGGGGCTTAATGGCATCCTGTGCACCTCAGTTTGCCCCTGTAAGTCTCGATTAACAGGGCCCCGATACCTGTAATGCCCTCCGCGCGGGTGACCCGGGGAAAGACATTGGCTAAAGTATTCTATCCTTATTCAAGAATCTTTAAAAGCCCCTGTTTCCAGACATGGTTGCTAACCGCGAGCGGTTTTTCTTCAATAGGACTATACTACTCAATAACGCCGCACGCCTTACCCGCACCGGCCGACTGTTAAAGATATTACAATGGCTTGGGCGCATAAGCTCGAGTCGGGATTCTACGTTTGGAACAGCAAATAACCGCGCGGAACGGTGAATGTATGGTCCCACTCACCCCGGCCTGTCACATACATTACCGACTTAGACACGATGACATTAGTTCCGACGGCCCTTAAGGCGGCTCCTACGTATTAGAATTGACGTATATGCCAATGACGCATGGGCGTATCGGAAGTTATCCCGTGTTAGACAGGTATGCTTCTTCGTGCCCCAGGACCCAGCGGCGACCTGCTTACAATGGGGATCGGACCCGCGGCGACTCTATATTCCAACTGTCCGAAACTCATACGGTACAGATTTTCATGCCATGTCCCGGATTTTTACAGGCGATTGCCCGTATACTGGCAGGGCCTCCCAATTCACAAACACCCGCCATTGTTCTAAGGCAAACCTCAGGGTCGACTCGAAGGAACAGCTAACTCTGTGACTTTAGTCTCCCCACCGTAGTAGGGGTAATACACACCCGTGCCGCACACTAAAGCTCATGCTCTCAACTGGCAAGGCTATCATATTATAGAAGCAGGCATTCGCCTCTCAGACTCGTTTGCTGGTGGGAATTGTGCACCACCCGTTGGCGGAAAGTAACTTACCGATAGTGCCGTCCCTCCTGCTCGCATTGGCGCTTAGTAAGAATAACTCGGGGCCCTCTACTCTATCCGTCATTTGCAGTTGAGCCCAGCTGGACTAACTGGCCATGTTAACATCTAAACACTTTGAGTTAACACACCGGGGCTGGAACGTTGCATGCACTACTTACTTAGTGAGCTTGCGTCGAAGACACTGTCCCTACATTTTTGCCGGTCGTTTAAAGCAAGAAACCTTCCCCGTTCGGCCAAACCTTTAGCCCGCTAGCTTTTGCACAACGTGGCAAGGTGATCGTCGGCTAACCACCCTCCGGTGGCGCGGGTTAACTGAAAGGTCCTAGCATCATAGTCAGTTTATCCAGACCGACACCTGGCTGAGGGGTGTTCATAAGTGACGGCGCGCTGTAACTAGCTGCCCACAGCGCTGAGCTTCGCTAGCAATCCACCTTCATGGATGAACCACATCTCAGACCTCATAACGTGGCGCGCCCGCCTCCCGTGACAATAACCTGCAAGGCCTTTACTTCGTACTAGACGAGAGGGACTTGCTGGTCTTGTTGGCGTCTGAGCAGTGCCCATACCCTCTCAAACGGCATTTCACTAAAGATGACGTGGCTCGTCGTTGTTCTTGGTAAAAATAAGTCGTGCTAGGGCCGTTTTAGGGTGGTATGAGGTCTGTTCTCTTGTGACATGATAGCAATTCCACAGGCTTGTTTTAGGGGGTTGTATTACGCCCTGCTGTCCGTAGTTACCCCACTCGTGAACAAGTCACACAAATCAGAGAATGCATACCCTGTAAGTTAATGGCCTACCGCTTGTACTGGGCCTAGTGATCAAGGAAAGATCAGTACTAGGCGCGTGCTCGCTCGGACGCAGCGGCACCTAAAGACGGGCTCACGTGCAAGGATTACTCTCACCACCCCTTTGAGAGCTTGCCAATATACTATGCGGCAGTTTGGTCCTAGAGTTGGGAAGTGAGCCGGTGTAGGGGGCCCATCATTAATCGCCCCCAAGATGCAACAGCCGACCCACCTCTACATACGAAAACCGTCTGGAGGATCCGCGCCGACTAATACCTTCTCGAGGGGACGCGTTGGCAATTGCCATTAATGTTTTTAGAGGAACCCGCACCCGGTGTTGCCCGCGAACTGGACAACTCTCAGATTCTAAACTCGTGCTACTGATGACTTAGCATTCAAAGTGCTAAGGAGGGATGTGGTTTATTCGAGTTCCCCGATCGATTAGTTTTTACATTCTCAAGATCCCCATCACCTAACTTAAAACGCAGTGCGTCGCCAGTTGACCAATAAACCGCCGTGAAACATAGCCACGCGTTTATCTTAGTTTGAATACGCAGCCCGTATCGATTCCGCTCTCGGTACGGTATACGCCACCAGCTCGGGGTAGTAAGGACTGCGCCTCCAGAGGAAACAAGAATGAAATCTAGTCCCGCGATCGCCCGTGACCCCTTAAGCCTGTTTACGTTAGCTAAGTAGTATCCAAACGAGAAGAATAAAGACCCCCGTTTAGAACGCTGCAAACTTAGCGCGAACGTGTTACACAGCGGTAGGTAGTAGGGGCAAGGCGACGAGTAAGATTGGCAGGCAGTGGCCTACATGTCCCCATGGTGAGCTTGGCTTGTCGCTATGTTGTGACTTAACGCCATATATCCAATTAAACCCCTGTGTGTAATTGTCCCCTCACCCAGGTCGACAATACTGTAAACAGCGAATGGTAGAACTCAAAAGCTTCGAGTCCCAGCATCGCGCATCGACCCCCCCGTATCAACGTTAGCACCTACGGCATGGGCTCGAAGAGCAGAACGGGCGATTACTTATGTTTTCCGACTTCTCAGTCACTCTCACTTCCATACTTGGTGGACACACTACACCCACTCGTCCTACACACATGCAAGGTTCGCGGCTCGAAGCAATACTGTAATACTGTCCTTTCTACGCGGACTGTACCTCTTCCAAACTTTAAAGGTGTCCGACTGGTGCAGTAAAGAAAGACGGCAATAGTCCGGTGAGTCCCCCACGGTTAAGCAGGACTGGTCTGGAGAACGTATGGAGTTCTGGGTCGTTATTGGTACTGCAAATGCGATTTGAGAATCGGTTACGAACCAGGATGAGGCTTCACAGAGTACTAAAGTAGCACTTTGTGTCATAGAATCCATCGAGGTAGTAACCGAGGGCACGGTCCCCATTTGCTCGGCAAGGCACCAGACTTTGATGGGGGCTATGCAATGAATATGTTTTTGGACTTACGATTGGTTCTCATTTTGGCACCCCGTACTGGAAGCGCCCCTTGTCAGGTAACTTGAGCTAGTAGCTAAAACACGGTGACCTGCTCCCAACGCGTTTCTCTTAATACCGAGCGCAACTAGGGTAAAGGTAATCGACAATTTATCGGCTGCACACGCCATCGCTGAACCGAGCGCGGGGCAAGATACTCACGAAGTTTTTTCCGGTCAGACCGGTCTAGCCCCCACCGCGCCTGAATGGCTGTCGTATCGTCAAGCACTAAATACTTATTCAATTATCCCCCGGTCCCCAAGATATGCGCGGGCGGGTCTGTAACCCAGTCTAAGGGTCATTATCGACACCCGGGCCCGCCTGAGCCCTTTCAAGTGAGTCTCTTGCTGTGCCGAATCGACAGGTGTAAGCACCACTGTGATGGTAGATGAAGCACGCTAAGTATGTATTTGGACGAATGGCTTGACACGTCGATTCGAGGAGTCTTTCTGAACTGTGTCGAGCGCGCCGGAGGGCCTCTCAACAACCTCAGAAAGACGGAGCTCCGCGCGATATAAGACACTCGGGGTTGTGCGCAATCAAGAGGTTGAAAACCCCCTAATGGGAAATTTGGCCGTTGCTGGAAGCGCGTTATTACGTGGTCCGAAGGTGGTTCATATAGATCACAGAAACCACAGATATCGGCACTTGATTACCTCCGCGGATCACTGAAGGTCTATTGAGTGGATAATGATCGCTCGCCCGGCTTTAGTCTAACCCTGCCCTACCTGACTGCGATCAGTGTATTGCCGCGGTGAATACCGAGAAAATGAAGTGTTCCCTGGAAGTCATTTACCTATAGGAAACGGGACGTTCAACCTATTGAAATACCGGTGGATGGACTTCAAACCAGGGCCGCAGGCTTTTATGCATGTACCTGTCTTAGAAATGTGACTCTGTATGTTAGTCCTTTGATCGGATAAATATTCATGTTTTTGCACGCACCATCAAGTAGACATTATTCGGTATACATTCAGGGAACCCGCCCACACCTCCATTTACCGGGGTCAGCGCGGCCCGATTTTGGCAATTAGGGCCCGCCGGTAGTCCCAGCACAGGCATGACTTCGCCAATTTACGGACCCACGCTCACTCATCACCAGTCCTTCTGCTACGATCCCACAGCGGTGCTCTAGGACGTCCAATCACAGGAGGTTGCAAGCGGTGTGCCACTTTTTAGCCACTTGCCGACTTGGGAGCCAGAATACTTTCTATCCGTCTCCGGAGGAGGCTCGGTTTTCTGCTATTGATACTCTACGTCCTTCATTGGGAATCCGATGGTACTAATGGCATGCGGCGTGATCATACTGATGAGCGCCGGTCGATTTTATCGATCCTGGGCGGCTTACAGCTAAAACTCGGCGGAGCATCATCCGTCGCAGCAGCATCCTCCCGCGTAAATTGTGCTCAGAAATGCGTGCCAGAGATTCATGTCCCACGGCAGAAAATTCGATGCCGAAAGAGCTGAGTGTGCATAAACCAATACAGGTGTGGGACAAACTCCGTGGCTGGCGGATCAATTCATGTGGACCGATCCGCAGAATGTCGCGATGCTAGAGTCAGGCGTTTATCTCATACTAATCACCGTACCACCTTTGAGCAGACCTTAGCTGGTTTGTATGGAGGACTGCGGCTCTAAGCAGTGGGACGGAGCGACGCACATAGCGCCGCATCATCTCCGATGCTCACTCTGGGACTGATTATTTCTGCGCGACTCCTTGACTCGGCATCCGTTCTCGACATGCGCTCGACAACAGGGAGCCCCGAGGTTGGCCAAGACCCTAACCCGAAAAGTTCAATCCAAGGACGAAGCAGCCGCGATGGCATAAGGAGTCTAATGACCCGGTTATAAATCGCAAAAGAAACCGATACATCTATGAAAATGACTAGAGCCATATCGTACGCTGTCTCACCTGTGCCTTCTCATTACCTACTCAGGGTGTATTGGGCTCCCAGGCCCGTCATAGCTGTTCATATAAGACCTGGCTAGGAGGCGCAGGCCCTACGTACTTAGAGTAAACGCGTAAACAGCGCGGGCAGGTCCGAATTCCTTATTCGTGTGTGGAATCACAGATTGTCGGATAGGCAACGGACCAGCCTCTAGTGCCCAGGCCTAATCCCTCGTCAAGATCAATTCTTAGCCTGTCTTTTCTGAGAGACACTGAAAACCCACTAGAACAGGCCGCGTTACAGAACCAACGTGATTATATGTGACAGTCCCTGATCATCTTCAATCTTACAAGGCCCTAGTTCTAGAACAGAAAAGATCCGCTTTGGCTCACCCAATGTCATACCTCACCGAAGGCGGGATTAAGCAGTTTACACCAGTGGTCAACTATATTTCGTACTCTGCCACTTGCGAGGGAAGACGAAAGGCGCCCGCGTACTCCTGTGTGCGAACAGTCATTGCTGCTTAAGTCAGGACATGTCGTAGACTATTTAATTGGTACTCTGCCCGTTTCACTCCCCGGTGTACTCGAATCTGCGGCCGAGGATGTGATATGTTCAGGTTTGCACTGGATGGTCAATGGCGCACCGCTGAATCATACCCCTCCCGACCAAACCATAAGGTGGGATAGGCCTCAAAATAGCCATTATGGACGTTGGAACTGGAATGGTTTCCGACAATCGTGCGATTCAACTGGTTGCCGTCAAATCTATGGACACGCCGTTTTTTACAGTCACTAACTAGTGCCCACAGAATGTGACCGCTGTCAACGTTTTACGCGAAGCAGAACTTGAGGTCCTCCTCACTGCTGCCTTCGCCTGCCAATCTTATGAAGGACCAGACCGTGCCTCATTCATAGTCTCCGACATTCATATATTCCTGGGTTTTCCGTAGTAGACAGATTCAAGGTAGTTACGGTAACCGCCAAAGGGAGTATGTAGTGTCAGTCGAATATCTAGCACACCGAACTGGATACGGCGTAAGTGAAGTTGTCTGGCATAATTGTGACGCGACCTTTTGGGAACGGAGCCATTTAGAATGTGACTATTTGTACAGAAGTGAAAGGCCAAGTGAATCACCTGTCTCCCGTTCAAAGGATATATTATGAAGACAATCTACCGACAGTTTGATATCATATGTTTAACCCGCTCCACAATATGGAGTACCCTTGTCGGGGGTCATCCCTAGAGGATTAGTGGTACTCGTGGACTCATCGATACATGCACCAGGTCTAAATCACGATAGGCACTCTTGTACGCGATTAAATCGGATACCGCGAGCATCGTTGGGTTGAAAACGAGCCTTGCACGTCTTGCTGAGACAAGCAAGTGAAGCCGCCGTCGCTTCTATACGTAATCAATGTCGGGGCATTGCCAGTGTCGCGCATAGGAGGTCATTCGCGCAGCACTCTTCAAGTCCAGTTATAACTGGACTCATCGGGACGATACGACTTAGGGGTTTTACCGAAGCCAAAAGGATGGGCCCCGCAGTTGTCAGCCAGCTGTCTAAATCCATACTCAAGAAAATGGTGTAGCCGTATCCCTCAACGATAGAGTGATGAACCGGGAGGCTCCCAGATTCCGCTGCATCCCCCTTGGAACGTGCGTTGTGAAGCGGGAGTCATTAACATCAGTGGAGGCTATACATATTCGTGGTCGAGGTGGCGGTGAAGACTAACCGGCGTGGCGTTGTGATTTCGGATTCGCGATTTCATAGAAGTGAAAAAACTCTTCCAGAAATAAACATGGGACTCTAAGCCACTGCCCTGGGCGTGGCTAGATGGCAGTTGGCTGCCAATTCCTAAGATCAGGTTGAGATCGAGCTCCAGTTGGTTGGTGAGTGAAGACGAACCGTCAGGCACCGGGGTTCACAAGCTCATAATCTGACAGTGCTCAAGATACCGGATATTGTCCGTCTCCGAGATTTACGGGCGTTCGCACCGAAGAAGGGAAAGTGTACCGGTCACTATCAACCACTCATGTATTTTTTGCTGGTCTATACCGCCCCGACTTTATGTCAGGTGTTATAAGTCGTATCTCCGAAACCGGTACGACCTAGATGATGGCGTTAGGAGATCTAGAAAACCGACGCCGGTTTCGCCTAGTTAGGATTACTTGACCTGCTGCGGTCTATTCCGTCCACCAGTTACCGTCCTCATCACTAATGTGCTGTATTGGGTGCTACTGAGAGAAGGGGTTAGACGCCACCCTCGTAACCTAGAATACGCGGCGAAGAGTGTAGATACTGTATTGGTGAGTCACGGCATCTTTCAGTGTGAGCTGAGGCACGCCGTCTAAGCAACGATGGTTTTATACGGATTTAGTAGTGCCAAGTTCTTTGTATGTCAAATCCAACCACATGGGAGCAGCACCGTATTCGTTGTTGCAAAGTGTTGTGTCAGTTTAATTTCTCACCTTTTGTGATCTCGCCGTCTGGGTACATTGGAGGGTAAGTTTGGTAATGGGAGGTCTCCACTC

作者: THEBEST 时间: 2004-12-14 10:36
标题: 两道题，问了N多人，没结果，再问一下看看
唉,要写好一个程序真是难哪.

我产生100000长度的源字符串找重复串,出现两个问题:
1>;执行时间长,也就是效率很低.
2>;下面是我发现的几组结果:

"AGACAATTGG"
   Length:  10
The Start Pos:  4447  45520  76827  45520  76827

"AGACCGACAC"
   Length:  10
The Start Pos:  11512  32035  78589  32035  78589

"GCGCGTTTGG"
   Length:  10
The Start Pos:  44143  52326  76843

可以看到,后面有两个开始位置与前面一样的,但又不都是这种情况,出现五个同样的基本上都是这种情况,有出现三个的又是正确的.看来这个BUG又要花时间了....

作者: THEBEST 时间: 2004-12-14 11:06
标题: 两道题，问了N多人，没结果，再问一下看看
呵呵,发现了一个规律,第一次出现"三个重复的字符串"之后就出一个错误的(也就是五个的(有两个是一样的)),然后间隔的出现这种情况,看来应该是我的那个for的处理的问题,但是还没看出来.

作者: bioinfor 时间: 2004-12-14 13:17
标题: 两道题，问了N多人，没结果，再问一下看看
TO THEBEST，你的水平以及钻研的精神实在让小弟佩服，这是我要到的一个例子的标准答案，如果这个能运行出来的话，那就证明你的程序没有问题了。
String:
ACGTGCGATCACAGGCCGTGCAGAGACTGACGATCAGACGACGTGACAGGCCGTGCAGAGACTGACGATCAG
Repeat:
Repeat: ACAGGCCGTGCAGAGACTGACGATCAG, Size: 27, Start Positions: 11, 46

BTW：那边搞SHELL的大虾和你做的差不多，就是在找非重叠这块没有过去。这是他们对上面这个例子的答案，很明显是没考虑重叠。
$ ./1 datafile|more
------------------- Line# 1 --------------------

ACAGGCCGTG Length=10 Position=11;46
CAGGCCGTGC Length=10 Position=12;47
AGGCCGTGCA Length=10 Position=13;48
GGCCGTGCAG Length=10 Position=14;49
GCCGTGCAGA Length=10 Position=15;50
CCGTGCAGAG Length=10 Position=16;51
CGTGCAGAGA Length=10 Position=17;52
GTGCAGAGAC Length=10 Position=18;53
TGCAGAGACT Length=10 Position=19;54
GCAGAGACTG Length=10 Position=20;55
CAGAGACTGA Length=10 Position=21;56
AGAGACTGAC Length=10 Position=22;57
GAGACTGACG Length=10 Position=23;58
AGACTGACGA Length=10 Position=24;59
GACTGACGAT Length=10 Position=25;60
ACTGACGATC Length=10 Position=26;61
CTGACGATCA Length=10 Position=27;62
TGACGATCAG Length=10 Position=28;63
ACAGGCCGTGC Length=11 Position=11;46
CAGGCCGTGCA Length=11 Position=12;47
AGGCCGTGCAG Length=11 Position=13;48
GGCCGTGCAGA Length=11 Position=14;49
GCCGTGCAGAG Length=11 Position=15;50
CCGTGCAGAGA Length=11 Position=16;51
CGTGCAGAGAC Length=11 Position=17;52
GTGCAGAGACT Length=11 Position=18;53
TGCAGAGACTG Length=11 Position=19;54
GCAGAGACTGA Length=11 Position=20;55
CAGAGACTGAC Length=11 Position=21;56
AGAGACTGACG Length=11 Position=22;57
.............................

作者: THEBEST 时间: 2004-12-14 14:27
标题: 两道题，问了N多人，没结果，再问一下看看
to bioinfor:

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

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

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

复制代码

把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 时间: 2004-12-14 14:39
标题: 两道题，问了N多人，没结果，再问一下看看

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

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

作者: lightspeed 时间: 2004-12-16 03:52
标题: 两道题，问了N多人，没结果，再问一下看看
THEBEST兄，　我用　awk 写了一个，　想对比一下与　C++ 处理速度上
的差距．　请去这里：
http://bbs.chinaunix.net/forum/viewtopic.php?t=464277&show_type=&start=15&sid=1dc92d81c4a3a4a8269c3f17a5d5e30f

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

作者: yuxh 时间: 2004-12-16 11:26
标题: 两道题，问了N多人，没结果，再问一下看看
这样是不是就可以了呢

#include <stdio.h>;
#include <stdlib.h>;
#include <string.h>;
#include <time.h>;
#define MAXSIZE 100
#define MINMATCH 5
char strUnit[] = {'A', 'C', 'G', 'T'};
int GenQueue(char *strQueue) {
time_t ck;
int nQueueSize,i;
if(strQueue == NULL) return 0;
memset(strQueue, 0, MAXSIZE);
ck = time(NULL);
srand(ck);
nQueueSize = rand() % MAXSIZE;
for(i = 0; i < nQueueSize; i++) {
strQueue[i] = strUnit[rand() % 4];
}
return nQueueSize;
}
int MatchVerted(char *strQueue, int nQueueSize) {
char *pQueue, strMatch[MAXSIZE / 2 + 1];
int i, nMatchLen, nBegin, nFlag, nPosition;
printf("\nVerted Repeat:\n");
for(nBegin = MINMATCH; nBegin < nQueueSize - MINMATCH; nBegin++) {
pQueue = strQueue + nBegin;
nMatchLen = 0;
nFlag = 0;
for(i = 0; i <= nQueueSize - nBegin; i++) {
if(strQueue[i] == pQueue[i]) {
if(nFlag == 0) {
nFlag = 1;
nPosition = i;
}
strMatch[nMatchLen++] = strQueue[i];
if(nMatchLen >;= nBegin) {
strMatch[nMatchLen] = 0;
printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, nPosition + nBegin);
nFlag = 0;
nPosition = 0;
nMatchLen = 0;
}
}
else {
if(nFlag == 1) {
if(nMatchLen >;= MINMATCH) {
strMatch[nMatchLen] = 0;
printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, nPosition + nBegin);
}
nFlag = 0;
nPosition = 0;
nMatchLen = 0;
}
}
}
}
}
int MatchInverted(char *strQueue, int nQueueSize) {
char *pQueue, strMatch[MAXSIZE / 2 + 1];
int i, nMatchLen, nBegin, nFlag, nPosition;
printf("\nInverted Repeat:\n");
for(nBegin = 0; nBegin < nQueueSize - 2 * MINMATCH; nBegin++) {
pQueue = strQueue + nQueueSize - 1 - nBegin;
nMatchLen = 0;
nFlag = 0;
for(i = 0; i < (nQueueSize - nBegin) / 2; i++, pQueue--) {
if(strQueue[i] == *pQueue) {
if(nFlag == 0) {
nFlag = 1;
nPosition = i;
}
strMatch[nMatchLen++] = strQueue[i];
}
else {
if(nFlag == 1) {
if(nMatchLen >;= MINMATCH) {
strMatch[nMatchLen] = 0;
printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, pQueue - strQueue + 1);
}
nFlag = 0;
nPosition = 0;
nMatchLen = 0;
}
}
}
if(nMatchLen >;= MINMATCH) {
strMatch[nMatchLen] = 0;
printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, pQueue - strQueue + 1);
}
}
}
int main(void) {
char strQueue[MAXSIZE];
int nQueueSize;
nQueueSize = GenQueue(strQueue);
printf("String:\n%s\n", strQueue);
MatchVerted(strQueue, nQueueSize);
MatchInverted(strQueue, nQueueSize);
}

复制代码

作者: THEBEST 时间: 2004-12-16 13:03
标题: 两道题，问了N多人，没结果，再问一下看看
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 时间: 2004-12-16 13:23
标题: 两道题，问了N多人，没结果，再问一下看看
我的算法和你们不一样
我把字符串当成两个一样的串来考虑，一个串固定，另一个串划动(象拉链一样)，每一个次都取最大匹配串。。。
这样比较清楚，不用考虑很多复杂的东西，但效率不是很高，o(n*n)

作者: yuxh 时间: 2004-12-16 13:33
标题: 两道题，问了N多人，没结果，再问一下看看
重复的情况应该是可以发现的
我的程序里串长是随机的，而且出来的结果很多，不是按照重复的排列，所以不好找
下面这个串
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 时间: 2004-12-16 15:00
标题: 两道题，问了N多人，没结果，再问一下看看

对于一个已知的基因序列片段如何在数据库中找出与之相近的记录，并标识出该片段
在记录中的位置，是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 时间: 2004-12-16 21:46
标题: 两道题，问了N多人，没结果，再问一下看看
高手真多。。。。。。。。。。

作者: lightspeed 时间: 2004-12-17 02:48
标题: 两道题，问了N多人，没结果，再问一下看看

原帖由 "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

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

复制代码

逆序匹配测试： 1 min 7 sec

Reverted Repeat: AGTTTTTCTTTTTTT, Size: 15, Start Positions: 674,4303
Reverted Repeat: TCATTCATGGTA, Size: 12, Start Positions: 4999,9542
Reverted Repeat: TTCTCAGACTAA, Size: 12, Start Positions: 6843,7896
Reverted Repeat: AGGTGGGCGGA, Size: 11, Start Positions: 1641,2976
Reverted Repeat: GTCTCTTAAAA, Size: 11, Start Positions: 2591,8498
Reverted Repeat: TTGAGGTGACA, Size: 11, Start Positions: 5358,5856
Reverted Repeat: ACAGAATAAAA, Size: 11, Start Positions: 6222,6567
Reverted Repeat: ACTAGAGCTTG, Size: 11, Start Positions: 7340,8599
Reverted Repeat: GTTTTCTTAA, Size: 10, Start Positions: 230,8448
Reverted Repeat: TTTACTTTAG, Size: 10, Start Positions: 611,1360
Reverted Repeat: TACAAAGAAC, Size: 10, Start Positions: 871,2576
Reverted Repeat: GTTCTCAACT, Size: 10, Start Positions: 882,2497
Reverted Repeat: GTGAAACCCT, Size: 10, Start Positions: 1189,1469,4554
Reverted Repeat: AAGGACTTTT, Size: 10, Start Positions: 1515,2225
Reverted Repeat: CTTTTTCTGA, Size: 10, Start Positions: 1545,2382
Reverted Repeat: CAATTTGATC, Size: 10, Start Positions: 2094,4775
Reverted Repeat: TCAAAAAAGA, Size: 10, Start Positions: 2897,5675
Reverted Repeat: GTGACAACAG, Size: 10, Start Positions: 3172,4730
Reverted Repeat: ATTTAATCGT, Size: 10, Start Positions: 3597,9181
Reverted Repeat: AATATCTTTG, Size: 10, Start Positions: 5550,7952
Reverted Repeat: CCTGGGAAGG, Size: 10, Start Positions: 5563,9524
Reverted Repeat: TCTCAAATAG, Size: 10, Start Positions: 5620,9293
Reverted Repeat: AGTATTATCA, Size: 10, Start Positions: 5650,7393
Reverted Repeat: CAATAAATGG, Size: 10, Start Positions: 8800,9810
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 小时。

9 50002 0
9 25005 0
9 12507 0
9 6258 0
9 3133 0
9 1571 0
9 790 0
9 399 0
9 204 0
9 106 0
9 57 1
33 57 0
33 45 1
39 45 1
42 45 1
43 45 0
Repeat: ATTGGATCATTGATCTAATCCAACCACATAACTATAATTACAG, Size: 43, Start Positions: 25161,25204
Repeat: TCGGCCTCCCAAAGTGCTGGGATTACAGGCGTGAGCCACCG, Size: 41, Start Positions: 26357,75092
Repeat: AGTCTTGCTCTGTCGCCCAGGCTGGAGTGCAGTGGCGCG, Size: 39, Start Positions: 31148,69805
.
.

复制代码

作者: yuxh 时间: 2004-12-17 09:05
标题: 两道题，问了N多人，没结果，再问一下看看
[quote]原帖由 "lightspeed"]3) 每个匹配串必须包括全部 ACGT 四个字符。（这是才是有效的基因片断）[/quote 发表：

把程序改一下

#include <stdio.h>;
#include <stdlib.h>;
#include <string.h>;
#include <time.h>;
#define MAXSIZE 10000
#define MINMATCH 10
#define AF 0x01
#define CF 0x02
#define GF 0x04
#define TF 0x08
#define FULLFLAG 0x0F
char strUnit[] = {'A', 'C', 'G', 'T'};
unsigned char hGeneFlag;
int GenQueue(char *strQueue) {
time_t ck;
int nQueueSize,i;
if(strQueue == NULL) return 0;
memset(strQueue, 0, MAXSIZE);
ck = time(NULL);
srand(ck);
nQueueSize = rand() % MAXSIZE;
nQueueSize = MAXSIZE;
for(i = 0; i < nQueueSize; i++) {
strQueue[i] = strUnit[rand() % 4];
}
return nQueueSize;
}
int MatchVerted(char *strQueue, int nQueueSize) {
char *pQueue, strMatch[MAXSIZE / 2 + 1];
int i, nMatchLen, nBegin, nFlag, nPosition;
printf("\nVerted Repeat:\n");
for(nBegin = MINMATCH; nBegin < nQueueSize - MINMATCH; nBegin++) {
pQueue = strQueue + nBegin;
nMatchLen = 0;
nFlag = 0;
hGeneFlag = 0;
for(i = 0; i <= nQueueSize - nBegin; i++) {
if(strQueue[i] == pQueue[i]) {
if(nFlag == 0) {
nFlag = 1;
nPosition = i;
}
switch(strQueue[i]) {
case 'A':
hGeneFlag |= AF;
break;
case 'C':
hGeneFlag |= CF;
break;
case 'G':
hGeneFlag |= GF;
break;
case 'T':
hGeneFlag |= TF;
break;
}
strMatch[nMatchLen++] = strQueue[i];
if(nMatchLen >;= nBegin && hGeneFlag == FULLFLAG) {
strMatch[nMatchLen] = 0;
printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, nPosition + nBegin);
nFlag = 0;
nPosition = 0;
nMatchLen = 0;
}
}
else {
if(nFlag == 1) {
if(nMatchLen >;= MINMATCH && hGeneFlag == FULLFLAG) {
strMatch[nMatchLen] = 0;
printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, nPosition + nBegin);
}
nFlag = 0;
nPosition = 0;
nMatchLen = 0;
}
}
}
}
}
int MatchInverted(char *strQueue, int nQueueSize) {
char *pQueue, strMatch[MAXSIZE / 2 + 1];
int i, nMatchLen, nBegin, nFlag, nPosition;
printf("\nInverted Repeat:\n");
for(nBegin = 0; nBegin < nQueueSize - 2 * MINMATCH; nBegin++) {
pQueue = strQueue + nQueueSize - 1 - nBegin;
nMatchLen = 0;
nFlag = 0;
hGeneFlag = 0;
for(i = 0; i < (nQueueSize - nBegin) / 2; i++, pQueue--) {
if(strQueue[i] == *pQueue) {
if(nFlag == 0) {
nFlag = 1;
nPosition = i;
}
switch(strQueue[i]) {
case 'A':
hGeneFlag |= AF;
break;
case 'C':
hGeneFlag |= CF;
break;
case 'G':
hGeneFlag |= GF;
break;
case 'T':
hGeneFlag |= TF;
break;
}
strMatch[nMatchLen++] = strQueue[i];
}
else {
if(nFlag == 1) {
if(nMatchLen >;= MINMATCH && hGeneFlag == FULLFLAG) {
strMatch[nMatchLen] = 0;
printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, pQueue - strQueue + 1);
}
nFlag = 0;
nPosition = 0;
nMatchLen = 0;
}
}
}
if(nMatchLen >;= MINMATCH && hGeneFlag == FULLFLAG) {
strMatch[nMatchLen] = 0;
printf("Repeat:%s, Size: %d, Start Positioins:%d, %d\n", strMatch, nMatchLen, nPosition, pQueue - strQueue + 1);
}
}
}
int main(void) {
char strQueue[MAXSIZE];
int nQueueSize;
nQueueSize = GenQueue(strQueue);
printf("String:\n%s\n", strQueue);
MatchVerted(strQueue, nQueueSize);
MatchInverted(strQueue, nQueueSize);
}

复制代码

长度为10000时

real 0m2.99s
user 0m2.98s
sys 0m0.01s

长度为100000时
real 5m0.26s
user 4m58.18s
sys 0m1.24s

作者: trustmyself 时间: 2004-12-17 11:14
标题: 两道题，问了N多人，没结果，再问一下看看
真的是好强啊！我是十分的佩服，希望可以盒大家做一很好朋友，哈哈～～～不知道你们是不是给一个机会哦。
哈哈～～～·

作者: bioinfor 时间: 2004-12-17 19:21
标题: 两道题，问了N多人，没结果，再问一下看看
//我将yuxh老大与lightspeed老大的程序运行比较如下：
//用yuxh老大的将10000个字符的data运行了一下，结果如下：

Verted Repeat:
Repeat:AACACAGGGA, Size: 10, Start Positioins:8416, 8471
Repeat:TGATATATCA, Size: 10, Start Positioins:5523, 5588
Repeat:TCGGTATTCAA, Size: 11, Start Positioins:1538, 1819
Repeat:CCACGCTGAT, Size: 10, Start Positioins:1760, 2065
Repeat:AGACTTTACC, Size: 10, Start Positioins:3304, 3860
Repeat:CTCTTGTGCTTA, Size: 12, Start Positioins:4218, 4991
Repeat:AAAACCACTGA, Size: 11, Start Positioins:3877, 4742
Repeat:CCTCGATTGG, Size: 10, Start Positioins:601, 1599
Repeat:TAGACGGCGC, Size: 10, Start Positioins:4364, 5496
Repeat:CCCTGAAAAGC, Size: 11, Start Positioins:6395, 7680
Repeat:ACAAGTCAAGG, Size: 11, Start Positioins:7969, 9299
Repeat:CCTGTTTACC, Size: 10, Start Positioins:2056, 3714
Repeat:TGAGCATATA, Size: 10, Start Positioins:6182, 7983
Repeat:GCATAAAGAG, Size: 10, Start Positioins:1518, 3322
Repeat:AGAAGGAATC, Size: 10, Start Positioins:5744, 7817
Repeat:CCGGCCGTCA, Size: 10, Start Positioins:2697, 4773
Repeat:AGACTCAACT, Size: 10, Start Positioins:5283, 8031
Repeat:GATCGGTGGA, Size: 10, Start Positioins:25, 3005
Repeat:GGTCCTGATAGCG, Size: 13, Start Positioins:1044, 4279
Repeat:GTAAGTGTTT, Size: 10, Start Positioins:540, 3976
Repeat:GTAAGCTAGG, Size: 10, Start Positioins:4008, 7636
Repeat:GTTTCAGATT, Size: 10, Start Positioins:3509, 7617
Repeat:AGATCGCCAC, Size: 10, Start Positioins:2382, 6775
Repeat:CCGCAGCGCA, Size: 10, Start Positioins:1121, 5636
Repeat:CGATTGGAAT, Size: 10, Start Positioins:1602, 6167
Repeat:CACTCATGTA, Size: 10, Start Positioins:821, 5531
Repeat:CTCGGATAGC, Size: 10, Start Positioins:2709, 9155
Repeat:CTCGAGCCAG, Size: 10, Start Positioins:1467, 8255
Repeat:ATTGCGACGA, Size: 10, Start Positioins:1265, 8589
Repeat:GAAGTGGGCG, Size: 10, Start Positioins:1848, 9573
Repeat:TTAATGCAAA, Size: 10, Start Positioins:1748, 9597
Repeat:CGTGATTCTG, Size: 10, Start Positioins:89, 8530
Repeat:TGCCTGTATG, Size: 10, Start Positioins:961, 9957
Inverted Repeat:
Repeat:ACCTTCCTTGACT, Size: 13, Start Positioins:3226, 6709
Repeat:AACCTCGATTGG, Size: 12, Start Positioins:599, 9117
Repeat:ATCGGAAGTC, Size: 10, Start Positioins:3140, 6039
Repeat:TAGAGGTTGC, Size: 10, Start Positioins:4228, 4520
Repeat:GGTACAATGC, Size: 10, Start Positioins:1698, 6789
Repeat:GATGGCTCTGG, Size: 11, Start Positioins:3467, 4314
Repeat:TTTCAGATTG, Size: 10, Start Positioins:3510, 3857
Repeat:GTTGCCGATG, Size: 10, Start Positioins:2671, 4515
Repeat:TAAATGTAGACC, Size: 12, Start Positioins:1072, 5938
Repeat:GCCGCGGCAG, Size: 10, Start Positioins:2588, 4366
Repeat:GCGTCTCCTT, Size: 10, Start Positioins:2871, 4048
Repeat:CGGATTAGGAC, Size: 11, Start Positioins:1624, 5157
Repeat:TGAATGTCTTAC, Size: 12, Start Positioins:2631, 3970
Repeat:TGGATTTGAT, Size: 10, Start Positioins:438, 5949
Repeat:GCGTGATTCTGC, Size: 12, Start Positioins:88, 6202
Repeat:GGCTTATTAGCG, Size: 12, Start Positioins:1614, 4549
Repeat:TGGGATCGAA, Size: 10, Start Positioins:1921, 4010
Repeat:ATAGGAACCT, Size: 10, Start Positioins:2948, 2961
Repeat:GACAATGGTC, Size: 10, Start Positioins:223, 5337
Repeat:GTCGCGTGATT, Size: 11, Start Positioins:85, 5420
Repeat:ACGTGGACTCG, Size: 11, Start Positioins:1530, 3932
Repeat:CCAGAGAGAGG, Size: 11, Start Positioins:628, 3821
Repeat:ATGGTAGGCTT, Size: 11, Start Positioins:104, 4258
Repeat:TAATTCTAAC, Size: 10, Start Positioins:1652, 2338
Repeat:TACTTAGCCAA, Size: 11, Start Positioins:1158, 2243
Repeat:TCGACAGTAA, Size: 10, Start Positioins:565, 2138
Repeat:ATGTCCGTGG, Size: 10, Start Positioins:509, 959
Repeat:TAGGCTTAAA, Size: 10, Start Positioins:108, 1282
real 0m1.382s
user 0m0.010s
sys 0m0.020s

复制代码

//我使用同样的数据集，也就是yuxh老大程序中产生的10000个随机字符，用lightspeed老大的程序运行结果如下：

$ time ./1 datafile
------------------Repeat Match Line# 1 --------------------
Repeat: GGTCCTGATAGCG, Size: 13, Start Positions: 1045,4280
Repeat: CTCTTGTGCTTA, Size: 12, Start Positions: 4219,4992
Repeat: TCGGTATTCAA, Size: 11, Start Positions: 1539,1820
Repeat: AAAACCACTGA, Size: 11, Start Positions: 3878,4743
Repeat: CCCTGAAAAGC, Size: 11, Start Positions: 6396,7681
Repeat: ACAAGTCAAGG, Size: 11, Start Positions: 7970,9300
Repeat: ATTGCGACGA, Size: 10, Start Positions: 1266,8590
Repeat: CTCGAGCCAG, Size: 10, Start Positions: 1468,8256
Repeat: GCATAAAGAG, Size: 10, Start Positions: 1519,3323
Repeat: CGATTGGAAT, Size: 10, Start Positions: 1603,6168
Repeat: TTAATGCAAA, Size: 10, Start Positions: 1749,9598
Repeat: CCACGCTGAT, Size: 10, Start Positions: 1761,2066
Repeat: GAAGTGGGCG, Size: 10, Start Positions: 1849,9574
Repeat: AGATCGCCAC, Size: 10, Start Positions: 2383,6776
Repeat: CCGGCCGTCA, Size: 10, Start Positions: 2698,4774
Repeat: CTCGGATAGC, Size: 10, Start Positions: 2710,9156
Repeat: AGACTTTACC, Size: 10, Start Positions: 3305,3861
Repeat: GTTTCAGATT, Size: 10, Start Positions: 3510,7618
Repeat: GTAAGCTAGG, Size: 10, Start Positions: 4009,7637
Repeat: TAGACGGCGC, Size: 10, Start Positions: 4365,5497
Repeat: AGACTCAACT, Size: 10, Start Positions: 5284,8032
Repeat: TGATATATCA, Size: 10, Start Positions: 5524,5589
Repeat: AGAAGGAATC, Size: 10, Start Positions: 5745,7818
Repeat: TGAGCATATA, Size: 10, Start Positions: 6183,7984
real 0m14.341s
user 0m14.140s
sys 0m0.050s

复制代码

//不得不佩服两位老大结果一样，呵呵，只是yuxh老大的位置计算的前了一位。不过时间上可是C明显要快，尤其当数据集大的时候。
//不过，还是不明白，为什么重复的片段大多集中在10-13呢，连14都很少见，奇怪。

作者: bioinfor 时间: 2004-12-17 19:22
标题: 两道题，问了N多人，没结果，再问一下看看
详细的情况请见：
http://bbs.chinaunix.net/forum/viewtopic.php?p=3094185#3094185

作者: lightspeed 时间: 2004-12-17 22:31
标题: 两道题，问了N多人，没结果，再问一下看看
用 C 果真快很多。但如果你从文件读数据，应该会慢一点点。
另外， awk 的串操作较慢，我准备放弃 substr 语句，相信
会有大的改善。

作者: twen345 时间: 2004-12-18 10:19
标题: 两道题，问了N多人，没结果，再问一下看看
两位老大好强呀，仔细研读二位的代码，学点东东

作者: assiss 时间: 2004-12-18 11:43
标题: 两道题，问了N多人，没结果，再问一下看看
挑毛病的来了，咳咳，
yuxh在程序里用了

GenQueue:
nQueueSize = rand() % MAXSIZE;
nQueueSize = MAXSIZE; //??好像是yuxh没注意，多加上去的。
main:
printf("String:\n%s\n", strQueue);

复制代码

这个造成了对内存的非法读取。

nFlag = 0;
nPosition = 0;
nMatchLen = 0;
hGeneFlag=0;//yuxh在这里忘记加上这一句了。

复制代码

白璧微瑕，瑕不掩瑜。各位继续。

作者: 资深菜鸟 时间: 2004-12-18 22:18
标题: 两道题，问了N多人，没结果，再问一下看看
应该用hash最方便而且可靠吧？

作者: bioinfor 时间: 2004-12-19 00:31
标题: 两道题，问了N多人，没结果，再问一下看看

原帖由 "lightspeed" 发表：
用 C 果真快很多。但如果你从文件读数据，应该会慢一点点。
另外， awk 的串操作较慢，我准备放弃 substr 语句，相信
会有大的改善。

等我有空把数据放到你的awk程序里试试，可能快一点，呵呵。

作者: bioinfor 时间: 2004-12-19 01:14
标题: 两道题，问了N多人，没结果，再问一下看看
[quote]原帖由 "资深菜鸟"]应该用hash最方便而且可靠吧？[/quote 发表：

老兄是perl方面的高手吗？

作者: THEBEST 时间: 2004-12-20 22:45
标题: 两道题，问了N多人，没结果，再问一下看看
没有心思再去分析了,感觉题目给的要求我还没有完全搞明白.我估计效率上C肯定是最快的,C++我估计比AWK要快.lightspeed不要....

我是估计,我对算法从来就不感冒,也没有研究过,我写的程序谈不上算法,只是解决方法.从你给的数据来看我感觉C++要快.

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)