我有两个字符串,例如“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 )怎么办?你能提供你对这个算法的实现吗?
谢谢
最佳答案
首先,这不是子串匹配问题——它是在两个字符串之间找到共同字符的问题。
您的解决方案适用于 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”),那么您可以减去当前的计数数量解决方案并相应地调整输出。
关于C++子串匹配实现,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/12758478/