PRHYME - Perfect Rhyme

A perfect rhyme is not a crime,
it is something that exceeds time, 
a bit of science, a piece of art, 
soft as a pillow, sharp as a dart.

Everyone tried it, but only few chosen ones succeeded. It is a hard task with an unclear path, but a famous end – should you reach it. Many compare it to finding the Holy Grail, or even to finding Waldo. The task is to find a perfect rhyme.

Problem specification

Given is a wordlist L, and a word w. Your task is to find a word in L that forms a perfect rhyme with w. This word u is uniquely determined by these properties:

  • It is in L.
  • It is different from w.
  • Their common suffix is as long as possible.
  • Out of all words that satisfy the previous points, u is the lexicographically smallest one.

Notes

A prefix of a word is any string that can be obtained by repeatedly deleting the last letter of the word. Similarly, a suffix of a word is any string that can be obtained by repeatedly deleting the first letter of the word.

For example, consider the word different.

This word is both its own prefix and suffix. Its longest other prefix is differen, and its longest other suffix is ifferent. The string rent is its yet another, even shorter suffix. The strings eent and iffe are neither prefixes nor suffixes of the word different.

Let u and v be two different words. We say that u is lexicographically smaller than v if either u is a prefix of v, or if i is the first position where they differ, and the i-th letter of u is earlier in the alphabet than the i-th letter of v.

For example, dog is smaller than dogs, which is smaller than dragon (because o is less than r).

Input specification

The input file consists of two parts. The first part contains the wordlist L, one word per line. Each word consists of lowercase English letters only, and no two words are equal.

The first part is terminated by an empty line.

The second part follows, with one query word w per line.

You may assume that in either part of the input, the length of a word will be no more than 30. And the number of words in each part of the input will be no more than 250000. The input file will be less than 5MB.

Output specification

For each query in the input file output a single line with its perfect rhyme. The output must be in lowercase.

Example

input:
perfect
rhyme
crime
time

crime
rhyme

output:
time
crime

In the second test case, there were two candidates that had an equally long common suffix (crime and time), the lexicographically smaller one was chosen.

Warning: large input/output data, be careful with certain languages

Added by:Fudan University Problem Setters
Date:2008-05-26
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:IPSC 2008

hide comments
2021-05-11 17:31:35 Rafail Loizou
Dude I brute force this and I still get a wrong answer... smh
2019-05-16 21:11:19 cegprakash
Just got ACC. It is guaranteed that there are at least two unique words in the insertion list.

Last edit: 2019-05-16 22:41:13
2019-03-27 16:12:01
im loving this task extremely so
2015-03-14 10:20:40 :D
This is a problem where you can easily generate random test data. Generate words from a small alphabet (like 'a' and 'b' only), so that it will create a lot of non-trivial suffix relations. Then solve it with brute force, by comparing every query to every entry on wordlist.
2015-01-14 05:20:08 Ashwin
more test cases ??
2014-07-30 09:04:34 yaswanth
test case 1:
a
aa
aaa

aa
aaa
aaaa
a

ans:
aaa
aa
aaa
aa
Test case 2:
abc
def

abc
def

ans:
def
abc

Last edit: 2014-07-30 09:05:20
2014-01-01 18:07:23 cegprakash
awesome problem! Is it guaranteed that there are atleast two unique words in the wordList?
2013-02-25 01:18:35 Rocker3011
the input should not have been so annoying, for real
2013-01-06 17:40:42 Alejandro
in the case
aaaaa

aaaaa



what should be the answer?


Edit: Read problem statement

Last edit: 2013-02-08 15:45:05
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.