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

THEBEST

需要那么多吗?不觉得,明天写出来,但测试到底是否完全正确就不知道有什么办法了.

aero

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

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

THEBEST

写了一下,但还有问题,随机生成的全是一样的字符呢?当然这样情况并不是不能存在,总的讲,程序还有是问题,只是一个思路而矣.

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 <exception>;
    
11. using namespace std;
    
12. 
    
13. const int SizeMax=10000;
    
14. char RandChar();
    
15. void RandString(string &s);
    
16. void OutputStatics(ofstream &out,
    
17.                  const string &s,const map<string,vector<int>; >; &sameStr);
    
18. void FindSameStr(const string &s, string::size_type minLen = 10);
    
19. void FindSameReverseStr(const string &s,string::size_type minLen = 10);
    
20. 
    
21. int main()
    
22. {
    
23.    ofstream test("C:\\test.txt");
    
24.    string testString;
    
25.    RandString(testString);
    
26.    test << testString << endl;
    
27.    FindSameStr(testString);
    
28. //  FindSameReverseStr(testString);   
    
29.    cin.get();
    
30. }
    
31. 
    
32. char RandChar()
    
33. {
    
34.     srand(time(0));
    
35.     switch(rand()%4)
    
36.     {
    
37.        case 0: return 'A';
    
38.                break;
    
39.        case 1: return 'C';
    
40.                break;
    
41.        case 2: return 'G';
    
42.                break;
    
43.        case 3: return 'T';
    
44.                break;
    
45.        default:
    
46.               cout << "Error and Exit Prog\n" << endl;
    
47.               exit(-1);
    
48.     }
    
49. }           
    
50. 
    
51. void RandString(string &s) {
    
52.       for (int i=0; i<SizeMax; ++i)
    
53.       s.push_back(RandChar());
    
54. }
    
55.       
    
56. void OutputStatics(ofstream &out,
    
57.                  const string &s,const map<string,vector<int>; >; &sameStr)
    
58. {
    
59.      out << "Source String:\n" << s << "\n\n" << endl;
    
60.      map<string,vector<int>; >;::const_iterator iter = sameStr.begin();
    
61.      out << "The Same String in the Source String:\n" << endl;
    
62.      while (iter != sameStr.end())
    
63.      {
    
64.          out << iter->;first << "   Length:  " << (iter->;first).size() << endl
    
65.              << "The Start Pos:  ";
    
66.          for (vector<int>;::const_iterator vi = (iter->;second).begin();
    
67.                         vi != (iter->;second).end(); ++vi)
    
68.              out << *vi << "  ";
    
69.          out << endl;
    
70.      }
    
71. }
    
72.         
    
73. void FindSameStr(const string &s, string::size_type minLen)
    
74. {
    
75.     string::size_type idx = 0, maxLen = minLen, pos = 0;
    
76.     map<string,vector<int>; >; mvs;
    
77.     set<string>; SetStr;
    
78.     string tempFound, moreLenFound, Found;
    
79.    
    
80. while (1)   //重要:前面的字符串没有同样的时候还需要找后面的,直到最后一个可能的字符串
    
81. {
    
82.     tempFound = string(s,idx,minLen);
    
83.     //只要能找到一个同样的就行   
    
84.     while ( (s.find(tempFound,idx+tempFound.length())) != string::npos)
    
85.     {
    
86.         Found = moreLenFound = tempFound;
    
87.         //是否存在更长的同样的字符串
    
88.         while (1)
    
89.         {
    
90.               moreLenFound.push_back(s[idx + maxLen++ - 1]);
    
91.               //再也找不到更长的字符串了
    
92.               if (s.find(moreLenFound,idx + maxLen) == string::npos)
    
93.               {
    
94.                   SetStr.insert(Found);
    
95.                   idx += (maxLen - minLen);
    
96.                   maxLen = minLen;
    
97.                   break;
    
98.               }
    
99.               Found = moreLenFound;  //保存最长同样的字符串
    
100.         }
     
101.     }
     
102. if ( (++idx + minLen) == SizeMax )
     
103.    break;
     
104. }   
     
105.      //处理SetStr中的字符串,找到所有共同的字符串的起点
     
106.      for (set<string>;::iterator iter = SetStr.begin(); iter != SetStr.end(); ++iter)
     
107.      {
     
108.          pos = 0;
     
109.          while( (pos = s.find(*iter),pos) != string::npos)
     
110.          {
     
111.              mvs[*iter].push_back(pos);
     
112.              pos += (*iter).size();
     
113.          }
     
114.      }
     
115.      ofstream coutstr("C:\\sourceStr.txt");   
     
116.      OutputStatics(coutstr,s,mvs);   //可以直接输出到cout上
     
117. }            
     
118. 
     
119. void FindSameReverseStr(const string &s,string::size_type minLen)
     
120. {
     
121.      //在适当的地方把被查找字符串反转一下,和上面的一样处理,也可以来个bool参数
     
122. }

复制代码

THEBEST

楼主,还没看你发的那个就写了一下,效率很低.

eagerly1

我不认为以上2位的程序已经完美,楼主的意见呢

THEBEST

