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 anbn i bnan 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 anbn en la seqüència de caràcters d’entrada, un espai en blanc, i el nombre de vegades que apareix el submot bnan 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.
Input
2 aaabbbaababbaabababbbaaaaabbbbabbbbabbaaaaabbabaaaaaaaabbaabbaaabaaaa
Output
5 6
Input
1 aabaabaabbbbbabaabbbaaabbbaaabbaabbabbbbbabbbaababbbaaaaabaababbabaabaaabaaabaabaabbbaaabbbbabbbaaaaabbabbbbaabbbabbbabbbbaaaabbaaabbbabbbbaaaabbabbbbababbbabbbaabaabaabbbaaaaabbaabbaabaabaabaaabbabba
Output
46 46
Input
3 baabaabaabaababbbababaabaaabaabababbbbaabbbbabbaaabababbbabbbbaaaaaaabbbbbbabababbabaababbaababababbabbabbbbabbabababbbbabaaaaaabaaababbbbaabaabbaababbbbbbaaabbbbababaabbaaabaaaaabaaaaaababbabbbabbbaa
Output
2 2
Input
5 aaabbaaaaaabbabbbbbbaaaaaaaaaabbbbbbbbbbaabaaaaaaabbbbbbbbbbaaaabaaaaabbbbbbabbbabaaaaaaaabbbbbbbbbbbaaaabaaaababbbbbbbbaaaaabaaaabbbbbbbbbbaaaaaaaaaabbbbbbbbbbaaaaabaaaabbbbbabbbbaaaaaaaababbbbbbbbbb
Output
5 4
- Author
- PRO1
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++