Longest substring that occurs at least twice: C++ question

Question

_{The title is horrible, I know, but until I know the answer to my question, I can't think of a better one. If you can, please edit.}

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

Input: a single string containing lowercase latin letters. The length of string is at least 1 and at most 100.
Output: a single number which is the length of the longest substring of the input string which occurs at least twice in that string( the occurrences may overlap).

Sample input: ababa
Sample output: 3

I got 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 Runtime Error on Test 42 (I can't know what input is that - site rules) with the following code which is but slightly different from the first one.

#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 can't figure out what's wrong with the second code (except the fact that is's slightly less effective and less readable). Is it that I am substracting a const_iterator from an iterator? Or because of int vs. size_t? The code is compiled (on their site) with MSVC8.0 or 9.0. Release mode. Any ideas? Thanks.

@MAK: I don't see how that's relevant here. That is, unless you want to get points with @Armen's first code :) — R. Martinho Fernandes, Jul 10 '11 at 14:07
@MAK: It's in Russian, and I have given all the conditions precisely — Armen Tsirunyan, Jul 10 '11 at 14:07
@Martinho Fernandes: Well, the first thing that came to mind was how long could the input strings be. There could also be other traps in the problem that the OP may have missed. I was also curious about where the problem was from, since I also enjoy solving problems at various OJs. Getting "points" by submitting someone else's code is rather meaningless don't you think? — MAK, Jul 10 '11 at 14:10
@MAK: I mentioned that the string is 100 chars at most. There are no other traps because I have showed you the code I code accepted with. So, the question is, in what way is the second code not equivalent to the first. — Armen Tsirunyan, Jul 10 '11 at 14:13
@Armen Tsirunyan: I am not doubting you, just trying to make doubly sure - experience at various forums shows it is always better to have a look at the original problem statement. Also, I was curious because I like solving problems like this too :). — MAK, Jul 10 '11 at 14:17
but it's not really fun to solve them with brute-force algorithms, right? :> — Karoly Horvath, Jul 10 '11 at 14:23
@yi_H: if the input string is 100 chars long it's better to code a quick brute-force code than to spend time thinking of a better algo (time pressure, you know) — Armen Tsirunyan, Jul 10 '11 at 14:26

MAK · Accepted Answer · 2011-07-10T14:23:55.017

8

Without running your code, I think your second solution fails on input strings of length 1.

Your dif vector is empty whenever the input string has length 1, which causes *max_element(dif.begin(), dif.end()) to fail.

edited Jul 10 '11 at 14:23

answered Jul 10 '11 at 14:15

MAK

26,140
11
55
86

This produces an Access violation, running in debug mode the following description is given: *Expression: vector iterator not derefencerable* – Tommy Andersen Jul 10 '11 at 14:19

score 3 · Answer 2 · answered Jul 10 '11 at 14:16

3

It segfaults on an input with length 1.

You are trying to derefence from an empty vector.

answered Jul 10 '11 at 14:16

Karoly Horvath

94,607
11
117
176

Longest substring that occurs at least twice: C++ question

2 Answers2

Linked