| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
LCP - 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łowaabaabaabbaababaabaa, 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: | Rafal Nowak |
| Data dodania: | 2007-06-06 |
| Limit czasu wykonania programu: | 0.100s-1s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET |
| Pochodzenie: | Własne |