[Risolto][C++]Una ricerca particolare in un array

[Krdan]

Sto cercando la soluzione da un po' ma non ho trovato ancora una risposta ai miei problemi:
Ho un'array di stringhe di circa 280.000 elementi, io devo cercare in questo array se esiste una parola con un determinato prefisso dato.
Un'esempio pratico
Facciamo caso che nell'array ci sia:
-Arancia
-Banana
-Mela

io devo cercare se il prefisso "Ban" esiste nell'array e in questo caso dovrebbe dire di si visto che c'è Banana, come posso fare?
Mi basta un'idea per partire, il codice poi vedrò di scriverlo da me.
Grazie  (b2b)

[Picciolz]

non ho capito bene nel esempio..
è un arrey? o un arrey di arrey? mi spiego.

arrey: char lettere[10000];
arrey di arrey: char *parola[10000];

il primo è simile a un elenco di lettere il secondo a un elenco di parole.
mi sono chiarito?? ???

[sospiro]

ma non si diceva array???
comunque il tuo array si presenta ordinato o meno?

[Krdan]

E' un dizionario, un array di array (del tipo char *parola[NUM]) ed è ordinato in ordine alfabetico crescente (A-Z).
Il prefisso è inserito dall'utente quindi non ha un numero specificato di lettere

[simo_magic]

allora possiamo sfoltire la ricerca un casino...
ricerca dicotomica e hai al massimo log2N confronti dove N è la lunghezza del vettore

quando fai il confronto vedi se la parola da esaminare inizia con i caratteri inseriti...
ps si dice "a-r-r-e-y" ma si scrive array 

[Uno]

Codice: Seleziona tutto

int main (int argc, char *argv[])
{
	char pre[]="prova";
	int len=strlen (pre);

	//trova tutte le parole tra gli argomenti con prefisso pre
	//non l'ho provato bisognerà sicuramente sistemare qualcosa
	for (j=0;j<argc;j++)
	{
		int i=0,j=0;
		char *p=argv[j];
		char *q=pre;
		while ( i<len && *p==*q )
		{
			p++;
			q++;
			i++;
		}

		if (i==len)
		{
			printf ("trovato: %s",argv[j])
		}
	}
}

[Picciolz]

Ciao UNO, mi sono permesso di correggere quei 2 errori di compilazione giusto x essere precisi!

//programma di --> UNO <---

int main (int argc, char *argv[])
{
char pre[]="prova";
int len=strlen (pre);
        int i=0;
//controllato e mi sembra funzionante
//corretto quasi nulla
for (int j=0 ; j<argc ;  j++)
{
i=0;
char *p=argv[j];
char *q=pre;
while ( i < len && *p==*q )
{
p++;
q++;
i++;
}

if (i==len)
{
printf ("trovato: %s",argv[j]);
}
}
}

[Krdan]

Grazie infinite, ho inteso il metodo, ora vedo di applicarlo alla mia situazione 

[Uno]

Ciao UNO, mi sono permesso di correggere quei 2 errori di compilazione giusto x essere precisi!

Bene, comunque si può ancora migliorare non accedendo agli argomenti da array, argv[j], ma con un puntatore.
Comunque lasciamo a Krdan la soddisfazione di farlo.

[jack84]

Se vuoi una soluzione molto veloce considerando che hai un'array ordinato puoi usare la ricerca binaria che opera in questo modo:confronta la tua parola con la parola che occupa la posizione N/2 (dove N è la dimensione dell'intero vettore, in pratica N/2 è la parola centrale)se la parola che cerchi è uguale a quella che è contenuta nell'array ti fermi, altrimenti se in ordine alfabetico la tua parola viene prima di quella contenuta nell'array prosegui sulla prima metà del vettore altrimenti sulla seconda metà.
A questo punto puoi suddividere ancora a metà la porzione di vettore in esame prendendo in considerazione l'elemento centrale della metà considerata ripetendo il procedimento finchè non trovi l'elemento. In pratica ogni volta vengono scartati metà degli elementi tra quelli presi in esame.

Qui c'e' un link per darti un'idea con degli esempi di implementazione
http://it.wikipedia.org/wiki/Ricerca_dicotomica


Copiato e incollato il codice da wikipedia in particolare questa è una soluzione ricorsiva per questo problema che richiama se stesso su un insieme via via più piccolo di elementi, notare l'eleganza

Codice: Seleziona tutto

int ricercaBinaria(int lista[], int x, int a, int z ) {

   int m;

   // Determina l'elemento centrale
   m = ( a + z ) / 2;

   if ( m < a ) {
       // l'elemento cercato non c'è
       return -1;
   } else if ( x < lista[m] ) {
       // Si ripete la ricerca nella parte inferiore
       return ricercaBinaria( lista, x, a, m-1 );
   } else if ( x > lista[m] ) {
       // Si ripete la ricerca nella parte superiore
       return ricercaBinaria( lista, x, m+1, z );
   } else {
       // m rappresenta l'indice dell'elemento cercato
       return m;
   }

}

[simo_magic]

elegante ma più lento della stessa funzione scritta in modo iterativo...
la funzione iterativa è sempre più veloce della rispettiva ricorsiva

[jack84]

Già inoltre il grave difetto della ricorsione è anche l'elevato dispendio di ulteriore memoria, lo stack cresce in fretta se non si stà attenti alla proliferazione delle chiamate. Però spesso una funzione ricorsiva è la soluzione davvero più comoda.