AB-słowa
Limit pamięci: 32 MB
Każdy niepusty ciąg, którego elementami są małe litery i , a także ciąg pusty nazywamy ab-słowem.
Jeżeli jest ab-słowem, a takimi dowolnymi liczbami całkowitymi,
że , to przez będziemy oznaczali podsłowo składające się z kolejnych liter .
Powiemy, że ab-słowo jest ładnie zbudowane, jeżeli zawiera tyle samo liter , co i dla każdego
podsłowo zawiera co najmniej tyle samo liter , co liter .
Podamy teraz indukcyjną definicję podobieństwa ładnie zbudowanych ab-słów:
- każde dwa puste ab-słowa (tzn. nie zawierające żadnych liter) są podobne;
- dwa niepuste, ładnie zbudowane ab-słowa i są podobne,
jeżeli są tej samej długości () i jest spełniony jeden z następujacych warunków:
- , oraz i są ładnie zbudowanymi, podobnymi ab-słowami,
- istnieje , , takie, że słowa , są ładnie zbudowanymi ab-słowami i
- , są ładnie zbudowanymi ab-słowami i jest podobne do oraz jest podobne do lub
- , są ładnie zbudowanymi ab-słowami i jest podobne do oraz jest podobne do .
Stopniem zróżnicowania niepustego zbioru ładnie zbudowanych ab-słów nazywamy największą liczbę ab-słów,
które można wybrać z tak, żeby żadne dwa wybrane słowa nie były do siebie podobne.
Zadanie
Napisz program, który
- wczyta ze standardowego wejścia elementy zbioru ;
- policzy stopień zróżnicowania ;
- zapisze wynik na standardowe wyjście.
Wejście
Na standardowym wejściu znajdą się:
- w pierwszym wierszu liczba elementów zbioru , ;
- w kolejnych wierszach elementy zbioru tj. ładnie zbudowane ab-słowa,
po jednym w każdym wierszu; pierwsza litera każdego ab-słowa jest pierwszym symbolem w wierszu i między kolejnymi literami
w słowie nie ma żadnych innych znaków; każde ab-słowo ma długość co najmniej , a co najwyżej .
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą — stopień zróżnicowania .
Przykład
Dla danych wejściowych:
3
aabaabbbab
abababaabb
abaaabbabb
poprawną odpowiedzią jest:
2
Autor zadania: Krzysztof Diks.