Třídy ekvivalence

Je dán neprázdný řetězec S skládající se výhradně ze znaků malých písmen anglické abecedy (a, b, c, ..., z).

Hodnotu znaku definujeme jako pořadové číslo tohoto znaku v seznamu (a, b, c, ..., z), hodnota a je tak 1, hodnota b je 2, atd, hodnota z je 26.

V této úloze standardní pojem podřetězec mírně omezíme a budeme jím rozumět právě každý (běžný) podřetězec řetězce S, jehož délka je alespoň 2 a zároveň je menší než délka S. Nebudeme tedy uvažovat prázdný podřetězec, podřetězce délky 1 a samotný S jako svůj vlastní podřetězec.

Řekneme, že dva podřetězce A a B řetězce S jsou ve slabém kontaktu, pokud první znak A leží vlevo od prvního znaku B a pro poslední znak A platí, že neleží vlevo od prvního znaku B a zároveň leží vlevo od posledního znaku B. Pokud A a B jsou ve slabém kontaktu, řekneme, že také B a A jsou ve slabém kontaktu. Relace "být ve slabém kontaktu" je tedy symetrickou relací na množině všech podřetězců S.
Příklad: S = abcdef, A = bcd, B = cdef, A a B jsou ve slabém kontaktu.
S = abcdef, A = ab, B = cde, A a B nejsou ve slabém kontaktu.
S = abcdef, A = bcde, B = cd, A a B nejsou ve slabém kontaktu.

Řekneme, že dva podřetězce A a B řetězce S jsou v silném kontaktu, pokud jsou jednak ve slabém kontaktu a zároveň pokud součet hodnot těch znaků A, které neleží v B, je roven součtu hodnot těch znaků B, které neleží v A. Relace "být v silném kontaktu" je také symetrickou relací na množině všech podřetězců S.
Příklad: S = aabdxybea, A = abdxy, B = xybe, A a B jsou v silném kontaktu, součet hodnot a, b, d je 7, stejně jako součet hodnot b, e.

Relaci ekvivalence na množině všech podřetězců S definujeme rekurentně takto:
Nechť A a B jsou podřetězce S.
1. Pokud A a B jsou v silném kontaktu, pak A a B prohlásíme za ekvivalentní.
2. Pokud existuje podřetězec C řetězce S takový, že A je ekvivalentní s C a zároveň B je ekvivalentní s C, pak A a B prohlásíme za ekvivalentní.
3. Každý podřetězec řetězce S prohlásíme za ekvivalentní se sebou samým.

Úloha
Máme vypsat v neklesajícím pořadí mohutnosti všech tříd ekvivalence na množině všech podřetězců S.

Vstup

Na vstupu je jeden textový řádek obsahující právě řetězec S. Délka S je alespoň 3 a nejvýše 500.

Výstup

Na výstupu je jeden textový řádek obsahující v neklesajícím pořadí mohutnosti všech tříd ekvivalence na množině všech podřetězců S. Sousední údaje na řádku jsou odděleny jednou mezerou a řádek neobsahuje úvodní mezeru, může obsahovat koncové mezery.

Příklad 1

Vstup:

aaaaaa

Výstup:

2 3 4 5

Jednotlivé třídy ekvivalence, které jsou celkem čtyři, zachycuje následující seznam množin podřetězců, znaky S neobsažené v konkrétním podřetězci jsou pro větší přehlednost nahrazeny tečkami.

{aaaaa. | .aaaaa},
{aaaa.. | .aaaa. | ..aaaa},
{aaa... | .aaa.. | ..aaa. | ...aaa},
{aa.... | .aa... | ..aa.. | ...aa. | ....aa}.

Příklad 2

Vstup:

acacaca

Výstup:

1 2 2 2 3 4 6

Jednotlivé třídy ekvivalence, jichž je celkem 7, zachycuje následující seznam množin podřetězců, znaky S neobsažené v konkrétním podřetězci jsou pro větší přehlednost nahrazeny tečkami.

{.cacac.},
{acaca.. | ..acaca},
{acacac. | .cacaca},
{.cac... | ...cac.},
{aca.... | ..aca.. | ....aca},
{acac... | .caca.. | ..acac. | ...caca},
{ac..... | .ca.... | ..ac... | ...ca.. | ....ac. | .....ca}.

Příklad 3

Vstup:

aabbaabaabb

Výstup:

1 1 1 1 1 1 1 1 2 2 2 3 3 4 5 5 5 7 8 

Jednotlivé třídy ekvivalence, jichž je celkem 19, zachycuje následující seznam množin podřetězců, znaky S neobsažené v konkrétním podřetězci jsou pro větší přehlednost nahrazeny tečkami.

{aa.........},
{.ab........},
{.abbaabaab.},
{.abbaabaabb},
{...ba......},
{....aa.....},
{.......aa..},
{........ab.},
{aabbaaba... | .abbaabaa..},
{aabbaabaab. | ..bbaabaabb},
{.....ab.... | ......ba...},
{aabbaabaa.. | ..bbaabaab. | ...baabaabb},
{.abbaab.... | ..bbaaba... | .....abaabb},
{aabba...... | .abbaa..... | ...baaba... | .....abaab.},
{aabbaa..... | ..bbaab.... | ...baabaa.. | ....aabaab. | ......baabb},
{aabbaab.... | .abbaaba... | ..bbaabaa.. | ...baabaab. | ....aabaabb},
{.abb....... | ..bba...... | ....aaba... | .....abaa.. | ........abb},
{aabb....... | .abba...... | ..bbaa..... | ...baab.... | ....aabaa.. | ......baab. | .......aabb},
{aab........ | ..bb....... | ...baa..... | ....aab.... | .....aba... | ......baa.. | .......aab. | .........bb}.

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data