Match di array

di
jackbalck
il
4 risposte
J
jackbalck
Pochi posts
Iscritto da
feb, 2014
Messaggi:
5

Match di array

Non riesco a capire come dovrei fare un programma del genere:


Ci sono array char T[100] e char P[20], un match di P in T è una porzione di T di
lunghezza 20 .
Assumeremo che T e P possano non essere completamente definiti e che
lo siano solo per la parte T[0..dimT-1] e P[0..dimP-1], dove dimT e dimP sono opportuni
valori letti da "input".
Si chiede di scrivere un programma che legga da "input" due interi dimT e dimP (tali
che 0<dimT<=100 e 0<dimP<=20) e poi legga dimT valori da "input" in T e dimP
valori ancora da "input" in P. Dopo queste letture, il programma deve individuare il più
piccolo indice i in [0..dimT-1] a partire dal quale T contiene un match di P[0..dimP-1].

In pratica p essendo più piccolo è contenuto in t e devo individuare a da che locazione in t mi parte la sfilza di 20 numeri di p?
Comunque non mi vengono in mente istruzioni per eseguire il tutto avendo appena cominciato con il c++ asd

4 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Match di array

    E' lo stesso problema di cercare una sottostringa all'interno di una stringa:

    data una stringa: "ciao pistolone, ma che fai cazzeggi?"

    devi cercare la posizione della sotto stringa "che".

    Se pensi alla stringa come ad un vettore, ed ai caratteri come dei numeri (la loro conversione in codice ASCII), questo di dovrebbe dare l'idea di come creare un algoritmo che risolve il tuo problema.

    E l'algoritmo (almeno questo tipo di algoritmo) non dipende dal fatto di scriverlo in C/C++/Java/Python/PHP/Ruby/Perl/Pascal/VisualBasic/... e qualunque altro linguaggio procedura/ead oggetti ti venga in mente

    Ti bastano i concetti di vettore, indice, ciclo, uguaglianza, condizione
  • J
    jackbalck
    Pochi posts
    Iscritto da
    feb, 2014
    Messaggi:
    5

    Re: Match di array

    Alla tua stringa sono morto haha
    In effetti ora mi è più chiaro grazie; per controllare che il mio P sia contenuto in T come potrei fare?
  • J
    jackbalck
    Pochi posts
    Iscritto da
    feb, 2014
    Messaggi:
    5

    Re: Match di array

    {
    INP>>dimT;
    INP>>dimP;
    for(int l=0; l<dimT; l++)
    {
    INP>>T[l];
    }
    for (int m=0; m<dimP; m++)
    {
    INP>>P[m];
    }
    for(int i=0; i<dimT; i++)
    {
    for(int k=0; k<dimP; k++)
    {
    if(conta!=dimP)
    {
    if (T[i+k]==P[k])
    {
    conta++;

    }
    else if(T[i+k]!=P[k])
    {
    conta=0;
    }
    }
    if(conta==dimP)
    {cout<<i;}
    }
    }
    }


    Non funziona
  • L
    Light
    Utente Attivo
    Iscritto da
    mag, 2013
    Messaggi:
    147

    Re: Match di array

    Anche se esistono già algoritmi di pattern matching estremamente efficienti come l'Algoritmo di Knuth-Morris-Pratt, penso che per esigenze didattiche una funzione di questo genere possa funzionare...
    
int match_string(char string[], char pattern[])
{
int i, j, k;
i=0;
while(string[i]!='\0')
	{
	j=i; k=0;
	while( pattern[k]!='\0' && string[j]==pattern[k])
		{
		j++; k++;
		}
	if (k > 0 && pattern[k] == '\0')
		return i;
	i++;
	}
return -1;	
}
Devi accedere o registrarti per scrivere nel forum
4 risposte