Newsgroup: it.comp.lang.c++
Titolo: Algoritmo di confronto... AIUTO

Salve,
ho un questito riguardante un le materie di Logica ed Informatica.
Devo inplementare un algoritmo (pseudocodifica o codifica in C++) che faccia
il confonto tra due stringhe di caratteri. Qusta funzione mi deve dire solo
se la seconda è contenuta nella prima.
ES:
stringa 1     ABABAABBAAB
stringa 2     ABBA
la stringa 2 c'è nella 1!
La difficoltà è la seguente: non bisogna utilizzare un semplice algoritmo di
confronto (se c'è la prima lettera leggi la seconda se c'è la seconda leggi
la terza ecc...) ma bisogna utilizzare un qualche teorema di "Algebra e
Logica" come ad esempio utilizzo delle matrici , grafi, o via di lì.
Qualcuno può darmi una mano???  Qualunque consiglio è ben accettato!!
valer...@libero.it

 Qualcuno può darmi una mano???  Qualunque consiglio è ben accettato!!
Il problema che poni è un caso particolare di pattern-matching, cioè la
ricerca di pattern all'interno di una sequenza (una sottostringa in una
stringa, una catena di geni nel DNA, etc.). Esistono algoritmi banali, che
al passo k confrontano il pattern di lunghezza m con la sottosequenza di
indici [k,k+m] (lentissimo, complessità quadratica), oppure ti puoi affidare
all'algoritmo di Knut-Morris-Pratt (complessità O(n+m) dove n è la lunghezza
della sequenza e m del pattern da ricercare).
Spero di esserti stato utile.
Ciao,
--
----------------------------
Fulvio Esposito
"La differenza tra teoria e pratica e', in pratica, un po' piu' che in
teoria"
----------------------------

 ha scritto nel messaggio
news:uvEo9.5046$RO.1...@twister1.libero.it...


 interessato a questo!!!
La grafia esatta e' Knuth-Morris-Pratt, e non e' un taorema - ma un
algoritmo per la ricerca di sequenze all'interno di stringhe di
caratteri.  Un altro algoritmo importante e' quello di Boyer-Moore,
sia nella versione originale che in quella variata da Horspool.  Si
usa l'uno o l'altro di questi algoritmi a seconda delle condizioni al
contorno (come ad esempio la dimensione del vocabolario, quella delle
stringhe e quella delle sequenze; oppure se bisogna cercare poche
volte tante sequenze differenti oppure tante volte la stessa
sequenza).
Parti da un buon testo universitario di algoritmi (ad esempio il
Cormen et al.) o da una ricerca sul web.
Nella nostra pagina locale di documentazione (sotto la URL
http://wwwcdf.pd.infn.it/localdoc.html
) c'e' una copia di un papero
classico sull'argomento, ormai un po' datato (e' vecchio di 10 anni)
ma che a suo tempo e' stato considerato fondamentale e per di piu' e'
molto chiaro: cerca nella URL il riferimento a "Graham A. Stephens'
1992 paper on string searching".
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Dept. of Physics, Univ. of Padova, Italy          loreti at pd dot infn dot it

 Logica" come ad esempio utilizzo delle matrici , grafi, o via di lì.
sento puzza di Pettorossi!


Infatti č paro paro il compito che ha dato Pettorossi come
primo esonero
Perň quello che l'OP non ha ben capito ( e cosa che io ho capito
solo oggi) č che il PettoReds ha chiesto TUTT'ALTRA cosa
che trovare un algoritmo veloce, una cosa che rasenta CONCETTUALMENTE
l'impossibile per me!
P.S. ma č cosě famoso come professore? finora tutto al mio corso
tutto ha fatto tranne la sua materia!

 tutto ha fatto tranne la sua materia!
forse xkč tale corso vanta 600 persone
e ogni anno ne passano 20 e ne arrivano altre 600!
W  ITALIANO