000
23.01.2009, 10:04 Uhr
mike
Pinguinhüpfer
(Operator)
|
Hi
Hab es selbst mal gebraucht und in einem anderen (Ruby-)Forum war es auch ein Rätsel:
Man hat eine Zahlensequenz (natürliche Zahlen): 0 1 2 3 4 5 6 4 5 6 4 5 6 ...
Und muss die kleinste sich wiederholende Sequenz suchen: hier eben 4 5 6
Hier meine Lösung - die Lösung ist gewachsen also evntl. etwas nicht C++lerisch 
| C++: |
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <stdlib.h>
#include <time.h>
using namespace std;
bool subSort(vector<unsigned> const &a, vector<unsigned> const &b)
{
/* Thats bad - first is bigger than second array */
if(a.size() > b.size())
{
pair<vector<unsigned>::const_iterator, vector<unsigned>::const_iterator > elem;
elem = mismatch(b.begin(), b.end(), a.begin());
/* Completly included */
if(elem.first == b.end())
return false;
if(*elem.first < *elem.second)
return false;
else
return true;
}
pair<vector<unsigned>::const_iterator, vector<unsigned>::const_iterator > elem;
elem = mismatch(a.begin(), a.end(), b.begin());
/* Completly included */
if(elem.first == a.end())
return true;
if(*elem.first < *elem.second)
return true;
else
return false;
}
int main()
{
ostringstream debugOutput;
vector<unsigned> src;
srand ( time(NULL) );
/* ein paar "falsche" Zahlen */
for(unsigned i=0; i < 10; i++)
{
src.push_back( rand() % 10 );
}
for(unsigned i=0; i < 50; i++)
{
src.push_back(7);
src.push_back(2);
src.push_back(3);
src.push_back(4);
}
/* ein paar "falsche" Zahlen */
for(unsigned i=0; i < 10; i++)
{
src.push_back( rand() % 10 );
}
copy(src.begin(), src.end(), ostream_iterator<unsigned>( debugOutput, " " ));
cout << debugOutput.str() << endl;
cout << "start build" << endl;
/* Build suffix tree */
vector<vector<unsigned> > vec;
vec.resize(src.size());
vector<unsigned>::iterator srcit = src.begin();
for(size_t index = 0; index < src.size(); index++, srcit++)
{
vec[index].resize(distance(srcit, src.end()));
copy(srcit, src.end(), vec.at(index).begin());
}
cout << "end build" << endl;
/* Sort the tree */
cout << "start sort" << endl;
sort(vec.begin(), vec.end(), subSort);
cout << "end sort" << endl;
cout << "start search"<<endl;
/* Go through the array and find best sequence */
vector<vector<unsigned> >::iterator it;
vector<unsigned> lastcommon;
vector<unsigned> currcommon;
vector<unsigned> prevdiff;
vector<unsigned> currdiff;
unsigned counter = 0, maxcounter = 0;
size_t bestdist;
vector<unsigned> bestdiff;
for(it = vec.begin(); it != vec.end(); it++)
{
if(it + 1 == vec.end())
break;
pair<vector<unsigned>::const_iterator, vector<unsigned>::const_iterator > elem;
size_t dist;
lastcommon = currcommon;
if(it->size() > (it+1)->size())
{
elem = mismatch((it + 1)->begin(), (it + 1)->end(), it->begin());
dist = distance(static_cast<vector<unsigned>::const_iterator>((it + 1)->begin()), elem.first);
currcommon.resize(dist);
copy(static_cast<vector<unsigned>::const_iterator>((it + 1)->begin()), elem.first, currcommon.begin());
}
else
{
elem = mismatch(it->begin(), it->end(), (it + 1)->begin());
dist = distance(static_cast<vector<unsigned>::const_iterator>(it->begin()), elem.first);
currcommon.resize(dist);
copy(static_cast<vector<unsigned>::const_iterator>(it->begin()), elem.first, currcommon.begin());
}
if(dist > bestdist)
{
bestdist = dist;
}
/*******************************************************************************************/
prevdiff = currdiff;
if(currcommon.size() != 0 && lastcommon.size() != 0)
{
pair<vector<unsigned>::const_iterator, vector<unsigned>::const_iterator > elem;
size_t dist;
if(currcommon.size() > lastcommon.size())
{
elem = mismatch(lastcommon.begin(), lastcommon.end(), currcommon.begin());
if(elem.first == lastcommon.end())
{
dist = distance(elem.second, static_cast<vector<unsigned>::const_iterator>(currcommon.end()));
currdiff.resize( dist );
copy(elem.second, static_cast<vector<unsigned>::const_iterator>(currcommon.end()), currdiff.begin());
}
}
else
{
elem = mismatch(currcommon.begin(), currcommon.end(), lastcommon.begin());
if(elem.first == currcommon.end())
{
dist = distance(elem.second, static_cast<vector<unsigned>::const_iterator>(lastcommon.end()));
currdiff.resize( dist );
copy(elem.second, static_cast<vector<unsigned>::const_iterator>(lastcommon.end()), currdiff.begin());
}
}
}
else
{
counter = 0;
}
if(prevdiff.size() == currdiff.size())
{
if(equal(prevdiff.begin(), prevdiff.end(), currdiff.begin()))
{
counter++;
}
}
else
{
counter = 0;
}
if(counter > maxcounter)
{
maxcounter = counter;
bestdiff = currdiff;
}
}
cout << "end search"<<endl;
debugOutput.str("");
copy(bestdiff.begin(), bestdiff.end(), ostream_iterator<unsigned>( debugOutput, " " ));
cout << debugOutput.str() << endl;
}
|
Optimale Lösungen kommen sogar mit Störwerten innerhalb der Sequenz zurecht:
0 1 2 3 4 5 6 4 5 6 4 5 6 9 4 5 6 4 5 6 4 5 6
Wenn wer Zeit und Lust hat 
lg
--
Dieser Post wurde am 29.01.2009 um 20:14 Uhr von FloSoft editiert. |
