C++子串匹配实现

Question

我有两个字符串，例如“hello”和“eo”，我希望在这两个字符串之间找到重复的字符，即本例中的“e”和“o”。

我的算法会这样走

 void find_duplicate(char* str_1, char* str_2, int len1, int len2)
 {
     char c ;

     if(len1 < len2)
     {
        int* idx_1 = new int[len1]; // record elements in little string
        // that are matched in big string
        for(int k = 0 ; k < len1 ; k++)
              idx_1[k] = 0;

        int* idx_2 = new int[len2]; // record if element in str_2 has been 
        // matched already or not
        for(int k = 0 ; k < len2 ; k++)
              idx_2[k] = 0;

        for(int i = 0 ; i < len2 ; i++)
        {     
            c = str_1[i];

            for(int j = 0 ; j < len1 ; j++)
            {
                 if(str_2[j] == c)
                 {
                    if(idx_2[j] == 0) // this element in str_2 has not been matched yet
                    {
                         idx_1[i] = j + 1; // mark ith element in idx as matched in string 2 at pos j
                         idx_2[j] = 1;
                    }
                 }
             }
         }

         // now idx_1 and idx_2 contain matches info, let's remove matches.
         char* str_1_new = new char[len1];
         char* str_2_new = new char[len2];
         int kn = 0;
         for(int k = 0 ; k < len1 ; k++)
         {
            if(idx_1[k] > 0)
            {
                 str_1_new[kn] = str_1[k];
                 kn++;
            }
         }

         kn = 0;
         for(int k = 0 ; k < len2 ; k++)
         {
             if(idx_2[k] > 0)
             {
                 str_2_new[kn] = str_2[k];
                 kn++;
             }
         }
      }
      else
      {
            // same here, switching roles (do it yourself)
       }
  }

我觉得我的解决方案很尴尬:- 在第一个 if/else 和代码重复中两种情况的对称性- 时间复杂度:2*len1*len2 操作用于查找重复项，然后 len1 + len2 操作用于删除- 空间复杂度:两个 len1 和两个 len2 char*。

如果未给出 len1 和 len2 会怎样(使用或不使用 STL vector )？

你能提供这个算法的实现吗？

谢谢

Answer 1

首先，这不是子串匹配问题——这是在两个字符串之间寻找共同字符的问题。

您的解决方案在 O(n*m) 中有效，其中 n=len1 和 m=len2 在您的代码中。通过计算每个字符串中的字符数(其中 c 等于字符集的大小)，您可以在 O(n+m+c) 时间内轻松解决相同的问题。这个算法叫做counting sort .

在您的案例中实现此示例代码:

#include <iostream>
#include <cstring> // for strlen and memset

const int CHARLEN = 256; //number of possible chars

using namespace std;

// returns table of char duplicates
char* find_duplicates(const char* str_1, const char* str_2, const int len1, const int len2)
{
  int *count_1 = new int[CHARLEN];
  int *count_2 = new int[CHARLEN];
  char *duplicates = new char[CHARLEN+1]; // we hold duplicate chars here
  int dupl_len = 0; // length of duplicates table, we insert '\0' at the end
  memset(count_1,0,sizeof(int)*CHARLEN);
  memset(count_2,0,sizeof(int)*CHARLEN);
  for (int i=0; i<len1; ++i)
  {
    ++count_1[str_1[i]];
  }
  for (int i=0; i<len2; ++i)
  {
    ++count_2[str_2[i]];
  }

  for (int i=0; i<CHARLEN; ++i)
  {
    if (count_1[i] > 0 && count_2[i] > 0)
    {
      duplicates[dupl_len] = i;
      ++dupl_len;
    }
  }
  duplicates[dupl_len]='\0';
  delete count_1;
  delete count_2;
  return duplicates;
}

int main()
{
  const char* str_1 = "foobar";
  const char* str_2 = "xro";
  char* dup =   find_duplicates(str_1, str_2, strlen(str_1), strlen(str_2));
  cout << "str_1: \"" << str_1 << "\" str_2: \"" << str_2 << "\"\n";
  cout << "duplicates: \"" << dup << "\"\n";
  delete dup;
  return 0;
}

请注意，我也在此处对输出进行排序。如果您不想这样做，您可以跳过第二个字符串中的字符计数，然后开始比较重复项。

但是，如果您打算能够检测同一字母的多个重复项(例如，如果“banana”和“arena”应该输出“aan”而不是“an”)，那么您只需减去在当前解决方案中计数并相应地调整输出。