Подсчет подмножеств двоичного шаблона

Question

У меня есть A = набор строк и B = отдельная строка. Я хочу посчитать количество вхождений из B в A.

Пример:

A:
10001
10011
11000
10010
10101

B:
10001

result would be 3.(10001 is a subset of 10001,10011,10101)

Так что мне нужна функция, которая принимает набор и строку и возвращает int.

int myfunc(set<string> , string){
int result;
// My Brain is melting
return result ;
}

редактировать: 00000 не должно быть подмножеством чего-либо!

Answer 1

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

Если, однако, набор строк обрабатывается только один раз, вам лучше просто просмотреть набор и вручную проверить каждую из них. От руки, примерно так:

int myfunc(set<string> in, string search){
    assert(search.length() <= 32);
    int result = 0;
    for(set<string>::iterator iIn = in.begin(); iIn != in.end(); ++iIn)
    {
       bool isSubset = true;
       if (iIn->length() != search.length()) // Is this guaranteed?
           isSubset = false;
       for (int iSearch = 0; isSubset && iSearch < search.length; ++iSearch)
           if (search[iSearch] == '1' && (*iIn)[iSearch] == '0')
               isSubset = false;
       if (isSubset)
           ++result;
    }
    return result;
}

Или же конвертировать в длинную первую версию:

int myfunc(set<string> in, string search){
    int result = 0;
    long searchInteger = strtol(search.c_str(), NULL, 2);
    for(set<string>::iterator iIn = in.begin(); iIn != in.end(); ++iIn)
        if ((strtol(iIn->c_str(), NULL, 2) & searchInteger) == searchInteger)
            ++result;
    return result;
}

Answer 2

Вы можете использовать двоичную and функцию:

if( ( pattern & listItem[i] ) == pattern )
{
  // match
}

Оба, pattern и listItem [i] должны быть числовыми типами данных для применения and.

Answer 3

Вы можете преобразовать эти строки в целое число и сделать поразрядно - и против маски:

if ((input & mask) == mask) {
    /* matches */
}

Answer 4

Можем ли мы предположить, что все строки имеют одинаковую длину и состоят только из символов 0 и 1?

Хорошо, да, тогда, если вы можете найти функцию для преобразования двоичной строки в целое число, тогда нужно поступить так, как другие предлагали использовать операцию 'и'.

В противном случае возможна что-то вроде:

int count = 0;
for (k=0; k<sizeofA; k++) {
  for (j=0; j<lengthOfString; j++)
      if ( ('1'==B[j]) && ('1' != A[k][j])) break;
  if (j==lengthOfString) count++;
}