Самая длинная подстрока, встречающаяся как минимум дважды: вопрос C ++

Question

_{Название ужасное, я знаю, но пока я не знаю ответ на свой вопрос, я не могу придумать лучшего. Если можете, отредактируйте.}

Я решил (для шутки) очень простую проблему на одном из сайтов OnlineJudge. Проблема заключается в следующем:

Ввод: одна строка, содержащая строчные латинские буквы. Длина строка не менее 1 и не более 100.
Вывод: одно число, которое является длина самой длинной подстроки входная строка, которая встречается как минимум дважды в этой строке (вхождения могут совпадать).

Пример ввода: ababa
Пример вывода: 3

Я получил Принято со следующим кодом:

#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;
}

Однако я получаю Ошибка времени выполнения теста 42 (я не могу знать, что это за ввод - правила сайта) со следующим кодом, который немного отличается от первого один.

#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());
}

После получаса ритуальных танцев я сдаюсь. Я не могу понять, что не так со вторым кодом (за исключением того факта, что он немного менее эффективен и менее читабелен). Это то, что я вычитаю const_iterator из iterator? Или из-за int против size_t? Код скомпилирован (на их сайте) с MSVC8.0 или 9.0. Режим выпуска. Есть идеи? Спасибо.

Answer 1

Без запуска вашего кода, я думаю, что ваше второе решение не сработает на входных строках длины 1.

Ваш dif вектор пуст, когда входная строка имеет длину 1, что приводит к сбою *max_element(dif.begin(), dif.end()).

Answer 2

Это происходит с ошибками на входе с длиной 1.

Вы пытаетесь отстегнуть от пустого вектора.