/* * Kernighan-Pike: Practice of Programming, 1998 * Addison-Wesley */ /* * Az STL elemei template-ek, tehát számos * headert kell betölteni: * * adatszerkezetenként külön-külön * es az algoritmusokat egyben * */ #include <string> // std::string #include <iostream> // standard input-output #include <deque> // sor (lopop, loext, hipop, hiext) #include <map> // rendezőfa #include <vector> // sorozat (hiext és hipop) using namespace std; const int nwords = 15000; // max output méret, szavakban //const int npref = 1; const int npref = 3; // fokszám: figyelembe vett előző állapotok char NONWORD[] = "\n"; // extremális elem // ez a típus képes tárolni az állapotátmeneteket typedef map< deque<string>, vector<string> > map_t; // ez a változó tárolja a mi állapotátmeneteinket map_t statetab; // felépíti az állapotátmeneteket: // egy adott prefix után milyen s szó következik void add( deque<string>& prefix, const string& s) { if ( prefix.size() == npref ) // warning: unsigned==signed { statetab[prefix].push_back(s); prefix.pop_front(); // kiveszi a legrégebbi állapotot } prefix.push_back(s); // berakja az újat } // eof-ig felépíti a táblánkat void build( deque<string>& prefix, istream& in) { string buf; while ( in >> buf ) add( prefix, buf); // közben prefix jobbra lép } // outputot generál void generate(int nwords) { deque<string> prefix; int i; int len = 0; for ( i = 0; i < npref; ++i) add( prefix, NONWORD); // TODO: véletlenszámgenerátort inicializálni for ( i = 0; i < nwords; ++i) { // kiválasztjuk a prefix-hez tartozó szavak sorozatát vector<string>& suf = statetab[prefix]; // és véletlenszerűen választunk egy szót const string& w = suf[rand() % suf.size()]; if ( w == NONWORD ) break; // végállapot: befejezzük a generálást // csak a sorok tördelése miatt if ( len + w.size() > 70 ) { cout << endl; len = 0; } cout << w << " "; len += w.size()+1; // következő prefix előállítása prefix.pop_front(); prefix.push_back(w); } } int main() { deque<string> prefix; // kezdeti állapot for ( int i = 0; i < npref; ++i) add( prefix, NONWORD); build( prefix, cin); // táblázat felépítése eof-ig add( prefix, NONWORD); // végállapot beállítása generate(nwords); // output: legfeljebb nwords szó return 0; }