发生至少两次的最长子字符串：C ++问题 [英] Longest substring that occurs at least twice: 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）。 
 std :: cout<< max;但是，我得到测试42的运行时错误     / em> （我不知道是什么输入 - 站点规则）与以下代码，但略有不同的第一个。
  #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 ？还是因为int和size_t？代码是在MSVC8.0或9.0上编译（在他们的网站上）。释放模式。有任何想法吗？感谢。
解决方案
没有运行你的代码，我想你的第二个解决方案失败长度为1的输入字符串。
 
 
 
每当输入字符串长度为1时，您的 dif 向量为空，这会导致 * max_element（dif.begin （），dif.end（））失败。
 
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.
解决方案
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.

                        
这篇关于发生至少两次的最长子字符串：C ++问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！