Najmniejszy obrót leksykograficzny łańcucha przy użyciu tablic sufiksowych w O (n)

Zacytuję problem z ACM 2003:

Rozważ ciąg długości n (1 <= n <= 100000). Określ jego minimalny obrót leksykograficzny. Na przykład obroty ciągu „alabala” to:

alabala

labalaa

abalaal

Balaala

alaalab

laalaba

aalabal

a najmniejsza z nich to „aalabal”.

Co do rozwiązania - wiem, że muszę zbudować tablicę sufiksów - i powiedzmy, że mogę to zrobić w O (n). Moje pytanie wciąż brzmi: jak znaleźć najmniejszy obrót w O (n)? (n = długość łańcucha)

Jestem bardzo zainteresowany tym problemem i nadal nie mam rozwiązania. Bardziej interesuje mnie koncepcja i sposób rozwiązania problemu, a nie konkretna implementacja.

Uwaga: minimalny obrót oznacza w tej samej kolejności, co w słowniku angielskim - „dwor” jest przed „słowem”, ponieważ d jest przed w.

EDYCJA: konstrukcja tablicy sufiksów przyjmuje O (N)

OSTATNIA EDYCJA: Myślę, że znalazłem rozwiązanie !!! Co jeśli po prostu scalę dwa ciągi? Więc jeśli ciąg ma postać „alabala”, nowy ciąg nazwałby mnie „alabalaalabala”, a teraz po prostu skonstruowałbym tablicę sufiksów tego (w O (2n) = O (n)) i otrzymałbym pierwszy przyrostek? Myślę, że to może być właściwe. Co myślisz? Dziękuję Ci!

Prostą sztuczką do skonstruowania wszystkich obrotów łańcucha o długości N jest konkatenacja łańcucha ze sobą.

Następnie każdy podciąg długości N tego ciągu o długości 2 N jest rotacją oryginalnego ciągu.

Lokalizowanie „leksykograficznie minimalnego” podciągu odbywa się następnie za pomocą konstrukcji drzewa O (N).

Jestem prawie pewien, że informacje zawarte w tablicy sufiksów nie są wystarczające, aby uzyskać dostęp do O (n), ale co najwyżej mogą pomóc w uzyskaniu O (n log n). Rozważ tę rodzinę sufiksów:

a
aba
abacaba
abacabadabacaba
abacabadabacabaeabacabadabacaba
...

Kolejny sufiks konstruujesz, biorąc poprzedni sufiks (powiedzmy aba), dodając następny znak, który nie został jeszcze użyty, a następnie ponownie dodając poprzedni sufiks (więc aba -> aba c aba).

Rozważmy teraz te ciągi (spacja jest dodawana dla podkreślenia, ale nie jest częścią ciągu):

ad abacaba
bd abacaba
cd abacaba

Dla tych trzech łańcuchów początek tablicy sufiksów będzie wyglądał następująco:

a
aba
abacaba
(other suffixes)

Wygląda znajomo? Te ciągi znaków są oczywiście dostosowane do tworzenia tablicy sufiksów. Teraz, w zależności od litery początkowej (a, b lub c), „poprawny” indeks (rozwiązanie twojego problemu) jest pierwszym, drugim lub trzecim sufiksem z powyższej listy.

Wybór pierwszej litery prawie nie wpływa na tablicę przyrostków; w szczególności nie wpływa na kolejność pierwszych trzech sufiksów w tablicy sufiksów. Oznacza to, że mamy ciągi log n, dla których tablica sufiksów jest bardzo podobna, ale „poprawny” indeks jest bardzo różny.

Chociaż nie mam żadnego twardego dowodu, to mocno sugeruje mi, że nie masz innego wyboru, jak porównać obroty odpowiadające tym trzem pierwszym trzem indeksom w tablicy dla ich uporządkowania leksykograficznego, co z kolei oznacza, że ​​będziesz potrzebował co najmniej O (n log n) czas na to (ponieważ liczba alternatywnych pierwszych znaków - w naszym przypadku 3 - to log n, a porównanie dwóch łańcuchów zajmuje czas O (n)).

Nie wyklucza to możliwości zastosowania algorytmu O (n). Mam tylko wątpliwości, że tablica sufiksów pomaga w osiągnięciu tego czasu działania.

Najmniejszy obrót to taki, który zaczyna się od sufiksu z tablicy sufiksów. Przyrostki są uporządkowane leksykograficznie. To daje duży start:

• wiesz, że kiedy otrzymasz takie k, że obrót rozpoczynający się od sufiksu k jest mniejszy niż obrót rozpoczynający się od sufiksu k +1, to koniec (zaczynając od pierwszego);
• możesz dokonać porównania „rotacja zaczynająca się od sufiksu k jest mniejsza niż rotacja zaczynająca się od sufiksu k +1” w O (1) poprzez porównanie długości sufiksów i opcjonalnie porównanie jednego znaku z drugim znakiem.

EDYCJA: „jedna postać z drugą postacią” może nie zawsze tak być, może być więcej niż jedną postacią, ale ogólnie nie badasz więcej niż n znaków w całym procesie wyszukiwania, więc jest to O (n).

