AlgoLiga 2018

Podsłowo jest to spójny podciąg łańcucha znaków.

Wspólne podsłowo dwóch słów jest to słowo które jest podsłowem zarówno w pierwszym słowie, jak i w drugim.

Masz dane dwa słowa A i B. Dla każdego podsłowa w słowie A wyznacz długość najdłuższego wspólnego podsłowa tego podsłowa oraz słowa B.

Wejście

W pierwszej linii znajduje się wyraz A, w drugiej lini wyraz B. Oba wyrazy składają się tylko z małych liter alfabetu łacińskiego, a ich długość nie przekracza 5000.

Wyjście

Przyjmijmy że n jest długością słowa A.

Na wyjście należy wpisać n liczb. i'ta liczba opisuje sumę wszystkich długości najdłuższych wspólnych podsłów dla słowa B oraz dla wszystkich różnych podsłów słowa A zaczynających się na i'tej pozycji (zobacz wyjaśnienie dla przykładu dla lepszego zrozumienia).

Przykład

Wejście:
abcbab
abaabc

Wyjście:
15
9
6
5
3
1

Wyjaśnienie dla przykładu:
Niech j'ta liczba w i'tej linii przedstawia długośc najdłuższego wspólnego podsłów dla słowa B
oraz podsłowa słowa A zaczynającego się na pozycji i i kończącego na pozycji i + j - 1.
Wtedy dla przykładu długości najdłuższych wspólnych podsłów wyglądają tak:
1 2 3 3 3 3 
1 2 2 2 2 
1 1 2 2 
1 2 2 
1 2 
1

Żeby otrzymać wynik wystarczy zsumować każdy wiersz, ponieważ w każdym i'tym wierszu 

znajdują się znalezione długości dla wszystkich podsłów zaczynających się na i'tej pozycji.