The longest substring that occurs at least twice: C ++ question

Question

_{The name is terrible, I know, but so far I do not know the answer to my question, I can not think of a better one. If you can, please edit.}

I solved (for fun) a very easy problem on one of the OnlineJudge sites. The problem is this:

Input: one line containing lowercase Latin letters. The string length is not less than 1 and not more than 100.
Conclusion: one number, which is the length of the longest substring, an input string that occurs at least twice in this string (occurrences may overlap).

Input Example: ababa
Output Example: 3

I received Accepted with the following code:

#include <iostream> #include <string> #include <algorithm> int main() { std::string s; std::cin >> s; int max = 0; typedef std::string::const_iterator sit; sit end = s.end(); for(sit it1 = s.begin(); it1 != end; ++it1) for(sit it2 = it1 + 1; it2 != end; ++it2) max = std::max(max, std::mismatch(it1, it1 + (end - it2), it2).first - it1); std::cout << max; } 

However, I get a Runtime Error in test 42 (I don’t know what the input is site rules) with the following code, which is slightly different from the first.

 #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main() { string s; cin >> s; vector<size_t> dif; for(string::const_iterator it1 = s.begin(); it1 != s.end(); ++it1) for(string::const_iterator it2 = it1 + 1; it2 != s.end(); ++it2) dif.push_back(mismatch(it1, it1 + (s.end() - it2), it2).first - it1); cout << *max_element(dif.begin(), dif.end()); } 

After half an hour of ritual dancing, I give up. I cannot understand what is wrong with the second code (except that it is slightly less efficient and less readable). Is it that I subtract const_iterator from iterator ? Or because of int vs. size_t? The code is compiled (on their website) with MSVC8.0 or 9.0. Release mode. Any ideas? Thanks.

Answer 1

Without running my code, I think your second solution crashes on input lines of length 1.

Your dif vector dif empty if the input line is 1, which results in the error *max_element(dif.begin(), dif.end()) .

Answer 2

It goes to the input with a length of 1.

You are trying to separate from an empty vector.