Pytania otagowane jako suffix-array

3
Obliczanie najdłuższego wspólnego podłańcucha dwóch łańcuchów przy użyciu tablic sufiksów
Po tym, jak nauczyłem się, jak budować tablicę sufiksów w złożoności , jestem zainteresowany odkrywaniem zastosowania tablic sufiksów. Jednym z nich jest znalezienie najdłuższego wspólnego podłańcucha między dwoma łańcuchami w czasie . W Internecie znalazłem następujący algorytm:O(N)O(N)O(N)O(N)O(N)O(N) połącz dwa ciągi AAA i BBB w jeden ciąg ABABAB obliczyć tablicę przyrostków …
1
Zliczanie liczby sum z przyległych podtablic tablicy
Otrzymujemy tablicę ze wszystkimi .a[1…n]a[1…n]a[1 \ldots n]a[i]>0a[i]>0a[i]>0 Teraz musimy dowiedzieć się, ile różnych sum można uformować z jego podstron (gdzie podtablica to ciągły zakres tablicy, tj. dla niektórych , suma jest sumą wszystkich elementy podtablicy). Na przykład, jeśli , to odpowiedź brzmi 4: możemy utworzyć .a[j…k]a[j…k]a[j\ldots k]j,kj,kj,ka=[1,2,1]a=[1,2,1]a=[1,2,1]1,2,3,41,2,3,4 1,2,3,4 Wiem, jak …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.