Count subset of binary pattern ..

Question

Hi there .

I have a A=set of strings and a B=seperate string. I want to count the number of occurences in from B in A.

Example :

A:
10001
10011
11000
10010
10101

B:
10001

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

So i need a function that takes a set and string and returns an int.

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

edit : 00000 shouldn't be a subset of anything !

Answer 1

You could convert these strings to an integer and do a bitwise-and against the mask:

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

Answer 2

You can use a binary and function:

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

Both, pattern and listItem[i] have to be numerical datatypes to apply the and.

Answer 3

Can we assume that the strings are all the same length and consist of only characters 0 and 1?

Ok, Yes, Then if you can find a function to convert a binary string to an integer, then doing as others have suggested using the 'and' operation is the way to go.

Otherwise a possibility is something like:

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

Answer 4

If you have control over the input, and these strings are really supposed to represent bitmasks, then you probably want to keep them as integers of some sort and use bitmasks as suggested by others. Otherwise, if your stuck with dealing with them as strings, and you're going to use the same set of strings to search through multiple times, you're still better off converting them to integral bitmasks.

If, however, the set of strings is only being processed once, you're better off just going through the set and manually checking each once. Offhand, something like this:

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

Or else the convert to long first version:

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