时间戳

首页 > 解决方案 > 在两个字符串 C++ 中找到最长的子字符串

c++ - 在两个字符串 C++ 中找到最长的子字符串

问题描述

我必须输入 2 个字符串（它们可以包含白色字符，没有新行），然后找到它们中最长的子字符串。

有我的代码：

#include <string>
#include <vector>

int main()
{
    std::string tekst1, tekst2;
    
    int s1{}, s2{}, y{}, z{}, longest{};

    std::getline(std::cin, tekst1);
    std::getline(std::cin, tekst2);

    
    std::vector<char> chartekst1(tekst1.c_str(), tekst1.c_str() + tekst1.size() + 1);//converting string to char
    std::vector<char> chartekst2(tekst2.c_str(), tekst2.c_str() + tekst2.size() + 1);
    s1 = chartekst1.size();
    s2 = chartekst2.size();
    char* podciag = new char[s1];//temporary char - will contain substring

    for (int i = 0; i < s1; i++)
    {
        for (int t = 0; t < s2; t++)
        {
            y = i;
            z = t;
            while(chartekst1[y] == chartekst2[z] || y<s1 || z < s2)
            { 
                i = 0;
                podciag[i] = chartekst1[y];//adding same chars to tmp char array
                longest += 1;
                y++;
                z++;
                i++;
                std::cout << podciag[i];
            }

        }
    }
}

现在我被困住了，我不知道下一步该怎么做。我遇到内存错误Debug Assertion Failed! - vector subscript out of range。some1可以帮助我吗？

标签： c++

解决方案

您的代码有很多问题：

  1. 你无缘无故地转换为string。可以使用或最好使用vector直接访问字符串。根本不需要。即使您不希望使用默认索引器，您也可以使用它，这是您可以使用的。[index].at(index)vectorstringc_str()const char*[]

  2. 您的循环非常不清楚。您正在重复变量i，t没有充分的理由。然后在最里面的主体中，您正在修改i这也会影响第一个循环。除非您知道应该修改循环变量，否则不应修改。即使那样，你也会遇到问题。

  3. 最里面的代码块中的修改i是导致调试断言错误的原因。vector使用.at(index)而不是更好地访问[index]。后者在某些实现（例如 MSVC++）中引发调试断言，并且不能被try/catch块捕获，因为它不是 C++ 异常。因此，vector不惜一切代价避免使用它。

我编写了一个快速代码，可以在不使用任何现有算法的情况下解决您的问题。在空间或时间复杂性方面，我的目标不是最好的 Big O。所以用一小撮盐吃。它肯定可以针对性能进行大量优化。但就目前而言，它完成了这项工作。

#include <string>
#include <iostream>

int main()
{
  // small is copy of the smaller string, large is similar
  std::string tekst1, tekst2, small, large;

  // scan strings from standard input device
  std::getline(std::cin, tekst1);
  std::getline(std::cin, tekst2);

  // determine which of the two inputs is smaller, assign small/large accordingly
  size_t s1, s2; 
  s1 = tekst1.size();
  s2 = tekst2.size(); 

  if (s1 > s2) {
    small = tekst2; 
    large = tekst1; 
  }
  else {
    small = tekst1; 
    large = tekst2;
  }

  // update s1 and s2 to reflect small and large lengths respectively
  // this is done to make looping easier
  s1 = small.size(); 
  s2 = large.size();

  // sub_small is to take sub-string from small string for comparison
  // sub_large is the sub-string from large for comparison
  std::string sub_small, sub_large;

  // set max length as length of small - this is max allowed length
  // this can only happen if small string is completely contained 
  // within large string
  size_t max_length = s1;

  size_t i, j; // i declared them outside of loop if you wish to use them later
  bool match = false; 

  // try matching sub-strings from max_length all the way down to 0
  while (max_length > 0) {
    // start with small string, take substring from it, compare to
    // all possible max_length subsets taken from the large string
    // if any match was found, break everything. if none, repeat
    for (i = 0; i < s1 && i + max_length <= s1; i++) {
      sub_small = small.substr(i, max_length); 

      for (j = 0; j < s2 && j + max_length <= s2; j++) {
        sub_large = large.substr(j, max_length); 
        match = sub_small == sub_large;
        if (match) break;
      }
      if (match) break;
    }
    if (match) break;
    max_length--;
  };

  std::cout << std::endl;

  if (match) {
    std::cout << "Largest matching sub-string has size [ " << max_length << " ]" << std::endl;
    std::cout << "Value: \"" << sub_small << "\""<< std::endl;
  }
  else {
    std::cout << "Could not find any matching substrings!" << std::endl;
  }
}

请注意：

  1. 代码将告诉它是否使用match变量找到任何子字符串。

  2. 该代码允许您判断找到的子字符串在较小和较大字符串中的起始位置。为此，请分别查看i和j表示找到的匹配项（如果有）的起始small索引large。

推荐阅读