Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

HW8rec - Problema sequenza parole

S
Shad87 (740 points)
6 9 11
in Recupero HW8 by (740 points)
recategorized by

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?

477 views

1 Answer

andrea.sterbini (207920 points)
750 1267 2373
by (208k 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)
6 9 11
by (740 points)
Ok, grazie 1000 prof!