Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Świadek nieokresowości (swiadek-nieokres) Memory limit: 32 MB Time limit: 0.50 s Mówimy, że słowo s o długości n ma okres długości p wtedy i tylko wtedy, gdy dla dowolnego znaku na pozycji i ≤ n − p, na pozycji i + p występuje ten sam znak. Na przykład: słowo abaabaabaab ma okresy długości 3, 6 oraz 9. W tym zadaniu wyjątkowo niezbyt interesuje nas znajdowanie okresów słów, ale świadków nieokresowości. Jeśli słowo nie ma okresu długości p, świadkiem jego nieokresowości (dla okresu długości p) nazwiemy minimalną liczbę (pozycję) i, że znak i-ty i i + p-ty są różne. Na przykład ponownie dla słowa: abaabaabaab świadkiem nieokresowości dla okresu długości 2 jest 2 (na drugiej pozycji w słowie występuje litera b, zaś na czwartej litera a). Napisz program, który: wczyta słowo s, dla każdej potencjalnej długości okresu (od 1 do długości słowa s) wyznaczy jej świadka nieokresowości (lub stwierdzi, że takowy nieistnieje) i wypisze wyniki na standardowe wyjście. Wejście W pierwszym (i jedynym) wierszu wejścia znajduje się niepusty ciąg znaków alfabetu angielskiego – słowo s. Wyjście W pierwszym (i jedynym) wierszu wyjścia powinien się znaleźć ciąg liczb pooddzielanych pojedynczymi odstępami o długości równej długości słowa s. i-ta liczba powinna być świadkiem nieokresowości słowa s dla okresu długości i lub powinna być równa 0 jeśli słowo s ma okres o długości i. Ograniczenia Długość słowa nie przekracza 1 000 000 znaków. Przykład Input Output Explanation abaab 1 2 0 1 0 Podane słowo ma okresy długości 3 oraz 5, stąd trzecia i piąta liczba na wyjściu powinna być równa 0. Aby słowo miało okres długości 1 musiałoby składać się z tych samych liter, tymczasem już drugi znak jest różny od pierwszego (stąd pierwsza liczba na wyjściu powinna być 1). Analogicznie pierwszy znak słowa różni się od piątego (stąd czwarta liczba na wyjściu powinna być 1). Podane słowo nie ma też okresu długości 2 czego dowodem jest różnica znaków na drugiej i czwartej pozycji.

Input	Output	Explanation
`abaab`	`1 2 0 1 0`	Podane słowo ma okresy długości 3 oraz 5, stąd trzecia i piąta liczba na wyjściu powinna być równa 0. Aby słowo miało okres długości 1 musiałoby składać się z tych samych liter, tymczasem już drugi znak jest różny od pierwszego (stąd pierwsza liczba na wyjściu powinna być 1). Analogicznie pierwszy znak słowa różni się od piątego (stąd czwarta liczba na wyjściu powinna być 1). Podane słowo nie ma też okresu długości 2 czego dowodem jest różnica znaków na drugiej i czwartej pozycji.