Topolino e i palindromi

Corso Online per Potenziare le Competenze Digitali

Topolino sta effettuando alcuni scavi archeologici per studiare le comunicazioni che avvenivano tra i membri dell’antica civiltà dei Mayali.
Con l’esperienza acquisita grazie agli anni di ricerca, Topolino sa che i Mayali comunicavano  esclusivamente per mezzo di palindromi.
Una stringa si dice palindroma quando si può leggere in modo equivalente sia da destra che da sinistra (ovvero, è uguale alla sua versione specchiata), alcuni esempi di palindromi sono Anna, oppure Ed Irene se ne ride per finire con quello che Topolino preferisce in assoluto (sebbene lo consideri un’espressione dell’ignoranza che dilagava nel popolo dei Mayali in ambito di genealogia), il quale recita: I topi non avevano nipoti.

Purtroppo, le iscrizioni che Topolino ha trovato fin ora sono molto danneggiate, molte delle lettere sono diventate completamente illeggibili a causa del tempo.
Aiuta Topolino a capire se una certa iscrizione può appartenere o no alle comunicazioni del popolo dei Mayali.

Dati di input

Il file input.txt è composto da una sola riga di testo che rappresenta l’iscrizione che Topolino intende analizzare.
La riga di testo può contenere spazi, lettere minuscole (dalla a alla z), ed il carattere * con il quale viene indicata una lettera talmente danneggiata da essere illeggibile.

Dati di output

Il file output.txt dovrà contenere una possibile interpretazione dell’iscrizione, qualora essa sia un valido candidato ad essere una comunicazione del popolo dei Mayali.
Se non dovesse essere possibile interpretare l’iscrizione, allora il file dovrà contenere la frase: impossibile.

Assunzioni

• La lunghezza della riga di testo in input non supera i 1000 caratteri (se si usano gli array di char, fare attenzione ad allocare spazio sufficiente per il carattere terminatore!).
• Se esistono diverse possibili interpretazioni dell’iscrizione, è sufficiente stamparne una qualunque.
• Il carattere * sostituisce sempre e solo una lettera (da a a z), non può sostituire uno spazio.

Esempi di input/output

input.txt	output.txt
i topi n*n a*ev*no n*pot*	i topi non avevano nipoti
la lazio vince lo scudetto	impossibile

/*
 www.valcon.it
 Corso Online per Potenziare le Competenze Digitali
 Topolino e i palindromi
*/

#include
#include
#include
#define LMAX 1000
using namespace std;

int main()
{ 
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");

    char frase[LMAX+1];
	fin.getline(frase, LMAX);
																						
    int pos1=0;
    int pos2=strlen(frase)-1;
    while(pos1 < pos2)
    {
    	     if(frase[pos1] == ' '        )   pos1++;
    	else if(frase[pos2] == ' '        )   pos2--;    		
    	else if(frase[pos1] == '*'        )   frase[pos1++]=frase[pos2--];    	                                    
    	else if(frase[pos2] == '*'        )   frase[pos2--]=frase[pos1++];
    	else if(frase[pos1] == frase[pos2]) { pos1++; pos2--;              }
		else                                  break;
	}    
    if(pos1 >= pos2) fout << frase;
    else	         fout << "impossibile";

	return 0;
}