PROBLEMA Aiuto con esercizio su stringhe (C)

[slyhardrock]

Ciao a tutti, vorrei chiedervi un aiuto per questo eserczio con stringhe in C. Ecco il testo dell'esercizio e la soluzione parziale. Vorrei chiedervi di aiutarmi a capire i passaggi che segnerò.


Testo esercizio:

https://imgur.com/a/HFWp8

Soluzione della funzione:

int anagramma(unsigned char *x, unsigned char *y) {
int i;
int xc[256], yc[256];
for (i = 0; i < 256; i++) { xc = yc = 0; }
int lenx = strlen(x);
int leny = strlen(y);
if(lenx != leny) return 0;
for (i = 0; i < lenx ; i++) {
xc[x] += 1; * Non capisco questo passaggio
yc[y] += 1; e questo
}
for (i = 0; i < 256; i++) {
if (xc != yc) return 0; * di conseguenza questo.
}
return 1;
}


Non riesco a capire proprio la sintassi di questi passaggi, che vuol dire xc[x]? Come andamento generale riesco a capirlo. Grazie ancora.

 

[_Achille]

Tecnicamente l’algoritmo si basa sulla stessa tecnica del CountingSort. Se due stringhe sono anagrammi, allora hanno lo stesso numero di lettere per ciascuna di esse.
xc e xy sono due vettori che tengono conto quante volte di incontra una lettera. L’inizializzazione può essere semplificata facendo

int xc[256]={0};
int yc[256]={0};

Quei passaggi che non capisci dovrebbero scorrere le stringhe e aumentare di 1 ogni carattere ASCII che si incontra (“ape” dovrebbe aumentare xc[96], xc[100] e xc[111] di 1).
Il problema? È che non sono sicuro del funzionamento. Tecnicamente una stringa del tipo const char* dovrebbe restituire l’intera stringa + carattere di terminazione, quindi il ciclo dovrebbe aumentare di 1 lo stesso valore perché secondo me non viene restituito la singola lettera ma la stringa piena.

Ma è la soluzione del problema?

 

[slyhardrock]

Tecnicamente l’algoritmo si basa sulla stessa tecnica del CountingSort. Se due stringhe sono anagrammi, allora hanno lo stesso numero di lettere per ciascuna di esse.
xc e xy sono due vettori che tengono conto quante volte di incontra una lettera. L’inizializzazione può essere semplificata facendo

int xc[256]={0};
int yc[256]={0};

Quei passaggi che non capisci dovrebbero scorrere le stringhe e aumentare di 1 ogni carattere ASCII che si incontra (“ape” dovrebbe aumentare xc[96], xc[100] e xc[111] di 1).
Il problema? È che non sono sicuro del funzionamento. Tecnicamente una stringa del tipo const char* dovrebbe restituire l’intera stringa + carattere di terminazione, quindi il ciclo dovrebbe aumentare di 1 lo stesso valore perché secondo me non viene restituito la singola lettera ma la stringa piena.

Ma è la soluzione del problema?

Si, questa è la soluzione parziale del problema, ovvero solo la funzione, poi si dovrebbe scrivere tutto il programma. Comunque copiando non riporta tutti i caratteri, allego la foto della soluzione. Non riesco a capire dal for per xc [x [ i] ] in poi, proprio come sintassi. Ti ringrazio

https://imgur.com/a/o6SYe

 

[_Achille]

Si, questa è la soluzione parziale del problema, ovvero solo la funzione, poi si dovrebbe scrivere tutto il programma. Comunque copiando non riporta tutti i caratteri, allego la foto della soluzione. Non riesco a capire dal for per xc [x [ i] ] in poi, proprio come sintassi. Ti ringrazio

https://imgur.com/a/o6SYe

Ahh ora è perfettamente giusto.
Un puntatore può essere utilizzato con la sintassi degli array. Per capire meglio utilizza la sintassi dei puntatori. Ecco il codice fatto meglio:

#include <iostream>
using std::cout;
#include <cstring>
using std::strlen;
#include <cstdlib>

bool isAnagram(const char* const, const char* const);

