Welk woord komt op de plaats van het vraagteken om deze woordenreeks af te werken?

Space, Cinema, Ester, Abaci, Cabaret, Seamen, ?

De volledige woordenreeks vormt een palindroom: je krijgt dezelfde reeks letters als je de letters van de woorden van links naar rechts of van rechts naar links leest. Het ontbrekende woord is dus Icecaps:

Space, Cinema, Ester, Abaci, Cabaret, Seamen, Icecaps

Opgave

Bij dit soort raadsel moet je op het einde van een gegeven woordenreeks één woord aanvullen zodat de volledige woordenreeks een palindroom vormt. Het ontbrekende woord kan je vinden door eerst alle letters van de gegeven woorden achter elkaar te schrijven. Daarbij zet je alle letters om naar kleine letters, om geen onderscheid te maken tussen hoofdletters en kleine letters. We noemen dit de voorwaartse reeks:

spacecinemaesterabacicabaretseamen

Daarna keer je de volgorde van de letters uit de voorwaartse reeks om. We noemen dit de achterwaartse reeks:

nemaesterabacicabaretseamenicecaps

Vervolgens zoek je de langste suffix van de voorwaartse reeks die ook een prefix is van de achterwaartse reeks. We hebben die langste gemeenschappelijke suffix/prefix hieronder in het groen aangeduid:

spacecinemaesterabacicabaretseamen*******
*******nemaesterabacicabaretseamenicecaps

Als je die langste gemeenschappelijke suffix/prefix als prefix weghaalt van de achterwaartse reeks, dan hou je het ontbrekende woord over. We hebben dat ontbrekende woord hierboven in het blauw aangeduid.

Prefix en suffix

Een prefix van een woord $$w$$ bestaat uit een reeks van één of meer letters aan begin van $$w$$. Zo is appel bijvoorbeeld een prefix van appelboom.

Een suffix van een woord $$w$$ bestaat uit een reeks van één of meer letters op het einde van $$w$$. Zo is boom bijvoorbeeld een suffix van appelboom.

Invoer

De eerste regel bevat een getal $$t \in \mathbb{N}_0$$. Daarna volgen $$t$$ regels die elk één woord bevatten dat enkel uit letters bestaat.

Uitvoer

De uitvoer bestaat uit de volgende vier regels:

  1. de voorwaartse reeks voor de gegeven reeks van $$t$$ woorden, gevolgd door evenveel sterretjes (*) als het aantal letters in het ontbrekende woord

  2. evenveel sterretjes (*) als het aantal letters in het ontbrekende woord, gevolgd door de achterwaartse reeks voor de gegeven reeks van $$t$$ woorden

  3. evenveel gelijkheidstekens (=) als het aantal karakters op de eerste (en ook de tweede) regel van de uitvoer

  4. het ontbrekende woord waarmee de gegeven reeks van $$t$$ woorden kan afgewerkt worden, geschreven als een hoofdletter gevolgd door kleine letters

Voorbeeld

Invoer:

6
Space
Cinema
Ester
Abaci
Cabaret
Seamen

Uitvoer:

spacecinemaesterabacicabaretseamen*******
*******nemaesterabacicabaretseamenicecaps
=========================================
Icecaps