Рубрики

Приложение суффиксного дерева 5 — самая длинная общая подстрока

Поиск по шаблону, Продвинутые Структуры данных

Если даны две строки X и Y, найдите самую длинную общую подстроку X и Y.

Наивный подход [O (N * M 2 )] и динамическое программирование [O (N * M)] уже обсуждались здесь .
В этой статье мы обсудим линейный временной подход для поиска LCS с использованием дерева суффиксов (Приложение 5- го дерева суффиксов).
Здесь мы построим обобщенное суффиксное дерево для двух строк X и Y, как уже обсуждалось в:
Обобщенное дерево суффиксов 1

Давайте возьмем тот же пример (X = xabxa и Y = babxba), который мы видели в Обобщенном дереве суффиксов 1 .
Мы построили следующее дерево суффиксов для X и Y:

Это обобщенное дерево суффиксов для xabxa # babxba $
Выше листы с индексами суффиксов в [0,4] являются суффиксами строки xabxa, а листы с индексами суффиксов в [6,11] — суффиксами строки babxa. Почему ??
Поскольку в каскадной строке xabxa # babxba $ индекс строки xabxa равен 0, а ее длина равна 5, поэтому индексы ее суффиксов будут 0, 1, 2, 3 и 4. Аналогичным образом индекс строки babxba равен 6, а его длина равна 6. , поэтому индексы его суффиксов будут 6, 7, 8, 9, 10 и 11.

При этом мы можем видеть, что на приведенном выше рисунке дерева обобщенных суффиксов есть некоторые внутренние узлы, имеющие листья под ним от

  • обе строки X и Y (т. е. есть по крайней мере один лист с индексом суффикса в [0,4] и один лист с индексом суффикса в [6, 11]
  • только строка X (т.е. все листовые узлы имеют индексы суффикса в [0,4])
  • только строка Y (т.е. все конечные узлы имеют индексы суффиксов в [6,11])

На следующем рисунке показаны внутренние узлы, помеченные как «XY», «X» или «Y» в зависимости от того, к какой строке принадлежат листья, которые они имеют под собой.

Что означают эти маркировки «XY», «X» или «Y»?
Метка пути от корня до внутреннего узла дает подстроку X или Y или обоих.
Для узла, помеченного как XY, подстрока от корня до этого узла принадлежит обеим строкам X и Y.
Для узла, помеченного как X, подстрока от корня до этого узла принадлежит только строке X.
Для узла, помеченного как Y, подстрока от корня до этого узла принадлежит только строке Y.

Посмотрев на рисунок выше, вы можете увидеть, как получить LCS из X и Y?
К настоящему времени должно быть ясно, что как получить общие подстроки X и Y хотя бы.
Если мы пройдем путь от корня до узлов, помеченных как XY, мы получим общую подстроку X и Y.

Теперь нам нужно найти самую длинную из всех распространенных подстрок.
Вы можете подумать, как получить LCS сейчас? Вспомните, как мы получили Longest Repeated Substring в данной строке, используя дерево суффиксов.
Метка пути от корня до самого глубокого узла, отмеченного как XY, даст LCS для X и Y. Самый глубокий узел выделен на рисунке выше, а метка пути «abx» от корня до этого узла — это LCS для X и Y.

// AC-программа для реализации Ukkonen's Suffix Tree Construction
// Здесь мы строим обобщенное суффиксное дерево для двух строк
// И затем мы находим самую длинную общую подстроку из двух входных строк
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_CHAR 256

   

struct SuffixTreeNode {

    struct SuffixTreeNode *children[MAX_CHAR];

   

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

    struct SuffixTreeNode *suffixLink;

   

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

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

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

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

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

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

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

    int start;

    int *end;

   

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

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

    int suffixIndex;

};

   

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; // Размер первой строки

   

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;

    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])

            {

                // Если недавно созданный узел ожидает его

                // суффиксная ссылка, которую нужно установить, затем установить суффиксную ссылку

                // этого ожидающего узла к текущему активному узлу

                if(lastNewNode != NULL && activeNode != root)

                {

                    lastNewNode->suffixLink = activeNode;

                    lastNewNode = NULL;

                }

  

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

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

       // 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);

}

  

