W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Szablonem słowa nazwiemy takie słowo , że wszystkie wystąpienia w pokrywają całkowicie słowo (tzn. każda litera słowa znajduje się wewnątrz jakiegoś spójnego fragmentu równego ). Prawie szablonem słowa nazwiemy takie słowo , że jest podsłowem (tj. spójnym fragmentem) oraz jest szablonem pewnego nadsłowa słowa . Poniższy rysunek pokazuje, dlaczego słowo aabaa jest prawie szablonem słowa aaaabaabaaaba:
Dla danego słowa należy wyznaczyć liczbę jego prawie szablonów oraz najkrótszy z nich.
W jedynym wierszu standardowego wejścia znajduje się niepuste słowo o długości nie większej niż . Składa się ono z małych liter alfabetu angielskiego.
W pierwszym wierszu standardowego wyjścia należy wypisać liczbę prawie szablonów słowa . W drugim wierszu należy wypisać najkrótszy prawie szablon słowa . Jeśli jest więcej niż jeden najkrótszy prawie szablon, to należy wypisać leksykograficznie najmniejszy spośród najkrótszych prawie szablonów.
Dla danych wejściowych:
aaaabaabaaaba
poprawną odpowiedzią jest:
10 aabaa
Podane w przykładowym wejściu słowo ma dziesięć prawie szablonów: aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa oraz abaabaaa.
Autor zadania: Tomasz Idziaszek.