c++ - 至少出现两次的最长子串 : C++ question

Question

_{我知道标题很糟糕，但在我知道我的问题的答案之前，我想不出更好的标题。如果可以，请编辑。}

我在一个 OnlineJudge 网站上(为了好玩)解决了一个非常简单的问题。问题是这样的:

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).

示例输入: 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());
}

半小时的仪式舞蹈后，我放弃了。我无法弄清楚第二个代码有什么问题(除了它的效率和可读性稍差)。是不是我要从 iterator 中减去 const_iterator？还是因为 int 与 size_t？代码是用 MSVC8.0 或 9.0 编译的(在他们的网站上)。 Release模式。有任何想法吗？谢谢。

Answer 1

如果不运行您的代码，我认为您的第二个解决方案无法处理长度为 1 的输入字符串。

当输入字符串的长度为 1 时，您的 dif vector 为空，这会导致 *max_element(dif.begin(), dif.end()) 失败。