Число символов, совпадающих между двумя строками в C++

Question

Я создаю небольшой проект для коррекции орфографии, это не домашнее задание.

Данные две строки str1 и str2. Нужно выяснить количество символов, совпадающих между двумя строками.

Например, если str1 = "назначить" и str2 = "assingn", то на выходе должно быть 6.

В str2, символы, "а", "с", "с", "я" , «g», «n» находятся в str1, «присваивать». Таким образом, вывод должен быть 6.

Если str1 = "sisdirturn" и str2 = "беспокоить", то вывод должен быть 6.

В str2, символы, "D", "I", "S" , "t", "u", "r" находятся в строке str1, "sisdirturn". Таким образом, выход должен быть равен 0.

Я пробовал много попыток, однако я не могу получить ответ. Пожалуйста, помогите разобраться в этом, и если есть какая-то идея улучшить это, расскажите.

Вот моя попытка до сих пор:

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; 
} 

Answer 1

#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), если это имеет значение. Если все входы малы, то это может быть быстрее, чем второе решение:

решения Сора имеет лучшую сложность, а также может быть реализовано сжато с использованием стандартных <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) является лучшим выбором.

Answer 2

Я не 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; 
} 

, но из вашего кода он выглядит, как вы хотите, чтобы выяснить, сколько именно из те же символы, что у них есть, то есть игнорирование фактического положения каждого ch тогда это был бы совсем другой процесс. Что-то вдоль линий этого

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; 
} 

Обратите внимание, что для этой второй функции есть, вероятно, гораздо более эффективные способы сделать это, но он должен работать все же

EDIT:

Этот код должен делать то, что вы хотите, основное отличие заключается он проверяет значение 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; 
}