Рубрики

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

По текстовой строке найдите Longest Repeated Substring в тексте. Если имеется несколько длинных повторяющихся подстрок, получите любую из них.

Longest Repeated Substring in GEEKSFORGEEKS is: GEEKS
Longest Repeated Substring in AAAAAAAAAA is: AAAAAAAAA
Longest Repeated Substring in ABCDEFG is: No repeated substring
Longest Repeated Substring in ABABABA is: ABABA
Longest Repeated Substring in ATCGATCGA is: ATCGA
Longest Repeated Substring in banana is: ana
Longest Repeated Substring in abcpqrabpqpq is: ab (pq is another LRS here)

Эта проблема может быть решена различными подходами с различными временными и пространственными сложностями. Здесь мы обсудим подход Suffix Tree (3- е приложение Suffix Tree). Другие подходы будут обсуждаться в ближайшее время.

В качестве предварительного условия мы должны знать, как построить дерево суффиксов тем или иным способом.
Здесь мы построим дерево суффиксов, используя алгоритм Укконена, который уже обсуждался ниже:
Построение суффикс-дерева Укконена — часть 1
Построение Суффикса Укконена — Часть 2
Построение Суффикса Укконена — Часть 3
Построение суффикс-дерева Укконена — часть 4
Построение Суффикса Укконена — Часть 5
Построение Суффикса Укконена — Часть 6

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

Это дерево суффиксов для строки «ABABABA $».
В этой строке повторяются следующие подстроки:
A, B, AB, BA, ABA, BAB, ABAB, BABA, ABABA
И самая длинная повторяющаяся подстрока — это ABABA.
В дереве суффиксов один узел не может иметь более одного исходящего ребра, начинающегося с одного и того же символа, и поэтому, если в тексте есть повторяющиеся подстроки, они будут использовать один и тот же путь, и этот путь в дереве суффиксов пройдет через один или несколько внутренние узлы вниз по дереву (ниже точки, где подстрока заканчивается на этом пути).
На рисунке выше мы можем видеть, что

  • Путь с подстрокой «A» имеет три внутренних узла вниз по дереву
  • Путь с подстрокой «AB» имеет два внутренних узла вниз по дереву
  • Путь с подстрокой «ABA» имеет два внутренних узла вниз по дереву
  • Путь с подстрокой «ABAB» имеет один внутренний узел вниз по дереву
  • Путь с подстрокой «ABABA» имеет один внутренний узел вниз по дереву
  • Путь с подстрокой «B» имеет два внутренних узла вниз по дереву
  • Путь с подстрокой «BA» имеет два внутренних узла вниз по дереву
  • Путь с подстрокой «BAB» имеет один внутренний узел вниз по дереву
  • Путь с подстрокой «BABA» имеет один внутренний узел вниз по дереву

Все вышеперечисленные подстроки повторяются.

Подстроки ABABAB, ABABABA, BABAB, BABABA не имеют внутреннего узла в дереве (после точки, где подстрока заканчивается на пути), и поэтому они не повторяются.

Вы видите, как найти самую длинную повторную подстроку?
На рисунке видно, что самая длинная повторяющаяся подстрока заканчивается на внутреннем узле, который находится дальше всего от корня (т. Е. Самый глубокий узел в дереве), потому что длина подстроки — это длина метки пути от корня до этого внутреннего узла.

Таким образом, поиск самой длинной повторяющейся подстроки сводится к нахождению самого глубокого узла в дереве суффиксов, а затем получает метку пути от корня к этому самому глубокому внутреннему узлу.

// 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; // Длина входной строки

   

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; k++)

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

}

   
// Выводим также дерево суффиксов вместе с настройкой индекса суффикса
// Таким образом, дерево будет напечатано в 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)

    {

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

}

  

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

int* substringStartIndex)

{

    if(n == NULL)

    {

        return;

    }

    int i=0;

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

    {

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

        {

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

            {

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

                                edgeLength(n->children[i]), maxHeight,

                                 substringStartIndex);

            }

        }

    }

    else if(n->suffixIndex > -1 && 

                (*maxHeight < labelHeight - edgeLength(n)))

    {

        *maxHeight = labelHeight - edgeLength(n);

        *substringStartIndex = n->suffixIndex;

    }

}

  

void getLongestRepeatedSubstring()

{

    int maxHeight = 0;

    int substringStartIndex = 0;

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

// printf ("maxHeight% d, substringStartIndex% d / n", maxHeight,
// substringStartIndex);

    printf("Longest Repeated Substring in %s is: ", text);

    int k;

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

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

    if(k == 0)

        printf("No repeated substring");

    printf("\n");

}

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

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

{

    strcpy(text, "GEEKSFORGEEKS$"); 

    buildSuffixTree();    

    getLongestRepeatedSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "AAAAAAAAAA$"); 

    buildSuffixTree();    

    getLongestRepeatedSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "ABCDEFG$"); 

    buildSuffixTree();    

    getLongestRepeatedSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "ABABABA$"); 

    buildSuffixTree();    

    getLongestRepeatedSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "ATCGATCGA$"); 

    buildSuffixTree();    

    getLongestRepeatedSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "banana$"); 

    buildSuffixTree();    

    getLongestRepeatedSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "abcpqrabpqpq$"); 

    buildSuffixTree();    

    getLongestRepeatedSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    strcpy(text, "pqrpqpqabab$"); 

    buildSuffixTree();    

    getLongestRepeatedSubstring();

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

    freeSuffixTreeByPostOrder(root);

  

    return 0;

}

Выход:

Longest Repeated Substring in GEEKSFORGEEKS$ is: GEEKS
Longest Repeated Substring in AAAAAAAAAA$ is: AAAAAAAAA
Longest Repeated Substring in ABCDEFG$ is: No repeated substring
Longest Repeated Substring in ABABABA$ is: ABABA
Longest Repeated Substring in ATCGATCGA$ is: ATCGA
Longest Repeated Substring in banana$ is: ana
Longest Repeated Substring in abcpqrabpqpq$ is: ab
Longest Repeated Substring in pqrpqpqabab$ is: ab

В случае нескольких LRS (как мы видим в последних двух тестовых примерах), эта реализация печатает LRS, который находится на 1- м лексикографическом уровне.

Построение дерева суффиксов Укконена занимает O (N) время и пространство, чтобы построить дерево суффиксов для строки длины N, и после этого нахождение самого глубокого узла займет O (N).
Так что это линейно во времени и пространстве.

Последующие вопросы:

  1. Найти все повторяющиеся подстроки в данном тексте
  2. Найти все уникальные подстроки в данном тексте
  3. Найти все повторяющиеся подстроки заданной длины
  4. Найти все уникальные подстроки заданной длины
  5. В случае нескольких LRS в тексте найдите тот, который встречается чаще всего

Все эти проблемы могут быть решены за линейное время с небольшими изменениями в приведенной выше реализации.

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

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

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

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

0.00 (0%) 0 votes