发生至少两次的最长子串:C++问题

Question

_{我知道,这个头衔太可怕了,但在我知道问题的答案之前,我想不出更好的一个.如果可以,请编辑.}

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

输入:包含小写拉丁字母的单个字符串.字符串的长度至少为1且最多为100.
输出:单个数字,即输入字符串中最长子字符串的长度,该字符串在该字符串中至少出现两次(出现次数可能重叠).

样本输入: ababa
样本输出: 3

我使用以下代码接受了Accepted:

#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())失败.