Newsgroup: it.comp.lang.c
Titolo: string matching aiuto!!!

salve a tutti..ho il seguente problema devo calcolare il numero di
occorrenze della array a(un array di char) all'interno dell'array b (un
array di char che utilizzo come testo)
#include <stdio.h>
int array_uguali(char *a,char *b,int y);
char a[]={'i','n','f','o','r','m','a','t','i','c','a'};
char
b[]={'i','i','n','f','o','r','m','a','t','i','c','a','d','o','i','n','g','o','f','o','i','n','f','o','r','m','a','t','i','c','a'};
void main()
{
	int i,conta=0;
	for (i=0;i<=31;i++)
 if (array_uguali(a,&b[i],11)==0);
 conta++;
 printf("%d\n\n\n",conta);
}
int array_uguali(char *a,char *b,int y)
{
int n=0,flag;
do{
if (a[n]==b[n])
flag=1;
else
return flag=0;
n=n+1;
}
while (a[n]!=b[n]|| n<=(y-1));
return flag;
}
questo è quello che sono riuscito a far venire fuori..ma il contatore
è sempre fermo a 1..so che la function array_uguali poteva essere
modificata con un doppio ciclo..ma sinceramente funziona cosi..e per
questo ho deciso di non toccarla almeno che non sia proprio la function
a determinare l'errore..grazie per l'aiuto!!!

 void main()
int main()
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 }
Mamma mia Andrea !
void find_s(char *s, char *t, int *n)
{
	int len = strlen(s);
	for(*n=0 ; (t=strstr(t, s))!=NULL ; t+=len,(*n)++);
}
--
Gianluca Puggelli
skype:pugg1138

gianluca...@gmail.com
 ha scritto:

senza libreria string.h..se no lo so fare :P

 Mamma mia Andrea !
Gianluca, lo so benissimo anch'io che usando una funzione dello standard
si risolve il problema, ma non credo che sia questo il punto.  Credo che
il nostro amico volesse concentrarsi sull'algoritmo di ricerca alla base.


 senza libreria string.h..se no lo so fare :P
Bigros,
questo requisito mi deve essere sfuggito...
Sul web ho trovato questa implementazione di strstr. Usare comunque
strstr mi sembra piu' semplice della soluzione proposta da Andrea.
char *strstr(const char * str1, const char * str2)
{
        char *cp = (char *) str1;
        char *s1, *s2;
        if ( !*str2 )
            return((char *)str1);
        while (*cp)
        {
                s1 = cp;
                s2 = (char *) str2;
                while ( *s1 && *s2 && !(*s1-*s2) )
                        s1++, s2++;
                if (!*s2)
                        return(cp);
                cp++;
        }
        return(NULL);
}
ciao
   g


         return(NULL);
Colgo l'occasione per dire che le funzioni dovrebbero avere un unico punto
d'uscita.  Progettare una funzione a questo modo significa progettarla
male.


 male.
Andrea, concordo al 100%  con quanto dici.
Questo codice non avrebbe passato la code inspection dell'azienda per
la quale lavoro.
FYI: Il codice e' un cut&paste delle librerie VC6 che ho trovato sul
web.


Andrea Laforgia ha scritto:

e tu che mi consigli è tutto il pomeriggio che provo ad inserire
varianti..ma nn riesco ad arrivare al nocciolo!!!..so che nel mio
programma c saranno 1 milione e mezzo di errori..ma c devo riuscire sob
sob

 programma c saranno 1 milione e mezzo di errori..
Io ti consiglio di prendere spunto dal codice che ti ho scritto in questo
thread e andare di passo passo con il tuo per verificare gli errori.



Comunque l'algoritmo è sbagliato.
Infatti il programma non funziona per
input come:
"AAABB" e "AABB"
Quando si trova l'errore
bisogna tornare al punto iniziale, cioè il valore di t_idx
dell'inizio del tentativo (+1 naturalmente).
Quello che fà strstr fondamentalmente.
Infatti la versione con strstr è corretta da questo punto
di vista.
OT {
    Il problema dello string matching è di rilevante interesse  teorico.
    Gli algoritmi presentati sono di complessita O(m*n)
    Dove con m e n indico la lunghezza delle stringhe di
    input.
    Esistono algoritmi anche piuttosto "contorti" e di non
    banale comprensione per risolvere il problema con complessità O(m+n).
    Si può fare riferimento al solito Donald E. Knuth
    per dare un'occhiata.
}
--
Giorgio Silvestri
DSP/Embedded/Real Time OS   Software Engineer

"AAABB" e "AABB"
Su questo hai perfettamente ragione.  E' stata la fretta di fornire
qualcosa di utilizzabile subito ;-)
Dal mio punto di vista, per implementare professionalmente un
algoritmo del genere, sarebbe il caso di ricorrere a tecniche già
conosciute come quella di Boyer-Moore-Horspool o Knuth-Morris-Pratt.

 Il subject del thread è "string matching", quindi si parla di stringhe
Non proprio.
"String matching" è un termine noto e ben definito in
informatica che non ha che fare con il C.
Quindi l'OP l'ho ha usato in questo contesto.
O almeno avrebbe dovuto.
A suffragare questa ipotesi c'è il fatto
che l'OP stesso usa array di char e non stringhe.
In ogni caso conviene fare un algoritmo più generale.
Tanto il costo aggiuntivo non è molto più alto.


Tanto il costo aggiuntivo non è molto più alto.
Ho già detto di condividere questo punto.

 inizializzare una stringa in C.
Poteva anche saperlo :-)


Poteva anche saperlo :-)
Sei disposto a scommettere ? Mi gioco una pizza e una birra.

"Andrea Laforgia" <a.laf...@andrealaforgia.it.invalid> ha scritto nel
messaggio news:43lef2hsp7fl7kivb...@4ax.com...


In termini probabilistici anche io penso che non lo sapeva ...:-)
e poi normalmente non scommetto!


Giorgio Silvestri ha scritto:

Alla fine non so se avete scommesso cmq string matching non è inteso
solo per stringhe ma anche per array di char..per quanto riguarda
l'inizializzazione di una stringa..bhe nn ci vuole una laurea in
ingegneria informatica per utilizzarle..a[]={"ecco qua"}

 ingegneria informatica per utilizzarle..a[]= "ecco qua" ;..ora si

big...@libero.it
 ha scritto:

a[]="ecco qua";..mo si!!

 ingegneria informatica per utilizzarle..a[]={"ecco qua"}
Già.


a[]="ecco qua";..mo si!!
mo no!!
char a[]="ecco qua"; /*  mo si!!   :-)   */