[quote]原帖由 "eagerly1"]我不认为以上2位的程序已经完美,楼主的意见呢[/quote 发表：

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

eagerly1

原帖由 "THEBEST" 发表：

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

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

bioinfor

[quote]原帖由 "eagerly1"]我不认为以上2位的程序已经完美,楼主的意见呢[/quote 发表：


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

THEBEST

程序终于调试好了,但存在一些必需说明的问题:
1>;我机子性能不好,产生10000长度也不知道结果到底是否正确.
2>;我用10位最大长度及至少4位一样长度的相等的字符串试了结果是正确的.
3>;希望帮忙测试一下.
4>;

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

复制代码

这个问题到底是什么引起的?如何解决.好像运气不好就会有,看到有警告不爽.
5>;程序效率很低,还可以改进很多.但需要时间.
6>;为什么随机数都是一样的?程序哪里错了,在产生随机数上.
7>;代码如下:

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 <exception>;
    
11. using namespace std;
    
12. 
    
13. const int SizeMax=1000;   //测试时改成自己想要的最大长度原串
    
14. char RandChar();
    
15. void RandString(string &s);
    
16. void OutputStatics(ofstream &out,
    
17.                  const string &s,const map<string,vector<int>; >; &sameStr);
    
18. void FindSameStr(const string &s, string::size_type minLen = 10);
    
19. void FindSameReverseStr(const string &s,string::size_type minLen = 10);
    
20. 
    
21. int main()
    
22. {
    
23.    ofstream test("C:\\test.txt");
    
24.    string testString;
    
25.    RandString(testString);
    
26.    test << testString << endl;
    
27.    FindSameStr(testString);  //测试时改成最小同样串长度,默认是10
    
28. //  FindSameReverseStr(testString);   
    
29.    cin.get();
    
30. }
    
31. 
    
32. char RandChar()
    
33. {
    
34.     srand(time(0));
    
35.     switch(rand()%4)
    
36.     {
    
37.        case 0: return 'A';
    
38.                break;
    
39.        case 1: return 'C';
    
40.                break;
    
41.        case 2: return 'G';
    
42.                break;
    
43.        case 3: return 'T';
    
44.                break;
    
45.        default:
    
46.               cout << "Error and Exit Prog\n" << endl;
    
47.               exit(-1);
    
48.     }
    
49. }           
    
50. 
    
51. void RandString(string &s) {
    
52.       for (int i=0; i<SizeMax; ++i)
    
53.       s.push_back(RandChar());
    
54. }
    
55.       
    
56. void OutputStatics(ofstream &out,
    
57.                  const string &s,const map<string,vector<int>; >; &sameStr)
    
58. {
    
59.      out << "Source String:\n" << s << "\n\n" << endl;
    
60.      map<string,vector<int>; >;::const_iterator iter = sameStr.begin(),
    
61.                                               iter_end = sameStr.end();
    
62.      out << "The Same String in the Source String:\n" << endl;
    
63.      while ( iter != iter_end)
    
64.      {
    
65.          out << iter->;first << "   Length:  " << (iter->;first).size() << endl
    
66.              << "The Start Pos:  ";
    
67.          for (vector<int>;::const_iterator vi = (iter->;second).begin();
    
68.                         vi != (iter->;second).end(); ++vi)
    
69.              out << *vi << "  ";
    
70.          out << endl << endl;
    
71.          ++iter;
    
72.      }
    
73. }
    
74.         
    
75. void FindSameStr(const string &s, string::size_type minLen)
    
76. {
    
77.     string::size_type idx = 0, maxLen = minLen, pos = 0;
    
78.     map<string,vector<int>; >; mvs;
    
79.     set<string>; SetStr;
    
80.     string tempFound, moreLenFound, Found;
    
81.    
    
82. while (1)   //重要:前面的字符串没有同样的时候还需要找后面的,直到最后一个可能的字符串
    
83. {
    
84.     tempFound = string(s,idx,minLen);
    
85.     //只要能找到一个同样的就行,注意是从该被找字符串之后开始找  
    
86.     while ( (s.find(tempFound,idx+tempFound.length())) != string::npos)
    
87.     {
    
88.         Found = moreLenFound = tempFound;
    
89.         //是否存在更长的同样的字符串
    
90.         while (1)
    
91.         {
    
92.               moreLenFound.push_back(s[idx + maxLen++ - 1]);
    
93.               //再也找不到更长的字符串了
    
94.               if (s.find(moreLenFound,idx + maxLen) == string::npos)
    
95.               {
    
96.                   SetStr.insert(Found);
    
97.                   idx += (maxLen - minLen);
    
98.                   maxLen = minLen;
    
99.                   tempFound = string(s,idx,minLen);  //构造好下一个被找字符串
    
100.                   break;
     
101.               }
     
102.               Found = moreLenFound;  //保存最长同样的字符串
     
103.         }        
     
104.     }
     
105. 
     
106. if ( (++idx + 2*minLen) >; SizeMax )
     
107.    break;
     
108. }   
     
109.      //处理SetStr中的字符串,找到所有共同的字符串的起点
     
110.      for (set<string>;::iterator iter = SetStr.begin(); iter != SetStr.end(); ++iter)
     
111.      {
     
112.          pos = 0;
     
113.          while( (pos = s.find(*iter,pos)) != string::npos)
     
114.          {
     
115.              mvs[*iter].push_back(pos);
     
116.              pos += (*iter).size();
     
117.              if(pos >;= SizeMax)
     
118.                  break;
     
119.          }
     
120.      }
     
121.      ofstream coutstr("C:\\sourceStr.txt");   
     
122.      OutputStatics(coutstr,s,mvs);   //可以直接输出到cout上
     
123. }            
     
124. 
     
125. void FindSameReverseStr(const string &s,string::size_type minLen)
     
126. {
     
127.      //在适当的地方把被查找字符串反转一下,和上面的一样处理,也可以来个bool参数
     
128. }

复制代码

下面的我用的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

原帖由 "bioinfor" 发表：

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

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