Рубрики

Приложение Suffix Tree 6 — длинная палиндромная подстрока

По заданной строке найдите самую длинную подстроку — палиндром.

Мы уже обсуждали наивный [O (n 3 )], квадратичный [O (n 2 )] и линейный [O (n)] подходы в наборе 1 , наборе 2 и алгоритме Манахера .
В этой статье мы обсудим другой подход с линейным временем, основанный на дереве суффиксов.
Если заданная строка S, то подход следующий:

  • Перевернуть строку S (скажем, перевернутая строка — R)
  • Получить самую длинную общую подстроку из S и R, учитывая, что LCS в S и R должен быть из одной и той же позиции в S

Вы понимаете, почему мы говорим, что LCS в R и S должны быть из одной и той же позиции в S ?

Давайте посмотрим на следующие примеры:

  • Для S = xababayz и R = zyababax , LCS и LPS оба являются абабами (ЖЕ)
  • Для S = abacdfgdcaba и R = abacdgfdcaba , LCS — это abacd, а LPS — это aba (РАЗНО)
  • Для S = pqrqpabcdfgdcba и R = abcdgfdcbapqrqp LCS и LPS оба являются pqrqp (ЖЕ)
  • Для S = pqqpabcdfghfdcba и R = abcdfhgfdcbapqqp LCS — это abcdf, а LPS — это pqqp ( РАЗНО )

Мы видим, что LCS и LPS не всегда одинаковы. Когда они разные?
Когда в S есть обратная копия непалиндромной подстроки, длина которой равна или больше, чем у LPS в S, тогда LCS и LPS будут отличаться .
Во 2 — м примера выше (S = abacdfgdcaba), для подстроки abacd, существует обратное копирование dcaba в S, который имеет большую длину , чем LPS ABA и так ЛПС и ЛВП различны здесь. Тот же самый сценарий в 4- м примере.

Чтобы справиться с этим сценарием, мы говорим, что LPS в S такой же, как LCS в S и R, учитывая, что LCS в R и S должны быть из одной и той же позиции в S.
Если мы снова посмотрим на 2- й пример, подстрока aba в R происходит из точно такой же позиции в S, что и подстрока aba в S, которая равна нулю (0- й индекс), и поэтому это LPS.

Ограничение позиции:

Мы будем обозначать строку S index как прямой индекс (S i ), а строку R index как обратный индекс (R i ).
Исходя из вышеприведенного рисунка, символ с индексом i (прямой индекс) в строке S длины N будет иметь индекс N-1-i (обратный индекс) в его обращенной строке R.
Если мы возьмем подстроку длины L в строке S с начальным индексом i и конечным индексом j (j = i + L-1), то в ее обращенной строке R обратная подстрока того же самого начнется с индекса N-1- j и закончится индексом N-1-i.
Если есть общая подстрока длины L в индексах S i (прямой индекс) и R i (обратный индекс) в S и R, то они будут приходить из той же позиции в S, если R i = (N — 1) — (S i + L — 1) где N — длина строки.

Таким образом, чтобы найти LPS строки S, мы находим самую длинную общую строку S и R, где обе подстроки удовлетворяют вышеуказанному ограничению, т.е. если подстрока в S имеет индекс S i , то такая же подстрока должна быть в R с индексом (N — 1) — (S i + L — 1). Если это не так, то эта подстрока не является кандидатом в LPS.

Наивные [O (N * M 2 )] и динамическое программирование [O (N * M)] подходы к поиску LCS двух строк уже обсуждались здесь, которые могут быть расширены, чтобы добавить ограничение позиции, чтобы дать LPS данной строки.

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

Находя LCS из двух строк X и Y, мы просто берем самый глубокий узел, помеченный как XY (то есть узел, который имеет суффиксы из обеих строк, поскольку он является дочерним).
Находя LPS строки S, мы снова найдем LCS для S и R с условием, что общая подстрока должна удовлетворять ограничению позиции (общая подстрока должна исходить из той же позиции в S). Чтобы проверить ограничение позиции, нам нужно знать все прямые и обратные индексы на каждом внутреннем узле (то есть индексы суффиксов всех дочерних листов ниже внутренних узлов).

