Matryca
Limit pamięci: 128 MB
Bajtocki Zakład Poligraficzny (BZP) otrzymał duże zlecenie na produkcję
prążkowanych tapet, stanowiących hit sezonu w projektowaniu wnętrz.
Każda tapeta składa się z jednakowej szerokości barwnych pionowych pasków.
BZP ma zająć się zaprojektowaniem oraz wydrukowaniem tapet.
Zleceniodawca z założenia określił barwy niektórych pasków na tapecie.
W przypadku pozostałych pasków pozostawił BZP pełną dowolność.
Do wydruku tapet w BZP używa się matryc drukujących pewną liczbę kolejnych pasków na tapecie.
Matryca ma określone barwy każdego z drukowanych pasków i może być krótsza niż cała tapeta.
Jeśli matryca składa się z pasków, przykłada się ją we wszystkich
możliwych pozycjach, na których jej paski pokrywają się z paskami tapety,
za każdym razem drukując wszystkie paski matrycy.
W ten sposób jeden pasek tapety może zostać zadrukowany więcej niż raz.
W przypadku, gdy dany pasek zostanie zadrukowany różnymi barwami, jego ostateczny
kolor będzie stanowił mieszankę tych barw.
Pracownicy BZP, niezależnie od posiadanego wyczucia estetyki, chcieliby przede
wszystkim zaprojektować możliwie najkrótszą matrycę, która pozwoli wydrukować całą tapetę.
Muszą oni pamiętać o tym, że w przypadku pasków określonych przez zleceniodawcę
muszą użyć czystej barwy, bez domieszki innych barw.
Innymi słowy, przy każdym przyłożeniu matrycy pokrywającym taki pasek, barwa
paska na matrycy musi być dokładnie taka, jak określona przez zleceniodawcę.
Wejście
Jedyny wiersz wejścia zawiera napis złożony z wielkich liter alfabetu łacińskiego
oraz gwiazdek (*), określający oczekiwany wygląd tapety.
Poszczególne litery oznaczają różne barwy pasków, natomiast gwiazdki oznaczają
paski, których barwa nie została określona przez zleceniodawcę.
Długość napisu spełnia .
Wyjście
Twój program powinien wypisać jeden wiersz zawierający jedną liczbę całkowitą :
minimalną długość matrycy, która pozwala wydrukować żądaną tapetę.
Przykład
Dla danych wejściowych:
A*B*B*A
poprawną odpowiedzią jest:
6
Wyjaśnienie do przykładu:
Matryca o długości 6 pozwalająca wydrukować przedstawioną na wejściu tapetę (złożoną z siedmiu pasków) to ABBBBA.
Autor zadania: Jakub Radoszewski.