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₁, c₂, c₃. A més a més, al principi de s hi trobem el caràcter c₁ una o més vegades, després ve el caràcter c₂ una o més vegades, i finalment ve el caràcter c₃ una o més vegades. La funció tindrà també tres paràmetres enters per referència n₁, n₂, n₃, a on hi haurà de dipositar el nombre d’ocurrències de c₁, c₂, c₃, 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.