Рубрики

Алгоритм Манахера — длинная палиндромная подстрока линейного времени — часть 3

В алгоритме Manacher Part 1 и Part 2 мы рассмотрели некоторые основы, разбирались в массиве длины LPS и в том, как эффективно рассчитать его на основе четырех случаев. Здесь мы будем реализовывать то же самое.

Мы видели, что в случае 1 и 2 не требуется нового сравнения символов. В случае 3 и 4 необходимо новое сравнение.
На следующем рисунке

Если вообще нужно сравнение, мы будем сравнивать только реальные символы, которые находятся в «нечетных» позициях, таких как 1, 3, 5, 7 и т. Д.
Четные позиции не представляют символ в строке, поэтому сравнение четных позиций не выполняется.
Если два символа в разных нечетных позициях совпадают, то они увеличат длину LPS на 2.

Есть много способов реализовать это в зависимости от того, как обрабатываются четные и нечетные позиции. Одним из способов было бы создать новую строку 1- го числа, где мы вставляем какой-то уникальный символ (скажем, #, $ и т. Д.) Во все четные позиции, а затем запускаем алгоритм для этого (чтобы избежать другого способа обработки четных и нечетных позиций). Другим способом может быть работа с данной строкой, но здесь четные и нечетные позиции должны обрабатываться соответствующим образом.

Здесь мы начнем с данной строки. Когда есть необходимость расширения и сравнения символов, мы будем расширяться в левую и правую позиции один за другим. Когда будет найдена нечетная позиция, сравнение будет выполнено, а длина LPS будет увеличена на ОДИН. Когда четная позиция найдена, сравнение не выполняется, и длина LPS будет увеличена на ОДНУ (таким образом, одна нечетная и одна четная позиции на левой и правой стороне увеличат длину LPS на ДВА).

C / C ++

// AC-программа для реализации алгоритма Manacher
#include <stdio.h>
#include <string.h>

  

char text[100];

void findLongestPalindromicString()

{

    int N = strlen(text);

    if(N == 0)

        return;

    N = 2*N + 1; // Счет позиции

    int L[N]; // LPS Length Array

    L[0] = 0;

    L[1] = 1;

    int C = 1; // centerPosition

    int R = 2; // centerRightPosition

    int i = 0; // currentRightPosition

    int iMirror; // currentLeftPosition

    int expand = -1;

    int diff = -1;

    int maxLPSLength = 0;

    int maxLPSCenterPosition = 0;

    int start = -1;

    int end = -1;

      

    // Раскомментируем его для печати массива LPS Length

    // printf ("% d% d", L [0], L [1]);

    for (i = 2; i < N; i++) 

    {

        // получаем currentLeftPosition iMirror для currentRightPosition i

        iMirror  = 2*C-i;

        // Сбросить расширение - означает, что расширение не требуется

        expand = 0;

        diff = R - i;

        // Если currentRightPosition i находится в centerRightPosition R

        if(diff > 0) 

        {

            if(L[iMirror] < diff) // Дело 1

                L[i] = L[iMirror];

            else if(L[iMirror] == diff && i == N-1) // Случай 2

                L[i] = L[iMirror];

            else if(L[iMirror] == diff && i < N-1)  // Случай 3

            {

                    L[i] = L[iMirror];

                    expand = 1;  // требуется расширение

            }

            else if(L[iMirror] > diff)  // Случай 4

            {

                L[i] = diff;

                expand = 1;  // требуется расширение

            }

        }

        else

        {

            L[i] = 0;

            expand = 1;  // требуется расширение

        }

          

        if (expand == 1)

        {

            // Попытка расширить палиндром с центром в currentRightPosition i

            // Здесь для нечетных позиций мы сравниваем символы и

            // если совпадение, то увеличиваем длину LPS на ОДИН

            // Если четная позиция, мы просто увеличиваем LPS на ОДИН без

            // любое сравнение символов

            while (((i + L[i]) < N && (i - L[i]) > 0) && 

                ( ((i + L[i] + 1) % 2 == 0) || 

                (text[(i + L[i] + 1)/2] == text[(i-L[i]-1)/2] )))

            {

                L[i]++;

            }

        }

  

        if(L[i] > maxLPSLength)  // Отслеживаем maxLPSLength

        {

            maxLPSLength = L[i];

            maxLPSCenterPosition = i;

        }

  

        // Если палиндром центрирован на currentRightPosition i

        // расширить за пределы centerRightPosition R,

        // настраиваем centerPosition C на основе расширенного палиндрома.

        if (i + L[i] > R) 

        {

            C = i;

            R = i + L[i];

        }

        // Раскомментируем его для печати массива LPS Length

        // printf ("% d", L [i]);

    }

    // Е ( "/ п");

    start = (maxLPSCenterPosition - maxLPSLength)/2;

    end = start + maxLPSLength - 1;

    // printf («начало:% d конец:% d / n», начало, конец);

    printf("LPS of string is %s : ", text);

    for(i=start; i<=end; i++)

        printf("%c", text[i]);

    printf("\n");

}

  

  

int main(int argc, char *argv[])

{

  

    strcpy(text, "babcbabcbaccba");

    findLongestPalindromicString();

  

    strcpy(text, "abaaba");

    findLongestPalindromicString();

  

    strcpy(text, "abababa");

    findLongestPalindromicString();

  

    strcpy(text, "abcbabcbabcba");

    findLongestPalindromicString();

  

    strcpy(text, "forgeeksskeegfor");

    findLongestPalindromicString();

  

    strcpy(text, "caba");

    findLongestPalindromicString();

  

    strcpy(text, "abacdfgdcaba");

    findLongestPalindromicString();

  

    strcpy(text, "abacdfgdcabba");

    findLongestPalindromicString();

  

    strcpy(text, "abacdedcaba");

    findLongestPalindromicString();

  

    return 0;

}

питон

# Программа Python для реализации алгоритма Manacher

   

def findLongestPalindromicString(text):

    N = len(text)

    if N == 0:

        return

    N = 2*N+1    Количество позиций

    L = [0] * N

    L[0] = 0

    L[1] = 1

    C = 1     # centerPosition

    R = 2     # centerRightPosition

    i = 0    # currentRightPosition

    iMirror = 0     # currentLeftPosition

    maxLPSLength = 0

    maxLPSCenterPosition = 0

    start = -1

    end = -1

    diff = -1

   

    # Раскомментируйте его для печати массива LPS Length

    # printf ("% d% d", L [0], L [1]);

    for i in xrange(2,N):

       

        # get currentLeftPosition iMirror for currentRightPosition i

        iMirror = 2*C-i

        L[i] = 0

        diff = R - i

        # Если currentRightPosition i находится в пределах centerRightPosition R

        if diff > 0:

            L[i] = min(L[iMirror], diff)

   

        # Попытка расширить палиндром с центром в currentRightPosition i

        # Здесь для нечетных позиций, мы сравниваем символы и

        # если совпадение, то увеличить длину LPS на ОДИН

        # Если чётная позиция, мы просто увеличиваем LPS на ОДИН без

        # любое сравнение символов

        try:

            while ((i+L[i]) < N and (i-L[i]) > 0) and \

                    (((i+L[i]+1) % 2 == 0) or \

                    (text[(i+L[i]+1)/2] == text[(i-L[i]-1)/2])):

                L[i]+=1

        except Exception as e:

            pass

   

        if L[i] > maxLPSLength:        # Track maxLPSLength

            maxLPSLength = L[i]

            maxLPSCenterPosition = i

   

        # Если палиндром центрирован на currentRightPosition i

        # расширить за пределы centerRightPosition R,

        # настройка centerPosition C на основе расширенного палиндрома.

        if i + L[i] > R:

            C = i

            R = i + L[i]

   

    # Раскомментируйте его для печати массива LPS Length

    # printf ("% d", L [i]);

    start = (maxLPSCenterPosition - maxLPSLength) / 2

    end = start + maxLPSLength - 1

    print "LPS of string is " + text + " : ",

    print text[start:end+1],

    print "\n",

   
# Драйверная программа

text1 = "babcbabcbaccba"

findLongestPalindromicString(text1)

   

text2 = "abaaba"

findLongestPalindromicString(text2)

   

text3 = "abababa"

findLongestPalindromicString(text3)

   

text4 = "abcbabcbabcba"

findLongestPalindromicString(text4)

   

text5 = "forgeeksskeegfor"

findLongestPalindromicString(text5)

   

text6 = "caba"

findLongestPalindromicString(text6)

   

text7 = "abacdfgdcaba"

findLongestPalindromicString(text7)

   

text8 = "abacdfgdcabba"

findLongestPalindromicString(text8)

   

text9 = "abacdedcaba"

findLongestPalindromicString(text9)

   
# Этот код предоставлен BHAVYA JAIN

Выход:

LPS of string is babcbabcbaccba : abcbabcba
LPS of string is abaaba : abaaba
LPS of string is abababa : abababa
LPS of string is abcbabcbabcba : abcbabcbabcba
LPS of string is forgeeksskeegfor : geeksskeeg
LPS of string is caba : aba
LPS of string is abacdfgdcaba : aba
LPS of string is abacdfgdcabba : abba
LPS of string is abacdedcaba : abacdedcaba

Это реализация, основанная на четырех случаях, рассмотренных в части 2 . В части 4 мы обсудили другой взгляд на эти четыре случая и несколько других подходов.

Эта статья предоставлена Анураг Сингх . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм Манахера — длинная палиндромная подстрока линейного времени — часть 3

0.00 (0%) 0 votes