免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 两道题，问了N多人，没结果，再问一下看看
123456下一页
最近访问板块 发新帖
楼主: bioinfor
打印 上一主题 下一主题

两道题，问了N多人，没结果，再问一下看看 [复制链接]

THEBEST

论坛徽章:
1
荣誉会员 日期:2011-11-23 16:44:17
21楼 [报告]
发表于 2004-12-13 22:51 |只看该作者

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

啊,发现程序处理有误.明天再改.是应该保存一下第一次找到的位置然后再在最后全部查找的时候从这个位置开始找而不是都从第0个位置往后找,这样会出现大重复序列中出现小重复序列.今天没时间了.对不起了........
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
bioinfor

论坛徽章:
0
22楼 [报告]
发表于 2004-12-13 22:56 |只看该作者

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

[quote]原帖由 "THEBEST"]啊,发现程序处理有误.明天再改.是应该保存一下第一次找到的位置然后再在最后全部查找的时候从这个位置开始找而不是都从第0个位置往后找,这样会出现大重复序列中出现小重复序列.今天没时间了.对不起了........[/quote 发表：


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

BTW，THEBEST兄你是不是看错了，序列是小于10000，重复的序列要至少大于10啊，你测试的怎么是10个长，重复的是4和5呢？还是你只是拿短的片段测试了一下？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
THEBEST

论坛徽章:
1
荣誉会员 日期:2011-11-23 16:44:17
23楼 [报告]
发表于 2004-12-14 08:24 |只看该作者

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

今天起了个大早,不过还是比较失望....
to bioinfor :
我知道,我前面程序里说明了要真正符合你的要求要改两个数据,我只是用这个短的来测试一下的.再发一个有一个问题未处理的情况:
  1. #include <iostream>;
  2. #include <fstream>;
  3. #include <string>;
  4. #include <vector>;
  5. #include <map>;
  6. #include <set>;
  7. #include <ctime>;
  8. #include <cstdlib>;
  9. #include <algorithm>;
  10. #include <utility>;
  11. using namespace std;

  13. const int SizeMax=10000;
  14. char RandChar();
  15. void RandString(string &);
  16. void OutputStatics(ofstream &,const string &,const map<string,vector<int>; >; &);
  17. void FindSameStr(const string &, string::size_type = 10);
  18. void FindSameReverseStr(const string &,string::size_type  = 10);

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

  29. char RandChar()
  30. {
  31. //  srand(time(0));    //因为每次"种子一样"的话产生的第一个随机数就是一样
  32.     switch(rand()%4)
  33.     {
  34.        case 0: return 'A';
  35.        case 1: return 'C';
  36.        case 2: return 'G';
  37.        case 3: return 'T';
  38.        default:
  39.               cout << "Error and Exit Prog\n" << endl;
  40.               exit(-1);
  41.     }
  42. }           

  44. void RandString(string &s)
  45. {
  46.     for (int i=0; i<SizeMax; ++i)              
  47.         s.push_back(RandChar());
  48. }
  49.       
  50. void OutputStatics(ofstream &out,
  51.                  const string &s,const map<string,vector<int>; >; &sameStr)
  52. {
  53.      out << "Source String:\n" << s << "\n\n" << endl;
  54.      map<string,vector<int>; >;::const_iterator iter = sameStr.begin(),
  55.                                               iter_end = sameStr.end();
  56.      out << "The Same String in the Source String:\n" << endl;
  57.      while ( iter != iter_end)   //不能直接简写为iter++,下面用到iter->;first
  58.      {
  59.          out << "\"" << iter->;first << "\"" << endl
  60.              << "       Length:  " << (iter->;first).size() << endl
  61.              << "The Start Pos:  ";
  62.          for (vector<int>;::const_iterator vi = (iter->;second).begin();
  63.                         vi != (iter->;second).end(); ++vi)
  64.              out << *vi + 1 << "  ";  //不以0(以1)为字符位置的开始
  65.          out << '\n' << endl;
  66.          ++iter;
  67.      }
  68. }
  69.         
  70. void FindSameStr(const string &s, string::size_type minLen)
  71. {
  72.     string::size_type idx = 0, pos = 0, maxLen = minLen;   
  73.     set<pair<string,string::size_type>; >; SetStr;    //元素为字符串与开始查找的位置对
  74.     string tempFound, moreLenFound, Found;
  75.    
  76.     while (1)   //重要:前面的字符串没有同样的时候还需要找后面的,直到最后一个可能的字符串
  77.     {
  78.       tempFound = string(s,idx,minLen);
  79.       //只要能找到一个同样的就行,注意是从该被找字符串之后开始找  
  80.       while ( (s.find(tempFound,idx+1)) != string::npos)
  81.       {
  82.           Found = moreLenFound = tempFound;
  83.           //是否存在更长的同样的字符串
  84.           while (1)
  85.           {
  86.               moreLenFound.push_back(s[idx + maxLen++ - 1]);
  87.               //再也找不到更长的字符串了
  88.               if (s.find(moreLenFound,idx + maxLen - minLen) == string::npos)
  89.               {
  90.                   SetStr.insert(make_pair(Found,idx));
  91.                   idx += (maxLen - minLen);
  92.                   maxLen = minLen;
  93.                   tempFound = string(s,idx,minLen);  //构造好下一个被找字符串
  94.                   break;
  95.               }
  96.               Found = moreLenFound;  //保存最长同样的字符串
  97.           }        
  98.       }
  99.       if ( (++idx + 2*minLen) >; SizeMax )
  100.          break;
  101.    }

  103.    map<string,vector<int>; >; mvs;   
  104.      //处理SetStr中的字符串,找到所有共同的字符串的起点
  105.    for (set<pair<string,string::size_type>; >;::iterator iter = SetStr.begin();
  106.                             iter != SetStr.end(); ++iter)
  107.    {
  108.        pos = iter->;second;   //不是从0开始找而是从被查找字符串的开始位置开始找
  109.        while( (pos = s.find((*iter).first,pos)) != string::npos)
  110.        {
  111.            mvs[(*iter).first].push_back(pos);
  112.            if((pos++) >;= SizeMax)
  113.                break;
  114.        }
  115.    }
  116.    ofstream coutstr("C:\\result.txt");   
  117.    OutputStatics(coutstr,s,mvs);   //可以直接输出到cout上
  118. }            

  120. void FindSameReverseStr(const string &s,string::size_type minLen)
  121. {
  122.      //在适当的地方把被查找字符串反转一下,和上面的一样处理,也可以来个bool参数
  123. }
复制代码
我运行一次后的情况如下:
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的更长的串),就不知道有没有重复串没找到的情况.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
THEBEST

