Donat n, Cuantes ocurrències de a...ab...b i b..ba...a (amb n a's i n b's) apareixen en una secuencia d'entrada X25258

Escriviu un programa que llegeixi un natural positiu n i una seqüència de caràcters d’entrada sobre {a,b}, i digui quantes ocurrències dels submots $a^nb^n$ i $b^na^n$ conté, respectivament.

Per exemple, si n és 3, llavors ha de dir quantes ocurrències de aaabbb i quantes ocurrències de bbbaaa conté la seqüència d’entrada.

Entrada

L’entrada té un natural positiu n en una primera línia, i una seqüència de caràcters ’a’ o ’b’ en una segona línia.

Sortida

El nombre de vegades que apareix el submot $a^nb^n$ en la seqüència de caràcters d’entrada, un espai en blanc, i el nombre de vegades que apareix el submot $b^na^n$ en la seqüència de caràcters d’entrada, seguit de salt de línia.

Observació

No es poden utilitzar mètodes d’emmagatzemament massiu d’informació (com per exemple string o vector). Llegiu l’entrada caràcter a caràcter.

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 lineal 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.