В Обобщенном дереве суффиксов S # R $ подстрока на пути от корня к внутреннему узлу является общей подстрокой, если внутренний узел имеет суффиксы из обеих строк S и R. Индекс общей подстроки в S и R может быть найдено путем просмотра индекса суффикса на соответствующем листовом узле.
Если строка S # имеет длину N, то:

  • Если индекс суффикса листа меньше N, то этот суффикс принадлежит S, и тот же индекс суффикса станет прямым индексом всех узлов-предков
  • Если индекс суффикса листа больше N, то этот суффикс принадлежит R, и обратный индекс для всех узлов-предков будет N-индексом суффикса.

Давайте возьмем строку S = cabbaabb . На рисунке ниже показано обобщенное суффиксное дерево для cabbaabb # bbaabbac $, где мы показали прямые и обратные индексы всех дочерних суффиксов на всех внутренних узлах (кроме корневых).
Прямые индексы в скобках (), а обратные индексы в квадратных скобках [].

На рисунке выше все конечные узлы будут иметь один прямой или обратный индекс в зависимости от того, к какой строке (S или R) они принадлежат. Затем детские прямые или обратные индексы распространяются на родителей.

Посмотрите на рисунок, чтобы понять, что будет прямым или обратным индексом на листе с заданным индексом суффикса. В нижней части рисунка показано, что листы с индексами суффиксов от 0 до 8 получат те же значения (от 0 до 8), что и их форвардный индекс в S, а листы с индексами суффиксов от 9 до 17 получат обратный индекс в R от 0 до 8.

Например, у выделенного внутреннего узла есть два потомка с индексами суффикса 2 и 9. Лист с индексом суффикса 2 находится с позиции 2 в S, поэтому его прямой индекс равен 2 и показан в (). Лист с индексом 9 с суффиксом находится с позиции 0 в R, поэтому обратный индекс равен 0 и показан в []. Эти индексы распространяются на родителя, и у родителя есть один лист с индексом суффикса 14, для которого обратный индекс равен 4. Таким образом, на этом родительском узле прямой индекс равен (2), а обратный индекс равен [0,4]. Точно так же мы должны понимать, как рассчитываются прямые и обратные индексы на всех узлах.

На рисунке выше все внутренние узлы имеют суффиксы из обеих строк S и R, то есть все они представляют общую подстроку на пути от корня к себе. Теперь нам нужно найти самый глубокий узел, удовлетворяющий ограничению позиции. Для этого нам нужно проверить, существует ли прямой индекс S i на узле, тогда должен быть обратный индекс R i со значением (N — 2) — (S i + L — 1), где N — длина строки S # и L — глубина узла (или длина подстроки). Если да, то рассмотрите этот узел как кандидата LPS, иначе проигнорируйте его. На рисунке выше выделен самый глубокий узел, который представляет LPS как bbaabb.

На рисунке не показаны прямые и обратные индексы корневого узла. Поскольку сам корневой узел не представляет какой-либо общей подстроки (в реализации кода также прямые и обратные индексы не будут рассчитываться на корневом узле)

Как реализовать этот метод для поиска LPS? Вот то, что нам нужно:

  • Нам нужно знать прямые и обратные индексы на каждом узле.
  • Для заданного прямого индекса S i на внутреннем узле нам нужно знать, присутствует ли обратный индекс R i = (N — 2) — (S i + L — 1) на том же узле.
  • Следите за самым глубоким внутренним узлом, удовлетворяющим вышеуказанному условию.

Один из способов сделать это выше:
В то время как DFS на дереве суффиксов, мы можем каким-то образом хранить прямые и обратные индексы на каждом узле (хранение поможет избежать повторных обходов по дереву, когда нам нужно знать прямые и обратные индексы на узле). Позже мы можем сделать еще одну DFS для поиска узлов, удовлетворяющих ограничению позиции. Для проверки ограничения позиции нам нужно искать в списке индексов.
Какая структура данных подходит здесь, чтобы сделать все это самым быстрым способом?

  • Если мы будем хранить индексы в массиве, это потребует линейного поиска, что сделает общий подход нелинейным во времени.
  • Если мы храним индексы в дереве (установлено в C ++, TreeSet в Java), мы можем использовать бинарный поиск, но общий подход будет нелинейным во времени.
  • Если мы будем хранить индексы в наборе хеш-функций (unordered_set в C ++, HashSet в Java), это обеспечит постоянный поиск в среднем, и это сделает общий подход линейным по времени. Набор на основе хеш-функции может занимать больше места в зависимости от сохраняемых значений.

