Приложение Suffix Tree 2 — Поиск по всем паттернам

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

}

int traverseEdge(char *str, int idx, int start, int end)

{

    int k = 0;

    // Обход края с посимвольным соответствием

    for(k=start; k<=end && str[idx] != '\0'; k++, idx++)

    {

        if(text[k] != str[idx])

            return -1;  // мо совпадение

    }

    if(str[idx] == '\0')

        return 1;  // совпадение

    return 0;  // еще символы, которые должны соответствовать

}

int doTraversalToCountLeaf(Node *n)

{

    if(n == NULL)

        return 0;

    if(n->suffixIndex > -1)

    {

        printf("\nFound at position: %d", n->suffixIndex);

        return 1;

    }

    int count = 0;

    int i = 0;

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

    {

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

        {

            count += doTraversalToCountLeaf(n->children[i]);

        }

    }

    return count;

}

int countLeaf(Node *n)

{

    if(n == NULL)

        return 0;

    return doTraversalToCountLeaf(n);

}

int doTraversal(Node *n, char* str, int idx)

{

    if(n == NULL)

    {

        return -1; // не совпадает

    }

    int res = -1;

    // Если узел n не является корневым узлом, то пересекаем ребро

    // от родительского узла n к узлу n.

    if(n->start != -1)

    {

        res = traverseEdge(str, idx, n->start, *(n->end));

        if(res == -1)  //не совпадает

            return -1;

        if(res == 1) //совпадение

        {

            if(n->suffixIndex > -1)

                printf("\nsubstring count: 1 and position: %d",

                               n->suffixIndex);

            else

                printf("\nsubstring count: %d", countLeaf(n));

            return 1;

        }

    }

    // Получить индекс символа для поиска

    idx = idx + edgeLength(n);

    // Если выходит ребро из узла n

    // с текущим символом str [idx], пройти через этот край

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

        return doTraversal(n->children[str[idx]], str, idx);

    else

        return -1;  // не совпадает

}

void checkForSubString(char* str)

{

    int res = doTraversal(root, str, 0);

    if(res == 1)

        printf("\nPattern <%s> is a Substring\n", str);

    else

        printf("\nPattern <%s> is NOT a Substring\n", str);

}

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

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

{

    strcpy(text, "GEEKSFORGEEKS$"); 

    buildSuffixTree();    

    printf("Text: GEEKSFORGEEKS, Pattern to search: GEEKS");

    checkForSubString("GEEKS");

    printf("\n\nText: GEEKSFORGEEKS, Pattern to search: GEEK1");

    checkForSubString("GEEK1");

    printf("\n\nText: GEEKSFORGEEKS, Pattern to search: FOR");

    checkForSubString("FOR");

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

    freeSuffixTreeByPostOrder(root);

    strcpy(text, "AABAACAADAABAAABAA$");

    buildSuffixTree();    

    printf("\n\nText: AABAACAADAABAAABAA, Pattern to search: AABA");

    checkForSubString("AABA");

    printf("\n\nText: AABAACAADAABAAABAA, Pattern to search: AA");

    checkForSubString("AA");

    printf("\n\nText: AABAACAADAABAAABAA, Pattern to search: AAE");

    checkForSubString("AAE");

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

    freeSuffixTreeByPostOrder(root);

    strcpy(text, "AAAAAAAAA$");

    buildSuffixTree();    

    printf("\n\nText: AAAAAAAAA, Pattern to search: AAAA");

    checkForSubString("AAAA");

    printf("\n\nText: AAAAAAAAA, Pattern to search: AA");

    checkForSubString("AA");

    printf("\n\nText: AAAAAAAAA, Pattern to search: A");

    checkForSubString("A");

    printf("\n\nText: AAAAAAAAA, Pattern to search: AB");

    checkForSubString("AB");

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

    freeSuffixTreeByPostOrder(root);

    return 0;

}