Рубрики

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

В алгоритме Manacher Part 1 и Part 2 мы рассмотрели некоторые основы, разбирались в массиве длины LPS и в том, как эффективно рассчитать его на основе четырех случаев. В третьей части мы реализовали то же самое.
Здесь мы еще раз рассмотрим четыре случая и попытаемся увидеть их по-другому и реализовать то же самое.
Все четыре случая зависят от значения длины LPS в currentLeftPosition (L [iMirror]) и значения (centerRightPosition — currentRightPosition), т.е. (R — i). Эти две информации известны ранее, что помогает нам повторно использовать предыдущую доступную информацию и избегать ненужного сравнения символов.

Если мы посмотрим на всех четырех случаях, мы увидим , что мы 1й набор минимум L [iMirror] и Ri в L [я] , а затем мы пытаемся расширить палиндром в зависимости от того , когда он может расширяться.

Приведенное выше наблюдение может выглядеть более интуитивно понятным, более простым для понимания и реализации, учитывая, что каждый понимает массив длины LPS, положение, индекс, свойство симметрии и т. Д.

C / C ++

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

  

char text[100];

int min(int a, int b)

{

    int res = a;

    if(b < a)

        res = b;

    return res;

}

  

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 maxLPSLength = 0;

    int maxLPSCenterPosition = 0;

    int start = -1;

    int end = -1;

    int diff = -1;

      

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

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

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

    {

        // получаем currentLeftPosition iMirror для 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 на ОДИН без

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

        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("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;

}

Джава

// Java-программа для реализации алгоритма Manacher

import java.util.*;

  

class GFG 

{

    static void findLongestPalindromicString(String text) 

    {

        int N = text.length();

        if (N == 0)

            return;

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

        int[] L = new int[N + 1]; // 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 maxLPSLength = 0;

        int maxLPSCenterPosition = 0;

        int start = -1;

        int end = -1;

        int diff = -1;

  

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

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

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

        {

  

            // получаем currentLeftPosition iMirror

            // для currentRightPosition i

            iMirror = 2 * C - i;

            L[i] = 0;

            diff = R - i;

  

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

            // centerRightPosition R

            if (diff > 0)

                L[i] = Math.min(L[iMirror], diff);

  

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

            // currentRightPosition i. Здесь для нечетных позиций,

            // сравниваем символы и если совпадают то

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

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

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

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

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

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

                          text.charAt((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;

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

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

            System.out.print(text.charAt(i));

        System.out.println();

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        String text = "babcbabcbaccba";

        findLongestPalindromicString(text);

  

        text = "abaaba";

        findLongestPalindromicString(text);

  

        text = "abababa";

        findLongestPalindromicString(text);

  

        text = "abcbabcbabcba";

        findLongestPalindromicString(text);

  

        text = "forgeeksskeegfor";

        findLongestPalindromicString(text);

  

        text = "caba";

        findLongestPalindromicString(text);

  

        text = "abacdfgdcaba";

        findLongestPalindromicString(text);

  

        text = "abacdfgdcabba";

        findLongestPalindromicString(text);

  

        text = "abacdedcaba";

        findLongestPalindromicString(text);

    }

}

  
// Этот код предоставлен
// sanjeev2552

питон

# Программа 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

C #

// C # программа для реализации алгоритма Manacher

using System;

  

class GFG 

{

    static void findLongestPalindromicString(String text) 

    {

        int N = text.Length;

        if (N == 0)

            return;

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

        int[] L = new int[N + 1]; // 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 maxLPSLength = 0;

        int maxLPSCenterPosition = 0;

        int start = -1;

        int end = -1;

        int diff = -1;

  

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

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

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

        {

  

            // получаем currentLeftPosition iMirror

            // для currentRightPosition i

            iMirror = 2 * C - i;

            L[i] = 0;

            diff = R - i;

  

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

            // centerRightPosition R

            if (diff > 0)

                L[i] = Math.Min(L[iMirror], diff);

  

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

            // currentRightPosition i. Здесь для нечетных позиций,

            // сравниваем символы и если совпадают то

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

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

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

            while (((i + L[i]) + 1 < 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;

        Console.Write("LPS of string is {0} : ", text);

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

            Console.Write(text[i]);

        Console.WriteLine();

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        String text = "babcbabcbaccba";

        findLongestPalindromicString(text);

  

        text = "abaaba";

        findLongestPalindromicString(text);

  

        text = "abababa";

        findLongestPalindromicString(text);

  

        text = "abcbabcbabcba";

        findLongestPalindromicString(text);

  

        text = "forgeeksskeegfor";

        findLongestPalindromicString(text);

  

        text = "caba";

        findLongestPalindromicString(text);

  

        text = "abacdfgdcaba";

        findLongestPalindromicString(text);

  

        text = "abacdfgdcabba";

        findLongestPalindromicString(text);

  

        text = "abacdedcaba";

        findLongestPalindromicString(text);

    }

}

  
// Этот код предоставлен PrinciRaj1992

Выход:

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

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

Чтобы избежать этой разной обработки четных и нечетных позиций, нам необходимо сделать четные позиции также для представления какого-либо символа (фактически все четные позиции должны представлять собой ОДИН ИСТОЧНИК, поскольку они ДОЛЖНЫ совпадать при сравнении символов). Один из способов сделать это — установить какой-либо символ на всех четных позициях, изменив заданную строку или создав новую копию заданной строки. Например, если входной строкой является «abcb», новая строка должна быть «# a # b # c # b #», если мы добавим # в качестве уникального символа на четных позициях.

Обсуждаемые два подхода уже могут быть модифицированы для работы с модифицированной строкой, где не требуется разная обработка четных и нечетных позиций.

Мы также можем добавить два РАЗНЫХ символа (еще не использованных нигде в строке в четных и нечетных позициях) в начале и в конце строки в качестве часовых, чтобы избежать проверки границ. С этими изменениями строка «abcb» будет выглядеть как «^ # a # b # c # b # $», где ^ и $ — стражи.
Эта реализация может выглядеть чище со стоимостью большего количества памяти.

Мы не реализуем их здесь, поскольку это простое изменение в данных реализациях.

Реализация подхода, обсужденного в текущей статье на модифицированной строке, может быть найдена в Longest Palindromic Substring Part II и в Java-переводе того же самого Принстона.

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

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

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

0.00 (0%) 0 votes