RICERCA PRESENZA SOTTOSTRINGA NELLE PAROLE

f
fred (320 points)
2 2 3
asked Nov 17, 2019 in HW4 obbligatorio by fred (320 points)
recategorized Nov 22, 2019 by andrea.sterbini
Avrei bisogno di qualche consiglio per quanto riguarda la ricerca della sottostringa segreta:

più che altro non so come implementare la ricerca tenendo conto allo stesso tempo che la sottostringa deve essere presente esattamente una volta per ogni parola..
674 views

8 Answers

s
scutigliani.luca (860 points)
6 10 15
answered Nov 17, 2019 by scutigliani.luca (860 points)

Prova utilizzando i set e la teoria degli insiemi. Il tipo set ha il metodo `.intersection` ! Inoltre puoi individuare le sottostringhe che si ripetono e non “candidarle” ad essere la stringa segreta.

Altrimenti c’è chi consiglia l’utilizzo dei dizionari, importando come chiave la sottostringa e come valore il numero di volte che si ripete nella frase. Trovo però che sia più inefficiente del metodo dei set.

a
a.pietroluongo (11250 points)
15 38 131
commented Nov 17, 2019 by a.pietroluongo (11,250 points)
Per trovare la parola segreta non penso che sia corretto usare i set perché andresti ad eliminare i caratteri uguali..
Christian (15220 points)
2 4 77
commented Nov 17, 2019 by Christian (15,220 points)
Dipende da come li usi.. io ho usato solo insiemi e funziona tutto perfettamente.
s
scutigliani.luca (860 points)
6 10 15
commented Nov 17, 2019 by scutigliani.luca (860 points)
Beh, se ogni elemento del set è una sottostringa che si ripete una volta sola non perdi nulla
Tommaso Sgroi (12990 points)
6 11 91
commented Nov 17, 2019 by Tommaso Sgroi (12,990 points)
E' giusto ma ci mette tanto...
s
scutigliani.luca (860 points)
6 10 15
commented Nov 17, 2019 by scutigliani.luca (860 points)
Per niente, non devi mica iterare su tutte le parole :P
a
alessiodales (1400 points)
0 0 2
answered Nov 17, 2019 by alessiodales (1,400 points)

Sebbene ci siano soluzioni più efficienti, puoi provare ad implementare il metodo count e da lì ricavarti la sottostringa.

a
a.pietroluongo (11250 points)
15 38 131
answered Nov 17, 2019 by a.pietroluongo (11,250 points)
Usando i dizionari
plm (18850 points)
7 15 118
answered Nov 17, 2019 by plm (18,850 points)
Io ti consiglio vivamente di utilizzare i set, ma non di usare l'intersezione. Ovvero i set ti permettono di poter lavorare sulle parole e non ti ritornare sui duplicati. Per esempio ci sono test come il 5 che presentano solo 2 stringhe diverse ed una delle due è ripetuta per tante volte. L'intersezione è un'operazione che è 5 volte più lenta di un confronto diretto tra stringhe. Il count è molto utile,ma se mai dovessi fare un count su una parola singola, questo non peserebbe sull'algoritmo, mentre se facessi count sulla lista di parole (ovvero tutte le parole che ricavi dal file, quindi anche 10 mila ripetizioni di una stessa parola), il programma andrebbe sicuramente in timeout
a
a.pietroluongo (11250 points)
15 38 131
answered Nov 17, 2019 by a.pietroluongo (11,250 points)
Intendevo il metodo intersection.
Tommaso Sgroi (12990 points)
6 11 91
answered Nov 17, 2019 by Tommaso Sgroi (12,990 points)

Come avevo detto in un altro post:


La parola nascosta sarà all'interno di ogni stringa, separata da spazio, UNA SOLA VOLTA PER STRINGA.

Nell'esempio del professore infatti, per le 6 stringhe con parola nascosta di lunghezza 3:
    
    moneta
    maratoneta
    pitone
    onesto
    storione
    sonetto
    
    la parola nascosta è 'one' e le posizioni sono nell'ordine: 1, 5, 3, 0, 5, 1

Questo vuol dire che cercando in ogni stringa tutte le sottostringhe di lunghezza 3, 'one' apparirà SOLO 1 volta in ogni stringa. Dopodiché dovrai ritornale la lista delle posizioni di 'one' all'interno delle tue stringhe.

Sapendo questo, se ti generassi tutte le possibili sottostringhe nella prima parola e le andassi a confrontare con le altre, noterai come solo 'one' venga ripetuta nella prima e nelle altre sottostringhe. Questo vuol dire che è inutile andare a cercare tutte le possibili sottostringhe in tutte le stringhe, bensì dovrai andare a cercare, confrontando, le possibili sottostringhe nelle altre parole tramite le sottostringhe della prima parola!

Per fare un esempio la stringa 'onesto' : one, nes, est, sto     

Se guardi la stringa successiva 'storione' sarà composta da: sto, tor, ori, rio, ion, one                                                                                                                                                                             

Quindi andando a guardare nella seconda parola vedrai che alcune sottostringhe si ripetono  così saprai quali sono le possibili sottostringhe da cercare.  Ora allora dovrai andare a vedere nelle altre parole quali sono ripetute tra quelle.

Se andassimo ora a prendere moneta: mon, one, net, eta.

Vedremo che confrontando con le POSSIBILI SOTTOSTRINGHE delle parole precedenti one e sto solo one è ripetuta una volta in moneta. Quindi possiamo già iniziare a supporre che one è la nostra parola segreta.

Per ottenerla ci sono vari metodi, ad esempio usare dei dizionari che tengono con le sottostringhe in una parola, oppure l'intersezione degli insiemi delle sottostringhe delle varie parole.



Spero di averti dato qualche spunto o qualcosa su cui pensare.

s
simone.lioy (1420 points)
23 30 39
answered Nov 17, 2019 by simone.lioy (1,420 points)
Anche io sto un incasinato, utilizzando il programma fatto da me sono riuscito a trovare la parola nascosta però il problema rimane nella posizione della parola perchè ci sono \n e mi sballano tutto. chiedo come eliminare \n e formare cosi le sei parole messe bene non come il file. spero di essere stato chiaro.
a
a.pietroluongo (11250 points)
15 38 131
commented Nov 17, 2019 by a.pietroluongo (11,250 points)
Puoi usare le slice per prendere la stringa tranne l'ultimo carattere o il metodo replace
s
simone.lioy (1420 points)
23 30 39
commented Nov 17, 2019 by simone.lioy (1,420 points)
mi rimango gli spazi vuoti, che mi scollegano le parole in due
a
a.pietroluongo (11250 points)
15 38 131
commented Nov 17, 2019 by a.pietroluongo (11,250 points)
Puoi usare la stringa vuota e non lo spazio..
s
simone.lioy (1420 points)
23 30 39
commented Nov 17, 2019 by simone.lioy (1,420 points)
gia fatto ma nulla
L
Lolloxox31 (1610 points)
11 16 26
commented Nov 17, 2019 by Lolloxox31 (1,610 points)
prova con le slice e due cicli while identici annidati
L
Lolloxox31 (1610 points)
11 16 26
answered Nov 17, 2019 by Lolloxox31 (1,610 points)
Prova ad usare i set per le stringhe del file e le possibili sottostringhe candidate ad essere la word nascosta, poi fai un ciclo dove escludi ogni volta le word non candidate mano a mano che scorri le stringhe del file, con me ha funzionato :)
s
simone.lioy (1420 points)
23 30 39
commented Nov 17, 2019 by simone.lioy (1,420 points)
messe in un insieme ma comunque rimangono spezzate le parole, il mio problema è unirle