Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_24_06 - Podsłowa, podsłowa wszędzie!

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 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.

Dodane przez:Bartek
Data dodania:2015-08-26
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY

ukryj komentarze
2015-08-29 18:38:23 Karol Waszczuk
W takim razie przydałaby się poprawka w wyjaśnieniu, ponieważ mowa tam o najdłuższych wspólnych podciągach.
2015-08-29 18:28:21 Bartek
Pewnie masz racje, ale w tym zadaniu szukamy podsłów, nie podciągów.
2015-08-29 18:25:56 Karol Waszczuk
Czy przypadkiem długość najdłuższego wspólnego podciągu dla podciągu słowa A od i = 1, j = 6 nie wynosi 4, bo:

ABcbAB
ABAaBc
2015-08-29 16:41:42 Bartek
1536MB
2015-08-29 16:38:56 Pawe³ Ma¶luch
Jaki limit pamięci ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.