Мы будем использовать два unordered_set (один для прямого и другого из обратных индексов) в нашей реализации, добавленный в качестве переменной-члена в структуру SuffixTreeNode.

// Программа на C ++ для реализации Ukkonen's Suffix Tree Construction
// Здесь мы строим обобщенное суффиксное дерево для заданной строки S
// и обратный R, тогда мы находим
// самая длинная палиндромная подстрока из заданной строки S
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <unordered_set>
#define MAX_CHAR 256

using namespace std;

  

struct SuffixTreeNode {

    struct SuffixTreeNode *children[MAX_CHAR];

   

    // указатель на другой узел через суффиксную ссылку

    struct SuffixTreeNode *suffixLink;

   

    / * (начало, конец) интервал определяет ребро, по которому

     узел связан с его родительским узлом. Каждый край будет

     соединить два узла, один родительский и один дочерний, и

     (начало, конец) интервал данного ребра будет сохранен

     в дочернем узле. Допустим, есть два куска A и B

     связаны ребром с индексами (5, 8), то это

     индексы (5, 8) будут храниться в узле B. * /

    int start;

    int *end;

   

    / * для конечных узлов хранит индекс суффикса для

      путь от корня до листа * /

    int suffixIndex;

      

    // Хранить индексы дочерних суффиксов в заданной строке

    unordered_set<int> *forwardIndices;

  

    // Хранить индексы дочерних суффиксов в обратной строке

    unordered_set<int> *reverseIndices;

};

   

typedef struct SuffixTreeNode Node;

  

char text[100]; //Строка ввода

Node *root = NULL; // Указатель на корневой узел

   
/ * lastNewNode будет указывать на вновь созданный внутренний узел,

  ожидание установки суффиксной ссылки, которая может получить

  новая ссылка суффикса (кроме корня) в следующем расширении

  та же фаза. lastNewNode будет установлен в NULL, когда последний

  вновь созданный внутренний узел (если есть) получил его

  сброс суффиксной ссылки на новый внутренний узел, созданный в следующем

  продление той же фазы. * /

Node *lastNewNode = NULL;
Node *activeNode = NULL;

   
/ * activeEdge представлен как символ входной строки

  индекс (не сам символ) * /

int activeEdge = -1;

int activeLength = 0;

   
// Остальная часть суффиксов сообщает, сколько суффиксов еще предстоит
// быть добавленным в дерево

int remainingSuffixCount = 0;

int leafEnd = -1;

int *rootEnd = NULL;

int *splitEnd = NULL;

int size = -1; // Длина входной строки

int size1 = 0; // Размер первой строки

int reverseIndex; // Индекс суффикса в обратной строке

unordered_set<int>::iterator forwardIndex;

   

Node *newNode(int start, int *end)

{

    Node *node =(Node*) malloc(sizeof(Node));

    int i;

    for (i = 0; i < MAX_CHAR; i++)

          node->children[i] = NULL;

   

    / * Для корневого узла СуффиксLink будет установлен в NULL

    Для внутренних узлов СуффиксLink будет установлен как root

    по умолчанию в текущем расширении и может измениться в

    следующее расширение * /

    node->suffixLink = root;

    node->start = start;

    node->end = end;

   

    / * суффиксIndex будет установлен в -1 по умолчанию и

      фактический индекс суффикса будет установлен позже для листьев

      в конце всех фаз * /

    node->suffixIndex = -1;

    node->forwardIndices = new unordered_set<int>;

    node->reverseIndices = new unordered_set<int>;

    return node;

}

   

int edgeLength(Node *n) {

    if(n == root)

        return 0;

    return *(n->end) - (n->start) + 1;

}

   

int walkDown(Node *currNode)

{

    / * изменение activePoint для перехода вниз (APCFWD) с помощью

     Пропустить / считать трюк (трюк 1). Если activeLength больше

     чем текущая длина ребра, установите следующий внутренний узел как

     activeNode и настройте activeEdge и activeLength

     соответственно представлять ту же ActivePoint * /

    if (activeLength >= edgeLength(currNode))

    {

        activeEdge += edgeLength(currNode);

        activeLength -= edgeLength(currNode);

        activeNode = currNode;

        return 1;

    }

    return 0;

}

   

