Nombre de subseqüencies felices i tristes en un string amb tres seccions X16298

En aquest exercici heu de fer vàries coses.

En primer lloc, haureu d’implementar una funció que rep un string $s$ que cumpleix unes condicions molt partículars de bon principi: l’string està format per tres caràcters diferents $c_1, c_2, c_3$. A més a més, al principi de $s$ hi trobem el caràcter $c_1$ una o més vegades, després ve el caràcter $c_2$ una o més vegades, i finalment ve el caràcter $c_3$ una o més vegades. La funció tindrà també tres paràmetres enters per referència $n_1, n_2, n_3$, a on hi haurà de dipositar el nombre d’ocurrències de $c_1, c_2, c_3$, respectivament. Aquesta és la capcelera:

// Pre: s is formed with three different characters c1,c2,c3, and is of the form c1...c1c2...c2c3...c3.
// Post: n1, n2, n3 are the number of occurrences of c1, c2, c3 in s, respectively.
void numberOccurrences(const string &s, int &n1, int &n2, int &n3);

Nota: els jocs de proves privats d’aquest exercici son grans estan dissenyats per a que calgui una implementació de cost logaritmic de numberSubsequences. Una implementació lenta us permetrà només superar els jocs de proves públics i obtenir la meitat de la n ota.

En segon lloc, haureu d’implementar una funció que rep un string $s$ que cumpleix una de les següents condicions:

1. $s$ comença per una o més ocurrències de $:$, que venen seguides per una o més ocurrències de $-$, que venen seguides per una o més ocurrències de $)$, i ja no hi ha cap caràcter més.

2. $s$ comença per una o més ocurrències de $($, que venen seguides per una o més ocurrències de $-$, que venen seguides per una o més ocurrències de $:$, i ja no hi ha cap caràcter més.

3. $s$ comença per una o més ocurrències de $:$, que venen seguides per una o més ocurrències de $-$, que venen seguides per una o més ocurrències de $($, i ja no hi ha cap caràcter més.

4. $s$ comença per una o més ocurrències de $)$, que venen seguides per una o més ocurrències de $-$, que venen seguides per una o més ocurrències de $:$, i ja no hi ha cap caràcter més.

En els casos (1) i (2) anteriors, la funció retornarà el nombre de subseqüències felices de $s$, i en els casos (3) i (4) anteriors, la funció retornarà el nombre de subseqüencies tristes de $s$. Una subseqüència feliç és una subsequència de tres caràcters, i a on aquests tres caràcters són, o bé :-) o bé (-:, en l’ordre donat. Una subseqüència trista és una subsequència de tres caràcters, i a on aquests tres caràcters són, o bé :-( o bé )-:, en l’ordre donat. Aquestes son les capceleres:

// Pre: s begins with one or more occurrences of a character c1, followed by one or more
//      occurrences of a character c2, followed by one or more occurrences of a character c3,
//      and there are no more characters in s.
//      moreover, either c1c2c3 = ":-)" or c1c2c3 = "(-:" or c1c2c3 = ":-(" or c1c2c3 = ")-:".
// Post: If c1c2c3 = ":-)" or c1c2c3 = "(-:", the function returns the number of happy subsequences.
//       If c1c2c3 = ":-(" or c1c2c3 = ")-:", the function returns the number of sad subsequences.
int numberHappyOrSadSubsequences(const string &s);

La funció anterior haurà d’usar convenientment la funció numberOccurrences mencionada al principi. En cas contrari, s’invalidarà l’entrega.

Observació

Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

Avaluació sobre 10 punts:

• Solució lenta: 5 punts.

• solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost logarítmic i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.