Donat n, quantes ocurrències de "ababab...ab" (amb "ab" n cops) apareixen en una secuencia d'entrada X68833
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 del submot (ab)n conté, incloent encavalcaments.
Per exemple, si n és 3, llavors ha de dir quantes ocurrències de ababab 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 (ab)n en la seqüència de caràcters d’entrada, incloent encavalcaments.
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 aaabbbabaabababbbabababaabababbababa
Output
7
Input
1 aabaabaabbbbbabaabbbaaabbbaaabbaabbabbbbbabbbaababbbaaaaabaababbabaabaaabaaabaabaabbbaaabbbbabbbaaaaabbabbbbaabbbabbbabbbbaaaabbaaabbbabbbbaaaabbabbbbababbbabbbaabaabaabbbaaaaabbaabbaabaabaabaaabbabba
Output
46
Input
3 baabaabaabaababbbababaabaaabaabababbbbaabbbbabbaaabababbbabbbbaaaaaaabbbbbbabababbabaababbaababababbabbabbbbabbabababbbbabaaaaaabaaababbbbaabaabbaababbbbbbaaabbbbababaabbaaabaaaaabaaaaaababbabbbabbbaa
Output
6
Input
5 bbaabbababbbabbaabaaababababbbabbbabababababababbbabababababbbababaaababababbbababababababbbababababaabbaabbabababababababbbaabaabababaaababaaaaaaabaaabababababbbabbaabababbbaaababbbabababababbbaaabab
Output
11
- Author
- PRO1
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++