1988 – Nomi incompleti

Si richiede di definire una procedura simile a quella che permette ad alcuni sistemi operativi di accettare nomi incompleti di file.

È dato un insieme lineare e finito (array o lista) i cui elementi sono stringhe di caratteri alfanumerici stampabili, già memorizzato sul file di nome ARCHIVI, caricabile interamente in memoria centrale sotto forma di tabella.

In tale tabella va cercata una stringa di input producendo in output un messaggio che indichi l’esito della ricerca se anche l’input è solo alfanumerico.

Se però l’input contiene almeno uno dei caratteri speciali ? e * l’output richiesto è differente e deve consistere di un elenco di tutte le stringhe della tabella che risultino, secondo quanto segue, uguali a quella di input; un apposito messaggio indicherà l’assenza di uguaglianze.

  1. Il carattere ? va ritenuto uguale a qualsiasi carattere si trovi nella sua stessa posizione entro una stringa della tabella.
    Per esempio, Z?PPA deve risultare uguale a ZAPPA, ZEPPA, ZUPPA, Z9PPA, ecc.
  2. Il carattere * va ritenuto uguale a qualsiasi sottostringa (compresa quella vuota) si trovi nella sua stessa posizione.
    Per esempio, un input costituito dal solo * deve risultare uguale a qualsiasi stringa; Z* risulta uguale a Z ma anche a ZIO o a ZUZZURELLONE.
  3. Componendo i due punti precedenti, Z??* deve risultare uguale a qualunque stringa di almeno tre caratteri che inizi con Z.

Il candidato produca un’analisi del problema fornendo eventuali condizioni aggiuntive.
Si richiede inoltre di sviluppare l’algoritmo e la codifica in un linguaggio di programmazione conosciuto di uno o più segmenti del programma.