开发者

Count subset of binary pattern

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 ;
}
开发者_如何学JAVA

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


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


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.


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

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


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

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