4

たとえば、「hello」と「eo」の 2 つの文字列があり、この例では「e」と「o」という 2 つの文字列の間で重複する文字を見つけたいと考えています。

私のアルゴリズムはこのようになります

 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 操作 - スペースの複雑さ: 2 つの len1 と 2 つの len2 char*.

とが指定されていない場合 (STL ベクトルに頼る場合としない場合) はどうlen1なりますか?len2

このアルゴリズムの実装を提供できますか?

ありがとう

4

2 に答える 2

3

まず第一に、これは部分文字列のマッチングの問題ではなく、2 つの文字列間で共通の文字を見つける問題です。

あなたのソリューションは、コード内でn=len1およびm=len2である O(n*m)で機能します。各文字列の文字を数えることで、同じ問題をO(n+m+c)時間で簡単に解決できます (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;
}

ここでも出力をソートしていることに注意してください。それをしたくない場合は、2 番目の文字列の文字数のカウントをスキップして、外出先で重複の比較を開始できます。

ただし、同じ文字の複数の重複を検出できるようにする場合 (たとえば、「バナナ」と「アリーナ」が「an」ではなく「aan」を出力する必要がある場合)、現在のカウント数を差し引くことができます。解決し、それに応じて出力を調整します。

于 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 に答える