HW8rec - Problema sequenza parole

S
Shad87 (740 points)
5 9 11
asked Jan 4, 2020 in Recupero HW8 by Shad87 (740 points)
recategorized Jan 6, 2020 by andrea.sterbini

Ho un piccolo problema con l'HW8rec riguardante la sequenza corretta delle parole tratte dai vari file di testo.
Nella traccia dell'esercizio viene dichiarato che esiste una sola sequenza valida, trovabile grazie al controllo dei caratteri in coda ad una parola e in testa ad un'altra. Viene anche detto esplicitamente che, in caso due parole abbiano in comune una stessa sottostringa, si deve prendere la più lunga.
Il mio problema è che, in alcuni file, esiste almeno una parola che si "lega" a più di una seconda parola per lo stesso numero di caratteri. In che modo dovrei scegliere la seconda parola in modo corretto?


Riporto un paio di esempi:

File: pezzi_3.txt
Sequenza indici: [10, 1, 5, 0, 8, 9, 2, 13, 12, 3, 7, 11, 6, 14, 4]

In questo caso la linea di testo numero 3 "itinvoluptatevelitessecillu" si dovrebbe collegare, secondo la lista indici, alla linea 7 "umdoloreeufugiatnullapariat", ma si collegherebbe correttamente anche alla linea 6 "upidatatnonproident,suntinc", in entrambi i casi, ovviamente, per lo stesso numero di caratteri (uno solo, evidenziato in rosso). 


File: pezzi_4.txt
Sequenza indici: [11, 12, 6, 3, 8, 10, 0, 14, 5, 9, 4, 15, 2, 1, 7, 13, 16]

Qui si verifica lo stesso problema di prima: la linea di testo numero 6 "oriadeigrafi,un", sempre secondo la lista degli indici, si dovrebbe collegare alla linea 3 "ncamminoinungr" ma si collega corrattemente anche alla linea 0 "ntato)èdettoh"  per lo stesso numero di caratteri (anche in questo caso è solamente uno, evidenziato in rosso).

Qualche consiglio?

384 views

1 Answer

andrea.sterbini (172780 points)
513 935 1789
answered Jan 4, 2020 by andrea.sterbini (172,780 points)

Devi provare entrambi i casi e vedere quale è giusto, esiste una sola soluzione che:

  • contiene tutte le parole
  • due parole consecutive hanno un suffisso/prefisso comune

Se di queste corrispondenze multiple ce ne sono N, può essere necessario esaminare un numero di casi esponenziale in N

S
Shad87 (740 points)
5 9 11
commented Jan 4, 2020 by Shad87 (740 points)
Ok, grazie 1000 prof!