Matematické Fórum

Takže, v cvičeniach z knihy Rozumíme C++ mám navrhnúť a implementovať program, ktorý vytvára permutovaný index. Je to pre mňa netriviálna úloha. Zatiaľ som dospel k tomuto:

pozn. k permutovanému indexu http://en.wikipedia.org/wiki/Key_Word_in_Context tu je to pekne vysvetlené.

Takže datovú štruktúru som po viacerých uváženiach zvolil

vector< list<string> > vety;

Najprv teda do toho načítam všetky vety, potom urobím rotácie, vytriedim, odrotujem a formátujem výstup.

Všetko viem ako spraviť, len ma nevie napadnúť, ako si pamätať začiatočné slová aby som po vyiriedení úspešne odrotovať.
Nemáte nejaký nápad?

Tu je presné znenie zadania:

Design and implement a program to produce a permuted index. A permuted index is one in which each phrase is indexed by every word in the phrase. So, given the following input,

The quick brown fox
jumped over the fence
the output would be

          The quick     brown fox
jumped over the     fence
The quick brown     fox
                           jumped over the fence
             jumped    over the fence
                   The    quick brown fox
     jumped over     the fence
                            The quick brown fox
A good algorithm is suggested in The AWK Programming Language by Aho, Kernighan, and Weinberger (Addison-Wesley, 1988). That solution divides the problem into three steps:

Read each line of the input and generate a set of rotations of that line. Each rotation puts the next word of the input in the first position and rotates the previous first word to the end of the phrase. So the output of this phase for the first line of our input would be
The quick brown fox
quick brown fox The
brown fox The quick
fox The quick brown
Of course, it will be important to know where the original phrase ends and where the rotated beginning begins.
Sort the rotations.
Unrotate and write the permuted index, which involves finding the separator, putting the phrase back together, and writing it properly formatted.