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.

Zadanie w systemie SPOJ (trudne)

1614. LCP

Kod zadania: LCP

Advertisement blocking software were detected ;( Please add this webpage to whitelist.

LCP

Pewnie już poznałeś problem Porządek sufiksów. Tym razem sortujemy sufiksy przyjmując, że na końcu łancucha znaków znajduje się unikatowy symbol największy w alfabecie. Na przykład dla słowa abaabaabbaababaabaa, porządek sufiksów jest nastepujacy:
 0 : (lcp= 5) : S_{ 2} : aabaabbaababaabaa
 1 : (lcp= 4) : S_{14} : aabaa
 2 : (lcp= 3) : S_{ 9} : aababaabaa
 3 : (lcp= 2) : S_{ 5} : aabbaababaabaa
 4 : (lcp= 1) : S_{17} : aa
 5 : (lcp= 7) : S_{ 0} : abaabaabbaababaabaa
 6 : (lcp= 5) : S_{12} : abaabaa
 7 : (lcp= 4) : S_{ 3} : abaabbaababaabaa
 8 : (lcp= 3) : S_{15} : abaa
 9 : (lcp= 2) : S_{10} : ababaabaa
10 : (lcp= 1) : S_{ 6} : abbaababaabaa
11 : (lcp= 0) : S_{18} : a
12 : (lcp= 6) : S_{ 1} : baabaabbaababaabaa
13 : (lcp= 5) : S_{13} : baabaa
14 : (lcp= 4) : S_{ 8} : baababaabaa
15 : (lcp= 3) : S_{ 4} : baabbaababaabaa
16 : (lcp= 2) : S_{16} : baa
17 : (lcp= 1) : S_{11} : babaabaa
18 :          : S_{ 7} : bbaababaabaa

Pewnie zauważyłeś, że wypisywane są pewne liczby lcp (longest common prefix) - długość najdłuższego wspólnego prefiksu z następnym w kolejności leksykograficznej sufiksem.

Twoim zadaniem jest wyznaczyć tablicę LCP

Specyfikacja wejścia

W pierwszym wierszu dana jest liczba n napisów (n < 20). W kolejnych wierszach dane są słowa złożone tylko z liter {a-z}. Każde słowo ma nie więcej niż 1000000 znaków.
Przykładowe wejście
3
ababa
abc
abaabaabbaababaabaa

Wyjście
3 1 0 2
0 0
5 4 3 2 1 7 5 4 3 2 1 0 6 5 4 3 2 1

Dodane przez:Rafał Nowak
Data dodania:2007-06-06
Limit czasu wykonania programu:0.100s-0.639s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Języki programowania:All except: ERL JS NODEJS PERL 6 VB.net
Pochodzenie:WĹ‚asne

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.