[C] Controllo ordine lettere fra due stringhe differenti

[IlPrescelto]

Salve a tutti Volevo chiedere il vostro parare riguardo a questa problematica. Come faccio a controllare che fra due stringhe differenti, una più lunga e una più corta, le parole della stringa più corta siano ripetute nello stesso ordine che hanno nella parola più lunga?
ES:
Cavallo-vallo----- giusto!
Cavallo-llova----- sbagliato!
Cavallo-callo-----giusto! (le lettere devono essere in ordine ma possono esserci anche dei "buchi" rispetto alla parola più grande, come in questo caso che "va" non è presente).

Purtroppo non ho un codice da incollare in quanto non capisco con che metodologia utilizzare. Se mi saprete dare dei consigli su come procedere, poi posterò il codice. Ovviamente non vi sto chiedendo di fare l'es per me ma solo "indirizzarmi" su come fare. Grazie mille


ps: ho cercato di utilizzare un titolo decente e spero che non dia problemi xD

[oregon]

Esamina le due stringhe lettera per lettera, usando due indici, diciamo i e j ...

Cerca la prima lettera della parola "vallo" a partire dalla prima lettera di "cavallo" e vedi se è uguale ...

Se non lo è (ma occhio alla fine della stringa), passa alla prossima lettera finché non la trovi ...

Se l'hai trovata, passa alla seconda lettera di "vallo" e continua la ricerca nella prima ... e così via.

[IlPrescelto]

Ammetto di averci pensato ma non ricordo perchè ho scartato questo metodo. Adesso provo e poi ti saprò dire

[ramy89]

Se hai la stringa s1 e s2 (s2 è la seconda stringa data in input), di lunghezza rispettivamente n1 e n2.Credi due array di interi v1 e v2.
In v1 ci metti una qualsiasi sequenza strettamente crescente di interi.
Poi per ogni j caratetre di s2, vai a vedere in quale indice di s1 si trova.Se non è presente concludi che s2 non soddisfa i requisiti, se è presente, supponiamo sia presente nella posizione i-esima di s1, nella posizione j-esima di v2 scrivi i.
Così per ogni carattere di s2.Se alla fine dell'algoritmo il vettore v2 è ordinato, allora s2 soddisfa i requisiti.

[ramy89]

Ho scritto una soluzione del problema in C, però non prenderla per oro colato.Potrebbe non essere giusta per tutti gli input.
Comunque ti suggerisco di provare a scrivere una soluzione tua.

int find(char *s1, char elem)
{
    int index=-1;
    for(int i=0;i<strlen(s1) && index==-1;i++)
    {
        if(s1[i]==elem)
            index=i;
    }
    return index;
}

int main(int argc, char **argv)
{
    char buf1[LENGTH],buf2[LENGTH];
    bool ok=true;
    int *v1,*v2;
    input(buf1);
    input(buf2);
    v1=(int*)malloc(strlen(buf1)*sizeof(int));
    v2=(int*)malloc(strlen(buf2)*sizeof(int));
    for(int i=0;i<strlen(buf1);i++)
        v1[i]=i;
    for(int i=0;i<strlen(buf2);i++)
        v2[i]=find(buf1,buf2[i]);
    for(int i=0;i<strlen(buf2)-1 && ok;i++)
    {
        if(v2[i]>v2[i+1] || v2[i]==-1)
            ok=false;
    }
    printf("%d\n",ok);
    free(v1);
    free(v2);
    return 0;
}

[MItaly]

    for(int i=0;i<strlen(s1) && index==-1;i++)

in linea di massima tirerei fuori la strlen: se il compilatore è abbastanza furbo può notare che è un'invariante, ma se non lo è stai ri-valutando strlen(s1) ad ogni iterazione del ciclo, il che significa scorrere la stringa fino in fondo ogni volta (il tuo ciclo diventa da O(n) a O(n^2)).

[IlPrescelto]

Grazie degli aiuti ma mi dovrò impegnare per capire quello che hai scritto xD comunque quella postata da Oregon non mi convince molto... Prendiamo in esempio vallo. Se io tengo la prima lettera V e controllo se è presente in cavallo, una volta che l'ho trovata passo ad a e fin qui ci siamo. Però dovrei ripartire da dove ho trovato la V e non dall'inizio perchè se per caso la v è presente prima della a mi viene contata giusta anche se è sbagliata.

[oregon]

Originariamente inviato da IlPrescelto
Grazie degli aiuti ma mi dovrò impegnare per capire quello che hai scritto xD comunque quella postata da Oregon non mi convince molto... Prendiamo in esempio vallo. Se io tengo la prima lettera V e controllo se è presente in cavallo, una volta che l'ho trovata passo ad a e fin qui ci siamo. Però dovrei ripartire da dove ho trovato la V e non dall'inizio perchè se per caso la v è presente prima della a mi viene contata giusta anche se è sbagliata.

Non ho capito ... fai un esempio con due stringhe ...

[ramy89]

Originariamente inviato da MItaly
in linea di massima tirerei fuori la strlen: se il compilatore è abbastanza furbo può notare che è un'invariante, ma se non lo è stai ri-valutando strlen(s1) ad ogni iterazione del ciclo, il che significa scorrere la stringa fino in fondo ogni volta (il tuo ciclo diventa da O(n) a O(n^2)).

Già, meglio salvare il valore di strlen in una variabile.

Originariamente inviato da IlPrescelto
Grazie degli aiuti ma mi dovrò impegnare per capire quello che hai scritto xD

Non serve, basta che provi a scrivere in C l' algoritmo che ho descritto a parole:

Se hai la stringa s1 e s2 (s2 è la seconda stringa data in input), di lunghezza rispettivamente n1 e n2.Credi due array di interi v1 e v2.
In v1 ci metti una qualsiasi sequenza strettamente crescente di interi.
Poi per ogni j caratetre di s2, vai a vedere in quale indice di s1 si trova.Se non è presente concludi che s2 non soddisfa i requisiti, se è presente, supponiamo sia presente nella posizione i-esima di s1, nella posizione j-esima di v2 scrivi i.
Così per ogni carattere di s2.Se alla fine dell'algoritmo il vettore v2 è ordinato, allora s2 soddisfa i requisiti.

[IlPrescelto]

Ci stavo pensando su ma ha un problemino... Mettiamo il caso che sia Aca-ca. Io tengo la C e scorro Aca. Mi legge che è nella seconda posizione e me lo salvo, come hai detto tu. A questo punto mi tengo la A ma nella parola più grande questa è anche prima della C e mi conterà errore.