论坛徽章:
1
荣誉会员 日期:2011-11-23 16:44:17
24楼 [报告]
发表于 2004-12-14 08:26 |只看该作者

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

有些BUG已清除,在程序中都给了注释.但那个警告还不知道是怎么回事,希望哪位兄弟帮忙指点一下.谢谢了.
to 楼主:我还没看你发的那个,所以没有新的想法.只是按照我一开始想的走下去了.等这个版本做好了再看看你给的那个会不会有更好的处理办法.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
assiss

论坛徽章:
0
25楼 [报告]
发表于 2004-12-14 09:15 |只看该作者

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

你用的是什么IDE？
MINGW DEVELOP STUDIO？
如果是，那只需要在每个代码文件的最后加一个空行就OK了。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
THEBEST

论坛徽章:
1
荣誉会员 日期:2011-11-23 16:44:17
26楼 [报告]
发表于 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
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
THEBEST

论坛徽章:
1
荣誉会员 日期:2011-11-23 16:44:17
27楼 [报告]
发表于 2004-12-14 09:48 |只看该作者

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

好了,终于知道找这种BUG是多么痛苦的事.它是逻辑上的而不是语言处理上的问题,所以你跟踪是没有用的,只能靠实例来分析,我打出了很多信息综合起来才发现了这个BUG,其实就是一个maxLen++ -1 ,应该是maxLen++.就因为这个,找了快一个多小时.

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

  1. #include <iostream>;
  2. #include <fstream>;
  3. #include <string>;
  4. #include <vector>;
  5. #include <map>;
  6. #include <set>;
  7. #include <ctime>;
  8. #include <cstdlib>;
  9. #include <algorithm>;
  10. #include <utility>;
  11. using namespace std;

  13. const int SizeMax=10000;
  14. char RandChar();
  15. void RandString(string &);
  16. void OutputStatics(ofstream &,const string &,const map<string,vector<int>; >; &);
  17. void FindSameStr(const string &, string::size_type = 10);
  18. void FindSameReverseStr(const string &,string::size_type  = 10);

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

  29. char RandChar()
  30. {
  31. //  srand(time(0));    //因为每次"种子一样"的话产生的第一个随机数就是一样
  32.     switch(rand()%4)
  33.     {
  34.        case 0: return 'A';
  35.        case 1: return 'C';
  36.        case 2: return 'G';
  37.        case 3: return 'T';
  38.        default:
  39.               cout << "Error and Exit Prog\n" << endl;
  40.               exit(-1);
  41.     }
  42. }           

  44. void RandString(string &s)
  45. {
  46.     for (int i=0; i<SizeMax; ++i)              
  47.         s.push_back(RandChar());
  48. }
  49.       
  50. void OutputStatics(ofstream &out,
  51.                  const string &s,const map<string,vector<int>; >; &sameStr)
  52. {
  53.      map<string,vector<int>; >;::const_iterator iter = sameStr.begin(),                                              iter_end = sameStr.end();
  54.      out << "The Same String in the Source String:\n" << endl;
  55.      while ( iter != iter_end)   //不能直接简写为iter++,下面用到iter->;first
  56.      {
  57.          out << "\"" << iter->;first << "\"" << endl
  58.              << "       Length:  " << (iter->;first).size() << endl
  59.              << "The Start Pos:  ";
  60.          for (vector<int>;::const_iterator vi = (iter->;second).begin();
  61.                         vi != (iter->;second).end(); ++vi)
  62.              out << *vi + 1 << "  ";  //不以0(以1)为字符位置的开始
  63.          out << '\n' << endl;
  64.          ++iter;
  65.      }
  66.      out << "\n\nSource String:\n" << s << "\n\n" << endl;
  67.      //为了方便查看(验证)结果,就把源串放在文件后面.
  68. }
  69.         
  70. void FindSameStr(const string &s, string::size_type minLen)
  71. {
  72.     string::size_type idx = 0, pos = 0, maxLen = minLen;   
  73.     set<pair<string,string::size_type>; >; SetStr;    //元素为字符串与开始查找的位置对
  74.     string tempFound, moreLenFound, Found;
  75.    
  76.     while (1)   //重要:前面的字符串没有同样的时候还需要找后面的,直到最后一个可能的字符串
  77.     {
  78.       tempFound = string(s,idx,minLen);
  79.       //只要能找到一个同样的就行,注意是从该被找字符串之后开始找  
  80.       while ( (s.find(tempFound,idx+1)) != string::npos)
  81.       {
  82.           Found = moreLenFound = tempFound;
  83.           //是否存在更长的同样的字符串
  84.           while (1)
  85.           {
  86.               moreLenFound.push_back(s[idx + maxLen++]);
  87.               //再也找不到更长的字符串了
  88.               if(s.find(moreLenFound,idx + 1) == string::npos)
  89.               {
  90.                   SetStr.insert(make_pair(Found,idx));
  91.                   idx += (maxLen - minLen);
  92.                   maxLen = minLen;
  93.                   tempFound = string(s,idx,minLen);  //构造好下一个被找字符串
  94.                   break;
  95.               }
  96.               Found = moreLenFound;  //保存最长同样的字符串
  97.           }        
  98.       }
  99.       if ( (++idx + 2*minLen) >; SizeMax )
  100.          break;
  101.    }

  103.    map<string,vector<int>; >; mvs;   
  104.      //处理SetStr中的字符串,找到所有共同的字符串的起点
  105.    for (set<pair<string,string::size_type>; >;::iterator iter = SetStr.begin();
  106.                             iter != SetStr.end(); ++iter)
  107.    {
  108.        pos = iter->;second;   //不是从0开始找而是从被查找字符串的开始位置开始找
  109.        while( (pos = s.find((*iter).first,pos)) != string::npos)
  110.        {
  111.            mvs[(*iter).first].push_back(pos);
  112.            if((pos++) >;= SizeMax)
  113.                break;
  114.        }
  115.    }
  116.    ofstream coutstr("C:\\result.txt");   
  117.    OutputStatics(coutstr,s,mvs);   //可以直接输出到cout上
  118. }            

  120. void FindSameReverseStr(const string &s,string::size_type minLen)
  121. {
  122.      //在适当的地方把被查找字符串反转一下,和上面的一样处理,也可以来个bool参数
  123. }
复制代码


运行结果如下:
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
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
THEBEST

论坛徽章:
1
荣誉会员 日期:2011-11-23 16:44:17
28楼 [报告]
发表于 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又要花时间了....
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
THEBEST

论坛徽章:
1
荣誉会员 日期:2011-11-23 16:44:17
29楼 [报告]
发表于 2004-12-14 11:06 |只看该作者

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

呵呵,发现了一个规律,第一次出现"三个重复的字符串"之后就出一个错误的(也就是五个的(有两个是一样的)),然后间隔的出现这种情况,看来应该是我的那个for的处理的问题,但是还没看出来.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
bioinfor

论坛徽章:
0
30楼 [报告]
发表于 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
.............................
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
123456下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP