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.