int main()
{

    cout << isAnagram("pizza", "pazzi");

}

bool isAnagram(const char* const string1, const char* const string2)
{

    size_t sizeString1, sizeString2;
    const size_t ASCII = 256;
    int letterOfString1[ASCII] = {0};
    int letterOfString2[ASCII] = {0};

    sizeString1 = strlen(string1);
    sizeString2 = strlen(string2);

    if(sizeString1!=sizeString2)
   
        return false;
   
    for(int i=0; i<sizeString1; i++)
    {
   
        //Equivalente a string1[i]. Stai dereferenziando l'indirizzo di string1 sommato a i*sizeof(char*)
        ++letterOfString1[*(string1+i)];
        ++letterOfString2[*(string2+i)];
    }

    for(int i=0; i<ASCII; i++)

        if(letterOfString1[i]!=letterOfString2[i])
   
            return false;
   
    return true;   

}

Spero tu riesca a capirlo meglio.

Ho fatto solo ora caso che tu programmi in C. Le uniche modifiche sono bool che diventa int, ++ che diventa +=1 e i false/true che diventano 0/1, e ovviamente l'I/O.

 

[DispatchCode]

Si, questa è la soluzione parziale del problema, ovvero solo la funzione, poi si dovrebbe scrivere tutto il programma. Comunque copiando non riporta tutti i caratteri, allego la foto della soluzione. Non riesco a capire dal for per xc [x [ i] ] in poi, proprio come sintassi. Ti ringrazio

https://imgur.com/a/o6SYe

xc ed yc sono indicizzati dal carattere che viene letto. In pratica ogni singolo carattere della stringa viene usato come indice all'interno degli array xc/yc; viene incrementato quindi il contatore che conterrà quante volte il carattere i-esimo si è ripetuto. L'ultimo for verifica che la posizione i dell'array xc abbia lo stesso valore della posizione i di yc.

xc ed yc fanno da "tabella di lookup": alla posizione 'A' (65 in decimale) ci sarà il numero delle ripetizioni di 'A', così come alla posizione 'a' (97) ci sarà il numero delle ripetizioni di 'a'.

 

[slyhardrock]

Ringrazio entrambi ora è più chiaro, rimane solo qualche dubbio per l ASCII. Grazie mille

 

[DispatchCode]

Dubbio di che tipo?
Questa è la tabella ASCII:

In effetti non è a 8bit, ma a 7bit (a 8bit è la ISO-Latin-1 se non ricordo male, che definisce le lettere accentate anche).
In tutti i linguaggi il cast di un carattere ti restituisce il codice a cui corrisponde. Ecco perchè nell'array viene utilizzato come indice: in realtà viene convertito in intero prima dell'accesso all'array.
Il codice sopra, in teoria, dovrebbe supportare ISO-Latin-1, e non proprio ASCII; ma è un estensione di ASCII, che introduce appunto altri caratteri (ecco perchè xc ed yc sono inizializzati a 256 e non a 127, che sono i caratteri definiti da ASCII).

 

[slyhardrock]

Nel codice della soluzione, inizializza due array xc yx di 256 elementi e li indicizza a zero. Poi prende la lunghezza delle due stringhe e se è diversa allora return 0. Tutto ok fino a qui. Poi dal prossimo for non è chiaro del tutto, anzi ora un po' di più dopo le vostre spiegazioni, ma ancora non me ne convinco del tutto. Cioè da quello che hai detto, l'ultimo for verifica che gli indici di entrambi gli array abbiano lo stesso carattere, ma essendo un anagramma non è possibile che magari abbiano lo stesso carattere ma in indici diversi?

 

[DispatchCode]

No, non è possibile poichè gli array xc ed yc fanno da "lookup table" per l'ultima verifica (dell'ultimo for).

Ti faccio un esempio pratico. Consideriamo la stringa 'aeiou' e la stringa 'uoaei', quelle presenti nel tuo screen. I due array xc ed yc vengono inizializzati con 256 elementi tutti a 0. 'aeiou' in decimale sono [97, 101, 105, 111, 117]; 'uoaei' è quindi [117, 111, 97, 101, 105].