void extendSuffixTree(int pos)

{

    / * Правило расширения 1, оно заботится о расширении всех

    листья, созданные до сих пор в дереве * /

    leafEnd = pos;

   

    / * Увеличивать оставшийсяSuffixCount, указывая, что

    добавлен новый суффикс в список суффиксов

    добавлено в дерево * /

    remainingSuffixCount++;

   

    / * установить lastNewNode в NULL при запуске новой фазы,

     указывает на то, что внутренний узел не ожидает

     это суффикс сброса ссылки в текущей фазе * /

    lastNewNode = NULL;

   

    // Добавить все суффиксы (еще не добавленные) по одному в дереве

    while(remainingSuffixCount > 0) {

   

        if (activeLength == 0)

            activeEdge = pos; // APCFALZ

   

        // Нет исходящего ребра, начинающегося с

        // activeEdge из activeNode

        if (activeNode->children]  == NULL)

        {

            // Расширение правила 2 (создается новый край листа)

            activeNode->children]  =

                                          newNode(pos, &leafEnd);

   

            / * Новый край листа создается в начале строки выше

             от существующего узла (текущий активный узел), и

             если есть какой-либо внутренний узел, ожидающий своего суффикса

             ссылка получить сброс, указать ссылку суффикса из этого последнего

             внутренний узел к текущему активному узлу. Затем установите lastNewNode

             значение NULL, указывающее, что больше нет узлов, ожидающих суффиксную ссылку

             сброс настроек.*/

            if (lastNewNode != NULL)

            {

                lastNewNode->suffixLink = activeNode;

                lastNewNode = NULL;

            }

        }

        // Есть исходящий фронт, начинающийся с activeEdge

        // из activeNode

        else

        {

            // Получить следующий узел в конце начала ребра

            // с activeEdge

            Node *next = activeNode->children] ;

            if (walkDown(next))// Пройдемся

            {

                // Начать со следующего узла (новый активный узел)

                continue;

            }

            / * Правило расширения 3 (текущий символ обрабатывается

              уже на грани) * /

            if (text[next->start + activeLength] == text[pos])

            {

                // APCFER3

                activeLength++;

                / * ОСТАНОВИТЬ всю дальнейшую обработку на этом этапе

                и перейти к следующему этапу * /

                break;

            }

   

            / * Мы будем здесь, когда activePoint будет в середине

              пройденный край и текущий символ

              обрабатывается не на краю (мы падаем

              дерево). В этом случае мы добавляем новый внутренний узел

              и новый край листа выходит из этого нового узла. Эта

              это расширение правила 2, где новый край листа и новый

            внутренний узел создан * /

            splitEnd = (int*) malloc(sizeof(int));

            *splitEnd = next->start + activeLength - 1;

   

            // Новый внутренний узел

            Node *split = newNode(next->start, splitEnd);

            activeNode->children]  = split;

   

            // Новый лист выходит из нового внутреннего узла

            split->children] = newNode(pos, &leafEnd);

            next->start += activeLength;

            split->children]  = next;

   

            / * Мы получили новый внутренний узел здесь. Если есть

              внутренний узел создан в последних расширениях того же

              фаза, которая все еще ждет своего суффикса

              сбросьте, сделайте это сейчас. * /

            if (lastNewNode != NULL)

            {

            / * СуффиксLink из lastNewNode указывает на текущий недавно

              создан внутренний узел * /

                lastNewNode->suffixLink = split;

            }

   

            / * Сделать текущий вновь созданный внутренний узел ожидающим

              для сброса ссылки суффикса (который указывает на root

              в настоящий момент). Если мы сталкиваемся с любым другим внутренним узлом

              (существующий или вновь созданный) в следующем расширении того же

              фаза, когда добавляется новый край листа (т.е. когда

              Расширение Правило 2 применяется к любому следующему расширению

              той же фазы) в этой точке, СуффиксЛинк этого узла

              будет указывать на этот внутренний узел. * /

            lastNewNode = split;

        }

   

        / * В дерево добавлен один суффикс, уменьшающий счетчик

          суффиксы еще предстоит добавить. * /

        remainingSuffixCount--;

        if (activeNode == root && activeLength > 0) // APCFER2C1

        {

            activeLength--;

            activeEdge = pos - remainingSuffixCount + 1;

        }

        else if (activeNode != root) // APCFER2C2

        {

            activeNode = activeNode->suffixLink;

        }

    }

}

   

