[c] Ricerca di una sottostringa

[Ed_Bunker]

Ciao, dovrei implementare una funzione che ricerchi (data una sottostringa ed il nome di un file .txt ) la sottostringa all'interno di tale file restituendo la posizione in cui si trova (La prima occorrenza) o -1 se la sottostringa non e' stata trovata. Avete suggerimenti, link o qualche algoritmo che renda abbastanza efficiente tale operazione ?!?

thks :)

[maxithron]

Se non ho capito male (probabilmente si, data l'ora e il mio rincogl...ento) ti serve la funzione strcspn che ha come prototipo:


size_t strcspn(char *str1, char *str2)


Questa funzione cerca appunto la prima occorrenza di una stringa con qualsiasi carattere di una seconda stringa.

[Ed_Bunker]

Originariamente inviato da maxithron
Se non ho capito male (probabilmente si, data l'ora e il mio rincogl...ento) ti serve la funzione strcspn che ha come prototipo:

size_t strcspn(char *str1, char *str2)

Questa funzione cerca appunto la prima occorrenza di una stringa con qualsiasi carattere di una seconda stringa.

Probabilmente intendevi dire la strspn(...) ....

Dal man:
strcspn(char * p, char * q) restituisce il numero di caratteri di p (Partendo dall'inizio) che corrispondono esattamente ai caratteri di q.
Esempio:


int main()
{
char * s1 = "cavolfiore";
char * s2 = "fiore";
int pos = strspn(s1, s2);
printf("%d\n", pos); /*STAMPA 0*/

char * s3 = "jonny";
char * s4 = "jo";
pos = strspn(s3, s4);
printf("%d\n",pos); /*STAMPA 2*/

return(0);
}



Io invece voglio trovare una certa sottostringa all'interno di un testo a prescindere della posizione in cui essa si possa trovare.
Devo trovare qualcosa perche' come lo sto facendo credo che l'efficienza sie pressoche' ridotta ai minimi termini...

[maxithron]

strspn è simile a quella che ti avevo postato ma restituisce la posizione del primo carattere di stringa1 che non è presente in stringa2.

forse ora però mi è più chiara la tua domanda(sottolineo il forse :) )

in questo caso potresti utilizzare strstr() che ricerca la prima occorrenza all'interno di un'altra stringa. Se per esempio la tua stringa2 non c'è in stringa1 ovviamente ti restituisce NULL.

per il prototipo basta il man, cmq :

char *strstr(char *p, char *q);



Dimenticavo... questa ti ricerca proprio una stringa all'interno di un'altra.

Sennò, mi rileggo il post domattina :D

[Ed_Bunker]

Originariamente inviato da maxithron
strspn è simile a quella che ti avevo postato ma restituisce la posizione del primo carattere di stringa1 che non è presente in stringa2.

forse ora però mi è più chiara la tua domanda(sottolineo il forse :) )

in questo caso potresti utilizzare strstr() che ricerca la prima occorrenza all'interno di un'altra stringa. Se per esempio la tua stringa2 non c'è in stringa1 ovviamente ti restituisce NULL.

per il prototipo basta il man, cmq :

char *strstr(char *p, char *q);



Dimenticavo... questa ti ricerca proprio una stringa all'interno di un'altra.

Sennò, mi rileggo il post domattina :D

Ecco... Questa dovrebbe fare al mio caso. Dopo do' un'occhiata al man. Grazie.
;)

[mmx[ngg]]

X cosa ti serve ?

Xke se ti devi semplicemente limitare a ricercare una stringa una sola volta all'interno di un buffer non hai molta scelta x renderlo particolarmente efficente....asm ?.

Se invece le ricerche sono multiple / massicce e di stringhe differenti sullo stesso buffer (mi suona familiare all'LZW) allora devi usare delle funzioni di hashing.

[Ed_Bunker]

Originariamente inviato da mmx[ngg]
X cosa ti serve ?

Xke se ti devi semplicemente limitare a ricercare una stringa una sola volta all'interno di un buffer non hai molta scelta x renderlo particolarmente efficente....asm ?.

Se invece le ricerche sono multiple / massicce e di stringhe differenti sullo stesso buffer (mi suona familiare all'LZW) allora devi usare delle funzioni di hashing.

Si e' solo la ricerca di una sottostringa all'interno di un file .txt .
Io credevo ci fosse cmq. una ricerca un po' piu' "astuta" della 'normale' ricerca lineare carattere per carattere.
Ieri ho terminato di fare una 'versione' dela funzione la quale consiste nel mappare il memoria in file per accedervi piu' velocemente (con mmap()) e poi, data una sottostringa(sstring), scorre carattere per carattere il testo(text):

se il primo carattere di "text" coincide con il primo carattere di "sstring" allora viene richiamata la funzione di libreria strncmp()

con questi parametri: 1: puntatore al testo, 2: puntatore alla sottostringa, 2: lunghezza della sottostringa.

Se questa funzione mi restituisce 0 allora esco dal ciclo e restituisco la pos. (Individuata utilizzando un contatore).
Altrimenti incremento il puntatore al testo (Andando sul carattere successivo) ed aumento il contatore.

Se arrivo alla fine del ciclo senza aver restituito nulla allora restituisco -1.

All'atto pratico la funz. sembrerebbe piuttosto veloce anche con file di testo piuttosto lunghi (Anche se non ho ancora provato a testare il tempo di exec con la time()... :rolleyes: ). Quello che mi preoccupa e' il "calcolo" della posizione che penso non sia attendibile visto che non considera tutte le linee ma solo quelle in cui ci sono caratteri o spazi e non quelle "vuote". :(
Ad esempio suppondendo righe lunghe 13:
Testo:

1111111111111
2222222222
333

Volendo cercare 3 la funzione mi restituirebbe la pos. 24 mentre io "preferirei" mi restituisse la pos. (13*2) + 1 = 27

Cosa ne dici ??

Grazie.
4

[cionci]

Usa la strstr che fa la stessa funzione...inoltre ti ritorna il puntatore alla stringa... A quel punto fai la differenza fra il puntatore ritornato e l'inzio del buffer ed hai la posizione esatta ;)

[Ed_Bunker]

Originariamente inviato da cionci
Usa la strstr che fa la stessa funzione...inoltre ti ritorna il puntatore alla stringa... A quel punto fai la differenza fra il puntatore ritornato e l'inzio del buffer ed hai la posizione esatta ;)

thks
:ave: :D ;)

[maxithron]

beh.... che avevo risposto di male allora stanotte alle 3.00 ? :mbe:



Originariamente inviato da maxithron


forse ora però mi è più chiara la tua domanda(sottolineo il forse :) )

in questo caso potresti utilizzare strstr() che ricerca la prima occorrenza all'interno di un'altra stringa. Se per esempio la tua stringa2 non c'è in stringa1 ovviamente ti restituisce NULL.

per il prototipo basta il man, cmq :

char *strstr(char *p, char *q);



Dimenticavo... questa ti ricerca proprio una stringa all'interno di un'altra.

Sennò, mi rileggo il post domattina :D


:D

[Ed_Bunker]

Originariamente inviato da maxithron
beh.... che avevo risposto di male allora stanotte alle 3.00 ? :mbe:
:D

Infatti ti avevo risposto:
"Ecco... Questa dovrebbe fare al mio caso. Dopo do' un'occhiata al man. Grazie."

Il fatto e' che non avevo ancora guardato il MAN.

Vabbe' gelosone anche tu ti meriti un...
http://forum.hwupgrade.it/faccine/23.gif :D :D