Как посчитать количество совпадающих символов в обоих строках?

Question

[StrapusCactus]

Как посчитать количество символов, которые есть и в первой и во второй строке?

Моё решение:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <clocale>
#include <string>
using namespace std;

int main()
{
    setlocale(LC_CTYPE, "rus");
    string a = "1234";
    string b = "9321";
    int p = 0;
    for(int z = 0; z < 4; z++){
        if(a.find(b[z]) == 0){
            p += 1;
        }
    }
    cout << p << endl;
    return 0;
}

По идеи в примере мне надо чтоб получилось 2. Типо числа 1 и 2 есть в другой строке.

А сама идея такова:
1. Есть строка;
2. Пройтись по строке;
3. Посчитать и прибавить в переменную кол-во совпадений
строка 1234 = 1234 равно 4
строка 1239 = 5912 равно 3
строка 9876 = 6123 равно 1

Надеюсь норм описал проблему =)

Спасибо за помощь!

Comments

[devalone]

Описал вопрос по русски, прими исправление, если я правильно понял, что ты хочешь

[Евгений Шатунов]

StrapusCactus , третий вариант, не затрагивающий память (как в случае с std::set), не делающий N^2 (т.к. M*N -> N*N) (как в случае с for-find) и никак не ущемляющий прав решивших твой вопрос ребят.

const size_t GetIntersectionsNumber( const std::string& left, const std::string& right )
{
   bool char_mask[256] = { 0 };
   for( int c : left )
   {
      char_mask[ c ] = true;
   }
   
   size_t intersections = 0;
   for( int c : right )
   {
      intersections += char_mask[ c ];
      char_mask[ c ] = false;
   }
   
   return intersections;
}

Answer 1

[devalone]

#include <algorithm>
#include <iostream>
#include <set>
#include <string>

int main()
{
    std::string str1 = "just string with some numbers 124632";
    std::string str2 = "1234567890 i";
    std::set<std::string::value_type> setOfSymbolsInStr1(
        str1.begin(),
        str1.end());

    std::set<std::string::value_type> setOfSymbolsInStr2(
        str2.begin(),
        str2.end());

    std::set<std::string::value_type> intersection;
    std::set_intersection(
        setOfSymbolsInStr1.begin(),
        setOfSymbolsInStr1.end(),
        setOfSymbolsInStr2.begin(),
        setOfSymbolsInStr2.end(),
        std::inserter(intersection, intersection.begin()));

    std::cout << intersection.size() << std::endl;

    return 0;
}

Comments

[StrapusCactus]

O_O а можно на моем примере правки сделать? я пока с std не работаю (т.к. совсем с нуля пока начал c++ изучать, да и хз чего эти std дают) Просто скачал Code Blocks, пробую в нем.

[Mercury13]

Зачем использовать на такую задачу большую пушку в виде std::set?

[StrapusCactus]

setlocale(LC_CTYPE, "rus"); ?

[devalone]

Mercury13, конкретно в этой задаче может и не нужно, но в случае когда строки будут длинные решение ТСа будет работать долго, на каждый символ первой строки будет перебираться вторая

[devalone]

StrapusCactus,

а можно на моем примере правки сделать?

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <clocale>
#include <string>
using namespace std;

int main()
{
    setlocale(LC_CTYPE, "rus");
    string str1 = "1235";
    string str2 = "9321";
    size_t countOfCommonSymbols = 0;
    for(size_t i = 0; i < 4; i++){
        if(str1.find(str2[i]) != string::npos){
            countOfCommonSymbols++;
        }
    }
    cout << countOfCommonSymbols << endl;
    return 0;
}

я пока с std не работаю

Вообще-то работаешь, string как раз оттуда.

да и хз чего эти std дают

Они дают готовые контейнеры, алгоритмы и т.д. и позволяют меньше велосипедить.

[StrapusCactus]

Спасибо. Буду читать дальше =)

[Mercury13]

Ринат Велиахмедов, вот мой код без «больших пушек».

#include <algorithm>
#include <iostream>
#include <clocale>
#include <string>

using namespace std;

class Counter
{
public:
    size_t cnt = 0;
    static int v;

    Counter& operator++() { ++cnt; return *this; }
    Counter operator++(int) { Counter r = *this; ++cnt; return r; }
    int& operator*() const { return v; }
};

int Counter::v = 0;


int main()
{
    setlocale(LC_CTYPE, "rus");
    string a = "1234444";
    string b = "9321999";

    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    std::string::iterator aEnd = std::unique(a.begin(), a.end());
    std::string::iterator bEnd = std::unique(b.begin(), b.end());
    Counter cnt = std::set_intersection(
            a.begin(), aEnd, b.begin(), bEnd, Counter());

    cout << cnt.cnt << endl;
    return 0;
}

Заглушка, работающая итератором + std::sort + std::unique.

[Mercury13]

Ринат Велиахмедов, Почему большая пушка — потому что издержки намного превышают std::string'овские.

[devalone]

Mercury13, и всё таки моё решение на больших строках работает быстрее :) Компилю с -O3, без оптимизиаций тоже

[devalone]

Mercury13, а вообще, если бы я заботился о производительности, я бы написал что-нибудь такое:

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string str1 = "123456";
    std::string str2 = "058765";
    
    unsigned char commonSymbols[256];
    std::fill(commonSymbols, commonSymbols + 256, 0);
    
    for (size_t i = 0; i < str1.size(); ++i)
        commonSymbols[str1[i]] = 1;
    
    for (size_t i = 0; i < str2.size(); ++i)
        commonSymbols[str2[i]] |= 2;
	
    size_t countOfCommonSymbols = 0;
    
    for(size_t i = 0; i < 256; ++i)
        if (commonSymbols[i] == 3)
            ++countOfCommonSymbols;

    std::cout << countOfCommonSymbols << std::endl;

    return 0;
}

[devalone]

Для юникода просто массив побольше.

[devalone]

Ринат Велиахмедов, ты ж только что оставлял комментарий, где говорил обратное... ну ладно, не суть, бенчмаркни то, которое я только что оставил в комментариях(с массивом) :)

[Sdima1357]

std::unordered_set быстрее будет

[devalone]

Sdima1357, быстрее будет решение с массивом, которое я привёл чуть выше, даже для unicode строк массив не будет слишком большим(1024 элемента)

[Sdima1357]

devalone, Согласен

Answer 2

[Mercury13]

3 тоже есть, так что правильный ответ 3. Ошибка тройная.

for(size_t z = 0; z < b.length(); z++){
        if(a.find(b[z]) != std::string::npos){

1. Индексы строк в STL беззнаковые, и компилятор может ругаться на сравнение знакового целого и беззнакового.
2. На что тут 4, если есть s.length()
3. Знак «не найдено» — std::string::npos.

Comments

[StrapusCactus]

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

std::string::npos - это просто знак не найдено? Или есть об этом интересная информация?

[Mercury13]

StrapusCactus, Да я понял.
Эта константа совпадает с std::numeric_limits<size_t>::max() и означает «не найдено» (если на выходе) или «до конца строки» (если на входе).
www.cplusplus.com/reference/string/string/npos

[StrapusCactus]

Спасибо =)