[C-PHP] Algoritmo di ricerca sottostringhe matchanti

[mfonz85]

Ciao a tutti,
ho un problema: ho 2 stringhe (che altro non sono che caratteri rappresentati come esadecimali) molto lunghe, di circa 10kb l'una.
Vorrei trovare le sottostringhe più lunghe uguali all'interno di queste 2 stringhe...

Esempio

dvksjvsvdvvbvbssbkueewOUIBVAdalwiiilaclca
cscasqoklsmccOUIBVAspjpsglmsbmsb

in questo caso l'algoritmo dovrebbe ritornarmi la sottostringa OUIBVA.

C'è un modo veloce per scrivere sto algoritmo in C o PHP? Va bene anche pseudocodice, perchè io non ho idee :(

[gugoXX]

L'ho fatto al lavoro in C# poco piu' di un mese fa, se ti serve domani lo posto.
Mi sembra di essere arrivato a complessita' n^2 Ln(n), quindi nel tuo caso estremamente lento.

[^TiGeRShArK^]

una possibile implementazione che pensandoci un attimo mi è venuta in mente è effettuare un XOR della prima stringa con la traslazione di un byte alla volta della seconda.
A quel punto devi memorizzarti il numero massimo di zeri consecutivi nelle varie esecuzioni dell'XOR ed effettuare la ricerca dell'esecuzione con il max numero di zeri.
Quindi, ricapitolando, se non mi sono dimenticato niente e se funziona (ad occhio mi sembrerebbe di si.. ma tra la teoria e la pratica di solito ce ne passa :D) avresti n^2 per la prima fase e log N per la seconda..
quindi mi sa che è equivalente alla soluzione di gugoxx :D
cmq sui processori moderni per stringhe di 10000 caratteri dovrebbe essere *sufficientemente* veloce :p

[mfonz85]

ma si ragazzi n^2 Ln(n) è perfetto, tanto serve solo a me questo algoritmo...
@ ^TiGeRShArK^: oddio, non ho capito come funziona...aspè fammi un esempio veloce, ti do le stringhe:

abbazalla
ciccalibba

In pratica come funziona?? :confused:

abbazzalla - ciccalibba
abbazzalla - iccalibba
abbazzalla - ccalibba
abbazzalla - calibba

intendi questo?

[gugoXX]

Avevo perso la prosceuzione.
Si', funziona come ha detto TigerShark, ed e' anche molto elegante.

Anche questo e' n^2 ln(n), ed e' piu' bello del mio.
Ma forse prendendo spunto da questo si puo' ridurre a n*Log(n).

anche a me serviva per qualche decina di Kappa, quindi non sono stato a cercare la soluzione ottima, ma direi che ci si puo' lavorare.

[^TiGeRShArK^]

ma si ragazzi n^2 Ln(n) è perfetto, tanto serve solo a me questo algoritmo...
@ ^TiGeRShArK^: oddio, non ho capito come funziona...aspè fammi un esempio veloce, ti do le stringhe:

abbazalla
ciccalibba

In pratica come funziona?? :confused:

abbazzalla - ciccalibba
abbazzalla - iccalibba
abbazzalla - ccalibba
abbazzalla - calibba

intendi questo?
no.. non ti devi perdere pezzi quanto trasli la stringa :D
dovrebbe essere così:

sacca ^ pacca = 10000
sacca ^ accap = 11011
sacca ^ ccapa = 11110
sacca ^ capac = 10111
sacca ^ apacc = 11101

ovviamente per brevità ho scritto '1' e '0' al posto di 11111111 e 00000000 come sarebbe nella realtà effettuando un XOR tra byte :p
ah..
dimenticavo..
Se non erro dovrebbe funzionare solo con stringhe di dimensione uguale :p

[k0nt3]

che culo! casualmente mi è capitato di implementare un algoritmo simile in C
te lo allego perchè non ho nemmeno voglia di ricordarmelo :asd:

[mfonz85]

no.. non ti devi perdere pezzi quanto trasli la stringa :D
dovrebbe essere così:

sacca ^ pacca = 10000
sacca ^ accap = 11011
sacca ^ ccapa = 11110
sacca ^ capac = 10111
sacca ^ apacc = 11101

ovviamente per brevità ho scritto '1' e '0' al posto di 11111111 e 00000000 come sarebbe nella realtà effettuando un XOR tra byte :p
ah..
dimenticavo..
Se non erro dovrebbe funzionare solo con stringhe di dimensione uguale :p

Ok, nel mio caso non ho stringhe di dimensione uguale ma poco male, spezzo la più lunga in tronconi e alla fine quello che rimane lo controllo pezzetto per pezzetto...
Ma dici che con PHP si può fare?? Mi metto a spulciare il manuale, vedo se lavorare con i byte funziona come nel C...

Quindi se non ho capito male... la migliore corrispondenza nel tuo caso è la prima, 10000 giusto?
Perfetto, è una genialata questo algoritmo :eek:

[mfonz85]

che culo! casualmente mi è capitato di implementare un algoritmo simile in C
te lo allego perchè non ho nemmeno voglia di ricordarmelo :asd:

Ti ringrazio :D
Per sfida personale prima di leggerlo provo ad implementarlo in PHP e vedo cosa ne cavo fuori, altrimenti ripiego sul tuo listato :D

[k0nt3]

tranquillo poi se avrai bisogno cercherò anche di spiegarlo (forse) :stordita:

[^TiGeRShArK^]

Ok, nel mio caso non ho stringhe di dimensione uguale ma poco male, spezzo la più lunga in tronconi e alla fine quello che rimane lo controllo pezzetto per pezzetto...
Ma dici che con PHP si può fare?? Mi metto a spulciare il manuale, vedo se lavorare con i byte funziona come nel C...

Quindi se non ho capito male... la migliore corrispondenza nel tuo caso è la prima, 10000 giusto?
Perfetto, è una genialata questo algoritmo :eek:
si la migliore corrispondenza è quella con il massimo numero di zeri.
cmq non so quanto può essere una genialata dato che è il primo che mi è venuto in mente... e quindi potrebbe anche presentare qualche problemino che ora mi sfugge :D
Cmq se provi ad implementarlo vedrai subito se funziona correttamente :p