4

我有两个字符串，例如“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字符*。

如果没有给出（有len1和len2没有诉诸 STL 向量）怎么办？

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

谢谢

4

2 回答 2

3

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

您的解决方案适用于O(n*m)，其中n=len1和m=len2在您的代码中。通过计算每个字符串中的字符（其中 c 等于字符集的大小），您可以在O(n+m+c)时间内轻松解决相同的问题。这种算法称为计数排序。

在您的情况下实现此示例代码：

#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”），那么您可以减去当前的计数解决方案并相应地调整输出。

于 2012-10-06T10:10:35.987 回答
0 
std::vector<char> duplicates;
for (auto c1: std::string(str_1))
  for (auto c2: std::string(str_2))
    if (c1 == c2)
      duplicates.push_back(c1);

或者如果您没有符合 c++11 的编译器。 

std::vector<char> duplicates;
std::string s1(str_1);
std::string s2(str_2);
for (std::size_t i = 0; i < s1.size(); i++)
  for (std::size_t j = 0; j < s2.size(); j++)
    if (s1[i] == s2[j])
      duplicates.push_back(s1[i]);

--基于Zaroth的回答

std::vector<int> count(256,0);
for (auto c : std::string(str_1))
 count[c] += 1;
for (auto c : std::string(str_2))
 if (count[c] > 0)
   duplicates.push_back(c);
于 2012-10-06T09:37:00.963 回答