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:	1s-20s
Limit długości kodu źródłowego	50000B
Limit pamięci:	256MB
Cluster:	Pyramid (Intel Pentium III 733 MHz)
Języki programowania:	All except: ERL JS NODEJS PERL 6
Pochodzenie:	Własne