Oh, Sab! P21214


Statement
 

pdf   zip

thehtml

Even though stereotypically associated with psychedellic and hard rock musical acts of the sixties and seventies, recent research suggests that the practice of backmasking is actually older than that, and places its origins in the work of the probably most famous Japanese poet of the Edo period, Matsuo Bashō.

According to Professor John Robert Page at the University of Hindemburg, most of Bashō’s best-known haikus contain at least pagan, if not openly satanic, hidden messages against the publicly accepted Buddhist and Shintoist practices of the time. Some of them are extremely blunt and violent—take for instance these famous verses from the Philippine Stanzas:

my lima fire
the viceruoy watches sunsets
will ikebana practice

Reading these words backwards, a message appears, clear as day:

ecitcarp anabeki lliw
stesnus sechtaw
youreciv eht
eri
f amil ym

In order to support his claims, Doctor Page reported about a press statement preserved at the Japanese National Library, where Bashō’s publisher reiterates that “our books only read in one direction: right-to-left”, allegedly to dismiss rumours about hidden messages in the poet’s work. It is also suspected that these rumours contributed to Bashō’s early retirement and self-imposed confinement to focus on the fishing of mudsharks and some related hobbies.

Input

Input starts with a natural number n, followed by n different words, followed by the number of haikus m, followed by m haikus, one per line. Assume that all words are made up of only lowercase letters, and that each haiku consists of lowercase letters, whitespaces and ‘/’.

Output

For each input haiku, print a line with its hidden message: Consider the reversed haiku (ignoring spaces and slashes), and print any given word that can be found when reading the haiku from left to right, avoiding all overlaps. In case of an overlap, always prefer the word that starts first (at the leftmost position), and longer words in the event of another tie. Separate words with spaces. If a kaiku has no hidden words, just print “-”.

Observation

The expected solution of this problem has time complexity Θ(n · ℓ), where ℓ is the sum of the lenghts of the haikus.

Public test cases
  • Input

    8
    family
    kill
    your
    yadayadayada
    z
    zz
    zb
    zbc
    4
    my lima fire / the viceruoy watches sunsets / will ikebana practice
    oh my dear reader / did you really expect something / hidden in plain sight
    yada yada ya / yada yada yada ya / yada yada ya
    bz zcb / zzz
    

    Output

    kill your family
    -
    yadayadayada
    zz zbc zz
    
  • Information
    Author
    Edgar Gonzalez
    Language
    English
    Official solutions
    C++
    User solutions
    C++