int 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)

            {

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

                    edgeLength(n->children[i]), 

                    maxHeight, substringStartIndex);

                  

                if(n->suffixIndex == -1)

                    n->suffixIndex = ret;

                else if((n->suffixIndex == -2 && ret == -3) ||

                    (n->suffixIndex == -3 && ret == -2) || 

                    n->suffixIndex == -4)

                {

                    n->suffixIndex = -4;// Отметить узел как XY

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

                    if(*maxHeight < labelHeight)

                    {

                        *maxHeight = labelHeight;

                        *substringStartIndex = *(n->end) - 

                            labelHeight + 1;

                    }

                }

            }

        }

    }

    else if(n->suffixIndex > -1 && n->suffixIndex < size1)// суффикс X

        return -2;// Пометить узел как X

    else if(n->suffixIndex >= size1)// суффикс Y

        return -3;// Пометить узел как Y

    return n->suffixIndex;

}

  

void getLongestCommonSubstring()

{

    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 common substring");

    else

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

    printf("\n");

}

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

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

{

    size1 = 7;

    printf("Longest Common Substring in xabxac and abcabxabcd is: ");

    strcpy(text, "xabxac#abcabxabcd$"); buildSuffixTree();

    getLongestCommonSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    size1 = 10;

    printf("Longest Common Substring in xabxaabxa and babxba is: ");

    strcpy(text, "xabxaabxa#babxba$"); buildSuffixTree();

    getLongestCommonSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    size1 = 14;

    printf("Longest Common Substring in GeeksforGeeks and GeeksQuiz is: ");

    strcpy(text, "GeeksforGeeks#GeeksQuiz$"); buildSuffixTree();

    getLongestCommonSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    size1 = 26;

    printf("Longest Common Substring in OldSite:GeeksforGeeks.org");

    printf(" and NewSite:GeeksQuiz.com is: ");

    strcpy(text, "OldSite:GeeksforGeeks.org#NewSite:GeeksQuiz.com$");

    buildSuffixTree();

    getLongestCommonSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    size1 = 6;

    printf("Longest Common Substring in abcde and fghie is: ");

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

    getLongestCommonSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    size1 = 6;

    printf("Longest Common Substring in pqrst and uvwxyz is: ");

    strcpy(text, "pqrst#uvwxyz$"); buildSuffixTree();

    getLongestCommonSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    return 0;

}

Выход:

Longest Common Substring in xabxac and abcabxabcd is: abxa, of length: 4
Longest Common Substring in xabxaabxa and babxba is: abx, of length: 3
Longest Common Substring in GeeksforGeeks and GeeksQuiz is: Geeks, of length: 5
Longest Common Substring in OldSite:GeeksforGeeks.org and 
NewSite:GeeksQuiz.com is: Site:Geeks, of length: 10
Longest Common Substring in abcde and fghie is: e, of length: 1
Longest Common Substring in pqrst and uvwxyz is: No common substring

Если две строки имеют размер M и N, то для построения Обобщенного суффиксного дерева требуется O (M + N), а поиск LCS представляет собой DFS на дереве, который снова равен O (M + N).
Таким образом, общая сложность линейна во времени и пространстве.

Следовать за:

  1. Учитывая шаблон, проверьте, является ли это подстрокой X или Y или обоих. Если это подстрока, найдите все ее вхождения, а также к какой строке (X или Y или обе) она принадлежит.
  2. Расширить реализацию, чтобы найти LCS из более чем двух строк
  3. Решить задачу 1 для более чем двух строк
  4. По заданной строке найдите ее длинную палиндромную подстроку

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

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

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

Приложение суффиксного дерева 5 — самая длинная общая подстрока

0.00 (0%) 0 votes