void print(int i, int j)

{

    int k;

    for (k=i; k<=j && text[k] != '#'; k++)

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

    if(k<=j)

        printf("#");

}

   
// Выводим также дерево суффиксов вместе с настройкой индекса суффикса
// Таким образом, дерево будет напечатано в DFS-стиле
// Каждое ребро вместе с индексом суффикса будет напечатано

void setSuffixIndexByDFS(Node *n, int labelHeight)

{

    if (n == NULL)  return;

   

    if (n->start != -1) // некорневой узел

    {

        // Распечатать метку по краю от родителя к текущему узлу

        // Раскомментируем строку ниже для печати дерева суффиксов

        // print (n-> start, * (n-> end));

    }

    int leaf = 1;

    int i;

    for (i = 0; i < MAX_CHAR; i++)

    {

        if (n->children[i] != NULL)

        {

            // Раскомментируем ниже двух строк для печати индекса суффикса

         // if (leaf == 1 && n-> start! = -1)

           // printf ("[% d] / n", n-> suffixIndex);

   

            // Текущий узел не является листом, так как имеет исходящий

            // края от него.

            leaf = 0;

            setSuffixIndexByDFS(n->children[i], labelHeight +

                                  edgeLength(n->children[i]));

            if(n != root)

            {

                // Добавляем индексы суффикса chldren в parent

                n->forwardIndices->insert(

                    n->children[i]->forwardIndices->begin(), 

                    n->children[i]->forwardIndices->end());

                n->reverseIndices->insert(

                    n->children[i]->reverseIndices->begin(), 

                    n->children[i]->reverseIndices->end());

            }

        }

    }

    if (leaf == 1)

    {

        for(i= n->start; i<= *(n->end); i++)

        {

            if(text[i] == '#')

            {

                n->end = (int*) malloc(sizeof(int));

                *(n->end) = i;

            }

        }

        n->suffixIndex = size - labelHeight;

  

        if(n->suffixIndex < size1) // Суффикс заданной строки

            n->forwardIndices->insert(n->suffixIndex);

        else // Суффикс обратной строки

            n->reverseIndices->insert(n->suffixIndex - size1);

          

        // Раскомментируем ниже строки, чтобы напечатать индекс суффикса

       // printf ("[% d] / n", n-> suffixIndex);

    }

}

   

void freeSuffixTreeByPostOrder(Node *n)

{

    if (n == NULL)

        return;

    int i;

    for (i = 0; i < MAX_CHAR; i++)

    {

        if (n->children[i] != NULL)

        {

            freeSuffixTreeByPostOrder(n->children[i]);

        }

    }

    if (n->suffixIndex == -1)

        free(n->end);

    free(n);

}

   
/ * Построить дерево суффиксов и напечатать края меток вместе с
suffixIndex. СуффиксИндекс для краев листа будет> = 0 и
для не листовых ребер будет -1 * /

void buildSuffixTree()

{

    size = strlen(text);

    int i;

    rootEnd = (int*) malloc(sizeof(int));

    *rootEnd = - 1;

   

    / * Root - это специальный узел с индексами начала и конца, равными -1,

    так как у него нет родителя, откуда ребро приходит к корню * /

    root = newNode(-1, rootEnd);

   

    activeNode = root; // Первый активный узел будет корневым

    for (i=0; i<size; i++)

        extendSuffixTree(i);

    int labelHeight = 0;

    setSuffixIndexByDFS(root, labelHeight);

}

  

void doTraversal(Node *n, int labelHeight, int* maxHeight, 

int* substringStartIndex)

