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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
