Лексикографски минимална ротација ниске

У рачунарству, лексикографски минимална ротација ниске, то јест лексикографски најмања кружна подниска представља проблем проналажења такве ротације дате ниске да је та ротација лексикографски најмања међу свим ротацијама те ниске. На пример, лексикографски минимална ротација ниске „ббааццаадд“ би била „ааццааддбб“. Могуће је да одређена ниска има више ротација које су лексикографски минималне, међутим за већину примена то није битно зато што те ротације морају бити међусобно еквивалентне. Проналазак лексикографски минималне ротације ниске има примену за нормализацију ниски. Ако ниске које се посматрају представљају изоморфне структуре као што су на пример графови, ова врста нормализације ниски омогућава једноставну проверу једнакости. Да би се избегло коришћене модуларне аритметике при рачунању индекса у нисци, често се користи трик да се ниска надовеже на саму себе.

Алгоритми

Наивни алгоритам

Код наивног алгоритма итерира се кроз све узастопне ротације ниске, при чему се памти и ажурира лексикографски најмања ротација на коју се до сада наишло. За ниску дужине н, временска сложеност овог алгоритма у најгорем случају износи O(n²).

Бутов алгоритам

Ефикасан алгоритам који решава овај проблем је изнео Бут (1980). Алгоритам користи модификовану функцију за претпроцесирање ниске из КМП алгоритма. Функција неуспеха се за ниску рачуна на уобичајен начин, међутим ниска се ротира током израчунавања па се за неке индексе ниске рачунања врше више одједном. Када су сви индекси функције неуспеха успешно израчунати и када нема потребе за поновном ротацијом ниске, познат је индекс где почиње лексикографски најмања ротација ниске и тај индекс се једноставно враћа. Коректност алгоритма није сасвим лако разумети, али се сам алгоритам једноставно имплементира.

def LCS(S):
    n = len(S)
    S += S      # Nadovezivanje niski da bi se izbegla modularna aritmetika
    f = [-1 for c in S]     # Funkcija neuspeha
    k = 0       # Indeks početka leksikografski najmanje rotacije pronađene do sada
    for j in range(1, 2*n):
        i = f[j-k-1]
        while i != -1 and S[j] != S[k+i+1]:
            if S[j] < S[k+i+1]:
                k = j-i-1
            i = f[i]
        if i == -1 and S[j] != S[k+i+1]:
            if S[j] < S[k+i+1]:
                k = j
            f[j-k] = -1
        else:
            f[j-k] = i+1
    return k

Занимљиво је да се уклањањем свих линија кода које модификују вредност променљиве k добија оригинална претпроцесирајућа функција која се користи у Кнут-Морис-Прат алгоритму, зато што ће променљива k (која представља ротацију) остати нула. Временска сложеност Бутовог алгоритма је O(n), при чему је n дужина ниске. Алгоритам ће извршити највише 3n поређења у најгорем случају, и користи O(n) додатног меморијског простора за чување табеле функције неуспеха.

Шајлоков алгоритам брзе канонизације

Шајлок (1981) је предложио алгоритам који има боље перформансе од Бутовог алгоритма. Он је приметио да ако постоји q лексикографски минималних еквивалентних ротација ниске дужине n, тада се оригинална ниска мора састојати од q једнаких подниски дужине d=n/q. Предложени алгоритам користи само n + d/2 поређења и константно додатне меморије.

Алгоритам има две фазе. Прва фаза служи за проналажење и одбацивање индекса ниске који засигурно нису места где лексикографски минимална ротација ниске почиње. Друга фаза представља проналажење индекса почетка лексикографски минималне ротације ниске међу преосталим индексима.

Дувалов алгоритам Линдон факторизације

Дувал (1983) је такође предложио ефикасан алгоритам који се базира на факторизацији ниске у своје компоненте Линдонове речи, и извршава се у линеарном времену и користи константно додатне меморије.

Варијанте

Шајлок (1979) је преложио ефикасан алгоритам за поређење две кружне ниске на једнакост без потребе за њиховом нормализацијом. Овај алгоритам је нашао примену у брзом генерисању одређених хемијских структура без њиховог понављања.

Види још

• Линдонова реч
• Кнут-Морис-Прат алгоритам