{

    if(n == NULL)

    {

        return;

    }

    int i=0;

    int ret = -1;

    if(n->suffixIndex < 0) // Если это внутренний узел

    {

        for (i = 0; i < MAX_CHAR; i++)

        {

            if(n->children[i] != NULL)

            {

                doTraversal(n->children[i], labelHeight + 

                    edgeLength(n->children[i]), 

                    maxHeight, substringStartIndex);

                  

                if(*maxHeight < labelHeight 

                    && n->forwardIndices->size() > 0 &&

                    n->reverseIndices->size() > 0)

                {

                    for (forwardIndex=n->forwardIndices->begin(); 

                            forwardIndex!=n->forwardIndices->end();

                            ++forwardIndex)

                    {

                        reverseIndex = (size1 - 2) -

                            (*forwardIndex + labelHeight - 1);

                        // Если получен обратный суффикс

                        // ЖЕ позиция в данной строке

                        // Отслеживаем самый глубокий узел

                        if(n->reverseIndices->find(reverseIndex) !=

                            n->reverseIndices->end())

                        {

                            *maxHeight = labelHeight;

                            *substringStartIndex = *(n->end) - 

                                labelHeight + 1;

                            break;

                        }

                    }

                }

            }

        }

    }

}

  

void getLongestPalindromicSubstring()

{

    int maxHeight = 0;

    int substringStartIndex = 0;

    doTraversal(root, 0, &maxHeight, &substringStartIndex);

      

    int k;

    for (k=0; k<maxHeight; k++)

        printf("%c", text[k + substringStartIndex]);

    if(k == 0)

        printf("No palindromic substring");

    else

        printf(", of length: %d",maxHeight);

    printf("\n");

}

   
// программа драйвера для проверки вышеуказанных функций

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

{

    size1 = 9;

    printf("Longest Palindromic Substring in cabbaabb is: ");

    strcpy(text, "cabbaabb#bbaabbac$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 17;

    printf("Longest Palindromic Substring in forgeeksskeegfor is: ");

    strcpy(text, "forgeeksskeegfor#rofgeeksskeegrof$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 6;

    printf("Longest Palindromic Substring in abcde is: ");

    strcpy(text, "abcde#edcba$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 7;

    printf("Longest Palindromic Substring in abcdae is: ");

    strcpy(text, "abcdae#eadcba$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 6;

    printf("Longest Palindromic Substring in abacd is: ");

    strcpy(text, "abacd#dcaba$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 6;

    printf("Longest Palindromic Substring in abcdc is: ");

    strcpy(text, "abcdc#cdcba$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 13;

    printf("Longest Palindromic Substring in abacdfgdcaba is: ");

    strcpy(text, "abacdfgdcaba#abacdgfdcaba$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 15;

    printf("Longest Palindromic Substring in xyabacdfgdcaba is: ");

    strcpy(text, "xyabacdfgdcaba#abacdgfdcabayx$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 9;

    printf("Longest Palindromic Substring in xababayz is: ");

    strcpy(text, "xababayz#zyababax$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    size1 = 6;

    printf("Longest Palindromic Substring in xabax is: ");

    strcpy(text, "xabax#xabax$"); buildSuffixTree();

    getLongestPalindromicSubstring();

    // Освобождаем динамически выделенную память

    freeSuffixTreeByPostOrder(root);

  

    return 0;

}

Выход:

Longest Palindromic Substring in cabbaabb is: bbaabb, of length: 6
Longest Palindromic Substring in forgeeksskeegfor is: geeksskeeg, of length: 10
Longest Palindromic Substring in abcde is: a, of length: 1
Longest Palindromic Substring in abcdae is: a, of length: 1
Longest Palindromic Substring in abacd is: aba, of length: 3
Longest Palindromic Substring in abcdc is: cdc, of length: 3
Longest Palindromic Substring in abacdfgdcaba is: aba, of length: 3
Longest Palindromic Substring in xyabacdfgdcaba is: aba, of length: 3
Longest Palindromic Substring in xababayz is: ababa, of length: 5
Longest Palindromic Substring in xabax is: xabax, of length: 5

Следовать за:
Обнаружить ВСЕ палиндромы в данной строке.
Например, для строки abcddcbefgf все возможные палиндромы: a, b, c, d, e, f, g, dd, fgf, cddc, bcddcb.

Мы опубликовали следующие дополнительные статьи о приложениях дерева суффиксов:

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

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

Приложение Suffix Tree 6 — длинная палиндромная подстрока

0.00 (0%) 0 votes