Krótki dowód: badasz znaki tylko wtedy, gdy sufiks k +1 jest dłuższy niż sufiks k , i zatrzymujesz się i znajdujesz swoje rozwiązanie, jeśli sufiks k +1 jest krótszy niż sufiks k (wtedy wiesz, że sufiks k jest tym, którego szukałeś). Więc badasz znaki tylko podczas wzrostu (długości) sekwencji sufiksów. Ponieważ badasz tylko nadmiar znaków, nie możesz zbadać więcej niż n znaków.

EDYCJA 2: Ten algorytm opiera się na fakcie, że „jeśli w tablicy sufiksów znajdują się dwa sufiksy sąsiadów, a poprzedni jest krótszy niż kolejny, poprzedni jest prefiksem kolejnego”. Jeśli to nie jest prawda, przepraszam.

EDYCJA 3: Nie, nie działa. „abaaa” ma tablicę przyrostków „a”, „aa”, „aaa”, „abaaa”, „baaa”. Ale może ta myśl może ostatecznie doprowadzić do rozwiązania, tylko niektóre szczegóły muszą być bardziej wyrafinowane. Podstawowym pytaniem jest, czy możliwe jest jakoś dokonać wspomnianego porównania dokonanego przez zbadanie mniejszej liczby znaków, więc jest to O (n) całkowicie, co, jak sądzę, może być możliwe. Po prostu nie mogę teraz powiedzieć jak.

Problem:

Leksykograficznie najmniej okrągły podciąg jest problemem znalezienia obrotu struny mającej najniższy porządek leksykograficzny ze wszystkich takich rotacji. Na przykład leksykograficznie minimalny obrót „bbaaccaadd” to „aaccaaddbb”.

Rozwiązanie:

Algorytm czasowy AO (n) zaproponował Jean Pierre Duval (1983).

Biorąc pod uwagę dwa wskaźniki ii j, algorytm Duval porównuje odcinki łańcucha długości j - irozpoczynające się od ii j(zwane „pojedynkiem” ). Jeśli index + j - ijest większa niż długość sznurka, segment jest tworzony przez owijanie.

Na przykład rozważmy s = „baabbaba”, i = 5 i j = 7. Ponieważ j - i = 2, pierwszym segmentem rozpoczynającym się od i = 5 jest „ab”. Drugi segment rozpoczynający się od j = 7 jest konstruowany przez owijanie i jest również „ab”. Jeśli ciągi są leksykograficznie równe, jak w powyższym przykładzie, wybieramy ten zaczynający się od i jako zwycięzca, czyli i = 5.

Powyższy proces powtarza się, aż mamy jednego zwycięzcę. Jeśli łańcuch wejściowy ma nieparzystą długość, ostatni znak wygrywa bez porównania w pierwszej iteracji.

Złożoność czasowa:

Pierwsza iteracja porównuje n ciągów o długości 1 (porównania n / 2), druga iteracja może porównywać n / 2 ciągi długości 2 (porównania n / 2) i tak dalej, aż do i-tej iteracji porównuje 2 ciągi długość n / 2 (porównania n / 2). Ponieważ za każdym razem liczba zwycięzców jest zmniejszana o połowę, wysokość drzewa rekurencji wynosi log (n), co daje nam algorytm O (n log (n)). Dla małych n jest to w przybliżeniu O (n).

Złożoność przestrzeni również wynosi O (n), ponieważ w pierwszej iteracji musimy zapisać n / 2 zwycięzców, drugą iterację n / 4 zwycięzców i tak dalej. (Wikipedia twierdzi, że ten algorytm wykorzystuje stałą przestrzeń, nie rozumiem jak).

Oto implementacja Scala; przejdź do ulubionego języka programowania.

def lexicographicallyMinRotation(s: String): String = {
 @tailrec
 def duel(winners: Seq[Int]): String = {
   if (winners.size == 1) s"${s.slice(winners.head, s.length)}${s.take(winners.head)}"
   else {
     val newWinners: Seq[Int] = winners
       .sliding(2, 2)
       .map {
         case Seq(x, y) =>
           val range = y - x
           Seq(x, y)
             .map { i =>
               val segment = if (s.isDefinedAt(i + range - 1)) s.slice(i, i + range)
               else s"${s.slice(i, s.length)}${s.take(s.length - i)}"
               (i, segment)
             }
             .reduce((a, b) => if (a._2 <= b._2) a else b)
             ._1
         case xs => xs.head
       }
       .toSeq
     duel(newWinners)
   }
 }

 duel(s.indices)
}

Nie widzę nic lepszego niż O (N²).

Jeśli masz listę N liczb całkowitych, możesz wybrać najmniejszą z porównań O (N).

Tutaj masz listę N ciągów o rozmiarze N (ich zbudowanie nic nie kosztuje, ciąg jest w pełni określony przez jego indeks początkowy). Możesz wybrać najmniejszą z porównań O (N). Ale każde porównanie to podstawowe operacje O (N). Zatem złożoność wynosi O (N²).