Find string from stream

find_substring_from_stream.cpp

/* Program: Find the character substring location of the input character string.
 * Author: Jyun-Yao Huang ([email protected])
 * License: Free
 */

#include <iostream>
#include <bitset>
#include <string>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

/* ***** Definition ***** */

#define _SIZE_OF_PATTERN_ 6
#define _NUM_OF_ALPHABETS_ 4

/* ***** End ***** */

/* Members */
map<char,size_t> m_mapInputAlphabet_;

/* ***** End ***** */

bool fnCompareBitMap(const vector<bitset<_SIZE_OF_PATTERN_> > & vecList1, const vector<bitset<_SIZE_OF_PATTERN_> > & vecList2)
{
    bool bCheck = true;
    size_t nSize = vecList1.size();
    if(nSize != vecList2.size())
        return false;
    vector<bitset<_SIZE_OF_PATTERN_> >::const_iterator it1=vecList1.begin();
    vector<bitset<_SIZE_OF_PATTERN_> >::const_iterator it2=vecList2.begin();
    for(size_t nIdx=0; bCheck && nIdx < nSize; ++nIdx)
    {
        bCheck = bCheck && (*it1 == *it2);
        ++it1;
        ++it2;
    }
    return bCheck;
}


//void fnLoadInputAlphabet(char * ptrcInput, size_t nSize)
void fnLoadInputAlphabet(const string & strInput)
{
    for(string::const_iterator it=strInput.begin(); it!=strInput.end(); ++it)
    {
        size_t nMax=m_mapInputAlphabet_.size();
        m_mapInputAlphabet_.insert(pair<char,size_t>(*it,nMax));
    }
}

//@Function: bool fnEndOfCharString(char &)
//@Brief: check the input character is the end of charstring.
//@Input: reference type character.
//@Output: True for success, or false.
bool fnIsEndOfCharString(const char & cTarget)
{
    return cTarget=='\0';
}

//@Function: void fnShowBitsetInfo( vector<bitset<_SIZE_OF_PATTERN_> > & )
//@Brief: show the information of input bitset vector
//@Input: reference type vector<bitset<_SIZE_OF_PATTERN_> >
//@Output: the information of input
void fnShowBitsetInfo( vector<bitset<_SIZE_OF_PATTERN_> > & source)
{
    for(size_t nIdx=0; nIdx <4; ++ nIdx)
    {
        cout << source[nIdx] << endl;
    }
}

//@Function: void fnSetBitListViaSettedAlphabet(char & cInput, vector<bitset<_SIZE_OF_PATTERN_> > & bitsetTarget, int nLocation)
//@Brief: Set bit-list using input character with corresponding location
//@Input: cInput: the wanna found character.
//        bitsetTarget: the target list.
//        nLocation: the corresponding location.
//@Output: None.
void fnSetBitListViaSettedAlphabet(const char & cInput, vector<bitset<_SIZE_OF_PATTERN_> > & bitsetTarget, size_t nLocation)
{
    bitsetTarget[m_mapInputAlphabet_.find(cInput)->second].set(nLocation);
}

int main(int argc, char * argv[])
{
    string strTargetPattern("ACGTAT"); // Done.
    string strInputString("AATACTGTAAACGACTGACAGATACCATTCAGACGTATCATGA"); // Done.
    set<char> setAlphabet;
    // Assume that there are 4 alphabets.
    vector<bitset<_SIZE_OF_PATTERN_> > vecBitSetList(_NUM_OF_ALPHABETS_);
    // Compared Sample Pattern.
    vector<bitset<_SIZE_OF_PATTERN_> > vecSampleList(_NUM_OF_ALPHABETS_);

    // Load BitSet characters.
    //fnLoadInputAlphabet(sTargetPattern,_SIZE_OF_PATTERN_);
    fnLoadInputAlphabet(strTargetPattern); // Done.

    // Create BitSetList of Target.
    size_t nIdx =0;
    for(string::const_iterator it=strTargetPattern.begin(); it!=strTargetPattern.end(); ++ it)
    {
        fnSetBitListViaSettedAlphabet(*it,vecBitSetList,nIdx++);
    }

    for(size_t nIdx=0;nIdx<strInputString.size() ; ++ nIdx)
    {
        if(fnIsEndOfCharString(strInputString[nIdx]))
            break;

        // Shifting
        for(int nTempIdx=0;nTempIdx < _NUM_OF_ALPHABETS_; ++ nTempIdx)
        {
            vecSampleList[nTempIdx] >>=1;
        }

        fnSetBitListViaSettedAlphabet(strInputString[nIdx],vecSampleList,strTargetPattern.size()-1);
        // Comparing.
        if(nIdx>= strTargetPattern.size()-1)
        {
            if(strInputString[nIdx]==strTargetPattern[strTargetPattern.size()-1])
            {
                if(fnCompareBitMap(vecBitSetList,vecSampleList))
                {
                    cout << "Location:" << nIdx-(strTargetPattern.size()-1) << endl;
                    return 0;
                }
            }
        }
    }

    return 0;
}