Количество символов, совпадающих между двумя строками в переполнении стека
Я строю небольшой проект по исправлению орфографии, это не домашняя работа.
Даны две строки str1 и str2. Нужно выяснить количество символов, совпадающих между двумя строками.
Например, если str1 = «assign» и str2 = «assingn», тогда результат должен быть 6.
В строке str2 символы «a», «s», «s», «i», «g», «n» находятся в строке str1, «assign». Таким образом, выход должен быть 6.
Если str1 = «sisdirturn» и str2 = «тревога», то выходное значение должно быть 6.
В строке str2 символы «d», «i», «s», «t», «u», «r» находятся в строке str1, «sisdirturn». Таким образом, выход должен быть 6.
Я пробовал много попыток, но я не могу получить ответ. Пожалуйста, помогите разобраться в этом, и если есть какие-либо идеи, чтобы улучшить это, скажите.
Вот моя попытка:
int char_match (string str1, string str2)
{
//Take two strings, split them into vector of characters and sort them.
int i, j, value = 0;
vector <char> size1, size2;
char* cstr1 = new char[str1.length() + 1];
strcpy(cstr1, str1.c_str());
char* cstr2 = new char[str2.length() + 1];
strcpy(cstr2, str2.c_str());
for(i = 0, j = 0 ; i < strlen(cstr1), j < strlen(cstr2); i++, j++)
{
size1.push_back( cstr1[i] );
size2.push_back( cstr2[j] );
}
sort (size1.begin(), size1.end() );
sort (size2.begin(), size2.end() );
//Start from beginning of two vectors. If characters are matched, pop them and reset the counters.
i = 0;
j = 0;
while ( !size1.empty() )
{
out :
while ( !size2.empty() )
{
if (size1[i] == size2[j])
{
value++;
pop_front(size1);
pop_front(size2);
i = 0;
j = 0;
goto out;
}
j++;
}
i++;
}
return value;
}
Решение
#include <iostream>
#include <algorithm> // sort, set_intersection
std::string::size_type matching_characters(std::string s1, std::string s2) {
sort(begin(s1), end(s1));
sort(begin(s2), end(s2));
std::string intersection;
std::set_intersection(begin(s1), end(s1), begin(s2), end(s2),
back_inserter(intersection));
return intersection.size();
}
int main() {
std::cout << matching_characters("assign", "assingn") << '\n'; // 6
std::cout << matching_characters("sisdirturn", "disturb") << '\n'; // 6
}
Выше используется сортировка, поэтому она имеет производительность O (N * log N), если это имеет значение. Если все ваши входы малы, то это может быть быстрее, чем второе решение:
Решение Sora имеет большую сложность, а также может быть реализовано кратко с использованием стандартных <algorithm>s:
#include <iostream>
#include <algorithm> // for_each
#include <numeric> // inner_product
int matching_characters(std::string const &s1, std::string const &s2) {
int s1_char_frequencies[256] = {};
int s2_char_frequencies[256] = {};
for_each(begin(s1), end(s1),
[&](unsigned char c) { ++s1_char_frequencies[c]; });
for_each(begin(s2), end(s2),
[&](unsigned char c) { ++s2_char_frequencies[c]; });
return std::inner_product(std::begin(s1_char_frequencies),
std::end(s1_char_frequencies),
std::begin(s2_char_frequencies), 0, std::plus<>(),
[](auto l, auto r) { return std::min(l, r); });
}
int main() {
std::cout << matching_characters("assign", "assingn") << '\n'; // 6
std::cout << matching_characters("sisdirturn", "disturb") << '\n'; // 6
}
Для удобства я использую функции C ++ 14, такие как общие лямбды. Возможно, вам придется внести некоторые изменения, если ваш компилятор не поддерживает C ++ 14.
Для меня решение с использованием sort а также set_intersection занимает около 1/4 времени как другое решение для этих входов. Это происходит потому, что сортировка и перебор массивов из 6 или 7 элементов может быть быстрее, чем обход массивов из 256 элементов.
sort/set_intersection (3667ns) против for_each/inner_product (16,363ns)
Как только входной сигнал достаточно велик, преимущество в скорости перевернется в другую сторону. Кроме того, в точке, где входные данные слишком велики, чтобы воспользоваться преимуществами оптимизации с небольшими строками, sort/set_intersection метод начнет делать дорогостоящие выделения памяти.
Конечно, этот результат производительности сильно зависит от реализации, поэтому, если производительность этой подпрограммы имеет значение, вам придется самостоятельно проверить ее на своей целевой реализации с реальным вводом. Если это не имеет значения, то решение O (N) — лучший выбор.
Другие решения
Я не на 100% уверен в том, чего вы на самом деле пытаетесь достичь, но в случае попытки увидеть, сколько символов совпадают в словах, это был бы простой случай — просто запустить цикл через них и добавить 1 каждый раз вы нашли совпадение, вот так
int char_match (string str1, string str2)
{
//Take two strings, split them into vector of characters and sort them.
unsigned int matches = 0;
unsigned int stringLength = (str1.length > str2.length) ? str2.length : str1.length;
for(unsigned int i = 0; i < stringLength; ++i)
{
if(str1[i] == str2[i])
{
++matches;
}
}
return matches;
}
но из вашего кода похоже, что вы хотите точно узнать, сколько у них одинаковых символов, то есть игнорирование фактической позиции каждого символа, тогда это будет довольно другой процесс. Что-то вроде этого
int char_match (string str1, string str2)
{
unsigned int str1CharCount[256] = {0};
unsigned int str2CharCount[256] = {0};
unsigned int matches = 0;
for(unsigned int i = 0; i < str1.length; ++i)
{
++str1CharCount[static_cast<unsigned short>(str1[i])];
}
for(unsigned int i = 0; i < str2.length; ++i)
{
++str2CharCount[static_cast<unsigned short>(str1[i])];
}
for(unsigned int i = 0; i < 256; ++i)
{
matches += (str1CharCount[i] > str1CharCount[i]) ? str1CharCount[i] - (str1CharCount[i] - str2CharCount[i]) : str2CharCount[i] - (str2CharCount[i] - str1CharCount[i]);
}
return matches;
}
обратите внимание, что для этой второй функции, вероятно, есть гораздо более эффективные способы сделать это, но она должна работать все равно
РЕДАКТИРОВАТЬ:
Этот код должен делать то, что вы хотели, главное отличие в том, что он проверяет значение ascii, чтобы убедиться, что это действительный символ
int char_match (string str1, string str2)
{
unsigned int str1CharCount[256] = {0};
unsigned int str2CharCount[256] = {0};
unsigned int matches = 0;
for(unsigned int i = 0; i < str1.length; ++i)
{
unsigned short aValue = static_cast<unsigned short>(str1[i]);
if(aValue >= static_cast<unsigned short>('a') && aValue <= static_cast<unsigned short>('z'))
{
++str1CharCount[static_cast<unsigned short>(str1[i]) - 32];
}
else if(aValue >= static_cast<unsigned short>('A') && aValue <= static_cast<unsigned short>('Z'))
{
++str1CharCount[static_cast<unsigned short>(str1[i])];
}
}
for(unsigned int i = 0; i < str2.length; ++i)
{
++str2CharCount[static_cast<unsigned short>(str1[i])];
}
for(unsigned int i = static_cast<unsigned short>('a'); i <= static_cast<unsigned short>('Z'); ++i)
{
matches += (str1CharCount[i] > str1CharCount[i]) ? str1CharCount[i] - (str1CharCount[i] - str2CharCount[i]) : str2CharCount[i] - (str2CharCount[i] - str1CharCount[i]);
}
return matches;
}