Met software zoals Swype¹ of SwiftKey² kunnen smartphonegebruikers tekst invoeren door hun vinger over het schermtoetsenbord te slepen in plaats van afzonderlijk op elke letter te drukken.

Opgave

Schrijf een bash shell script waaraan als eerste argument een reeks van twee of meer letters moet doorgegeven worden. Aan het shell script moet ook nog een woordenboek doorgegeven worden, dat bestaat uit een lijst van woorden (enkel letters) die allemaal op een afzonderlijke regel staan. De locatie van het woordenboek (een tekstbestand) kan als tweede argument aan het shell script doorgegeven worden. Als geen tweede argument aan het shell script wordt doorgegeven, dan moet het woordenboek uitgelezen worden uit stdin. Het shell script mag ervan uitgaan dat de argumenten die eraan doorgegeven worden geldig zijn, zonder dat dit expliciet moet gecontroleerd worden.

Het shell script moet naar stdout een lijst uitschrijven van alle woorden uit het woordenboek die uit minstens vijf letters bestaan en die met de gegeven reeks letters kunnen gevormd worden. Een woord kan gevormd worden uit een reeks letters als de volgende voorwaarden voldaan zijn:

1. het woord begint met de eerste letter uit de reeks

2. het woord eindigt met de laatste letter uit de reeks

3. de letters van het woord vormen een deelreeks³ van de reeks letters; opeenvolgende gelijke letters in het woord kunnen wel op dezelfde letter uit de reeks afgebeeld worden (het woord queen kan bijvoorbeeld gevormd worden met de reeks letters qxuyezn, ondanks het feit dat de letter e maar één keer in de reeks letters voorkomt)

Hierbij wordt geen onderscheid gemaakt tussen hoofdletters en kleine letters. Bij het oplijsten van de woorden moet hun oorspronkelijke volgorde uit het woordenboek aangehouden worden.

Voorbeeld

Onderstaande voorbeeldsessie geeft aan hoe het shell script (dat we wandelingen genoemd hebben) moet kunnen gebruikt worden. Hierbij gaan we ervan uit dat het tekstbestand woordenboek.txt⁴ zich in de huidige directory bevindt.

$ wandelingen "qwertyuihgfcvbnhjk" < woordenboek.txt
quick
$ wandelingen "qwertyuytresdftyuiokn" < woordenboek.txt
queen
question
$ wandelingen "ghijakjthoijerjidsdfnokg" woordenboek.txt
gaeing
garring
gathering
gating
geeing
gieing
going
goring

Voor het eerste voorbeeld uit bovenstaande sessie tonen we hieronder hoe het woord quick uit de gegeven reeks letters (bovenaan de figuur) kan gevormd worden.

Voor het tweede voorbeeld uit bovenstaande sessie tonen we hieronder hoe de woorden queen en question kunnen gevormd worden uit de gegeven reeks letters (in het midden van de figuur). Let hierbij op het feit dat de twee opeenvolgende letters e in het woord queen beide gebruikmaken van dezelfde letter e in de reeks letters.