Nel secondo for avviene questo:

// Primo ciclo (riporto i valori dei caratteri invece che x[i] ed y[i], per rendere esplicito il procedimento)
xc[97]++;
yc[117]++;

// Secondo ciclo
xc[101]++;
yc[111]++;

// Terzo ciclo
xc[105]++;
yc[97]++;

// Quarto ciclo
xc[111]++;
yc[101]++;

// Quinto ciclo
xc[117]++;
yc[105]++;

Tutte le lettere compaiono una volta in entrambi gli array, e di conseguenza xc ed yc conterranno i seguenti valori: [1, 1, 1, 1, 1]. Ovviamente, mi sembra superfluo precisarlo, ma gli array xc ed yc avranno a 1 solo le posizioni accedute in precedenza, le altre saranno ancora a 0.

Va da sè che con l'ultimo for non avrai elementi differenti in quanto la posizione 0 dell'array xc sarà uguale alla posizione 0 di yc, etc etc.

Se avessi ad esempio le stringhe: "ba" ([98, 97]) e "bc" ([98, 99]) allora avresti questa situazione:

// Primo ciclo
xc[98]++;
yc[97]++;

// Secondo ciclo
xc[98]++;
yc[99]++;

La situazione sopra sarà questa: xc conterrà i valori 1 solo alle posizioni 97 e 98; l'array yc però avrà ad 1 le posizioni 98 e 99 (gli altri valori saranno ovviamente a 0).
L'ultimo ciclo quindi farà questo (riporto solo il primo di nostro interesse):

// i=97
xc[i] == y[c] // false; termina

in quanto la posizione xc[97] è valorizzata (ad 1), mentre la posizione yc[97] non è valorizzata (non essendoci 'a' nella stringa).

 

[slyhardrock]

No, non è possibile poichè gli array xc ed yc fanno da "lookup table" per l'ultima verifica (dell'ultimo for).

Ti faccio un esempio pratico. Consideriamo la stringa 'aeiou' e la stringa 'uoaei', quelle presenti nel tuo screen. I due array xc ed yc vengono inizializzati con 256 elementi tutti a 0. 'aeiou' in decimale sono [97, 101, 105, 111, 117]; 'uoaei' è quindi [117, 111, 97, 101, 105].

Nel secondo for avviene questo:

// Primo ciclo (riporto i valori dei caratteri invece che x[i] ed y[i], per rendere esplicito il procedimento)
xc[97]++;
yc[117]++;

// Secondo ciclo
xc[101]++;
yc[111]++;

// Terzo ciclo
xc[105]++;
yc[97]++;

// Quarto ciclo
xc[111]++;
yc[101]++;

// Quinto ciclo
xc[117]++;
yc[105]++;

Tutte le lettere compaiono una volta in entrambi gli array, e di conseguenza xc ed yc conterranno i seguenti valori: [1, 1, 1, 1, 1]. Ovviamente, mi sembra superfluo precisarlo, ma gli array xc ed yc avranno a 1 solo le posizioni accedute in precedenza, le altre saranno ancora a 0.

Va da sè che con l'ultimo for non avrai elementi differenti in quanto la posizione 0 dell'array xc sarà uguale alla posizione 0 di yc, etc etc.

Se avessi ad esempio le stringhe: "ba" ([98, 97]) e "bc" ([98, 99]) allora avresti questa situazione:

// Primo ciclo
xc[98]++;
yc[97]++;

// Secondo ciclo
xc[98]++;
yc[99]++;

La situazione sopra sarà questa: xc conterrà i valori 1 solo alle posizioni 97 e 98; l'array yc però avrà ad 1 le posizioni 98 e 99 (gli altri valori saranno ovviamente a 0).
L'ultimo ciclo quindi farà questo (riporto solo il primo di nostro interesse):

// i=97
xc[i] == y[c] // false; termina

in quanto la posizione xc[97] è valorizzata (ad 1), mentre la posizione yc[97] non è valorizzata (non essendoci 'a' nella stringa).

Mio Dio sei stato chiarissimo, finalmente ho capito! Grazie mille per la risposta più che esaustiva!