Problem description
Bajtazar jest naukowcem zatrudnionym w Gdyńskim Centrum Biologii Obliczeniowej. Pracuje jako informatyk teoretyk i zajmuje się przede wszystkim projektowaniem efektywnych algorytmów operujących na napisach, wzorcach i tekstach. Ostatnio Bajtazar dostał zlecenie, aby przygotować program umożliwiający wyznaczanie współczynnika podobieństwa danego wzorca i tekstu.
Współczynnik ten oblicza się następująco. Wzorzec można dopasować do tekstu na wiele różnych sposobów. Interesują nas tylko takie konfiguracje, w których każda litera wzorca jest przyporządkowana do jakiejś litery tekstu. Ponadto, w dopasowaniu nie może być dziur, tzn. wzorzec musi zostać dopasowany do fragmentu tekstu o długości równej długości wzorca. Dla każdego takiego dopasowania wyznaczamy liczbę pozycji, na których litera wzorca jest taka sama jak odpowiadająca jej litera tekstu. Napisz program, który wczyta wzorzec i tekst, wyznaczy współczynnik podobieństwa i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się niepusty napis złożony z małych liter alfabetu angielskiego – jest to wzorzec. W drugim wierszu standardowego wejścia również znajduje się niepusty napis złożony z małych liter alfabetu angielskiego – jest to tekst. Możesz założyć, że długość wzorca nie przekracza długości tekstu.
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą: współczynnik podobieństwa wzorca i tekstu.
Ograniczenia
Długość tekstu nie przekracza 2 000 000 znaków.
W testach wartych łącznie 25% maksymalnej punktacji długość tekstu nie przekracza 5 000 znaków.
Przykład
| Input | Output | |
|
|