Check this program: #include <map> #include <string> #include <iostream> #include <algorithm> #include <iterator>
using namespace std; class Range : public pair<const char*, const char*> { public: size_t size() const { return second - first; } Range(const char* f=0, const char * s=0) : pair<const char*, const char*>(f ,s) {} }; ostream & operator << (ostream & out, const Range& r) { out<<"range size: "<<r.size()<<" ["; copy(r.first, r.second, ostream_iterator<char>(out, "")); out<<"]"; return out; } typedef map<char, int> SetCnt; // array based implementation will have complexity O(m) bool checkSet(const SetCnt & setCnt) { SetCnt::const_iterator sIt = setCnt.begin(), sEnd = setCnt.end(); for (SetCnt::const_iterator sIt = setCnt.begin(); sIt != sEnd; + +sIt ) { if (sIt->second == 0) { return false; } } return true; } // array based implementation will have complexity O(1) bool checkAndShrink(SetCnt & setCnt, char c) { SetCnt::iterator sIt = setCnt.find(c); if (sIt == setCnt.end()) { return true; } if (sIt->second > 1) { sIt->second--; return true; } return false; } // aproximate complexity is O(n*m + m) // where n - is size of input sequence and m - is number of key words. Range solve(const char * strBegin, const char * strEnd, const char * setBegin, const char * setEnd) { SetCnt setCnt; // complexity O(m) for (const char * cIt = setBegin; cIt != setEnd; cIt++ ) { setCnt[*cIt] = 0; } bool solved = false; Range range(strBegin, strEnd), result(range); for (const char * sIt = strBegin; sIt != strEnd; sIt++ ) { SetCnt::iterator it = setCnt.find(*sIt); if (it != setCnt.end()) { setCnt[*sIt] += 1; range.second = sIt + 1; if (checkSet(setCnt)) { solved = true; while (checkAndShrink(setCnt, *range.first)) { range.first++; } if (result.size() > range.size()) { result = range; } // Debug cout<<range<<endl; } } } return solved ? result : Range(0, 0); } int main() { const char * string = "abrebbqbcdfagbasdfbbaggqqebbcg--324c"; const char * set = "abc"; Range range = solve(string, string + strlen(string), set, set + strlen(set)); if (range.size()) { cout<<"The shortes subsequence is: "<<range<<endl; } else { cout<<"No solution..."<<endl; } return 0; } --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---