POLSKI SPOJ

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

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.064s-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
Pochodzenie:Własne

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