Суффикс Массив | Комплект 1 (Введение)

// Наивный алгоритм построения суффиксного массива заданного текста
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

  
// Структура для хранения информации суффикса

struct suffix

{

    int index;

    char *suff;

};

  
// Функция сравнения, используемая sort () для сравнения двух суффиксов

int cmp(struct suffix a, struct suffix b)

{

    return strcmp(a.suff, b.suff) < 0? 1 : 0;

}

  
// Это основная функция, которая принимает строку 'txt' размера n как
// аргумент, строит и возвращает массив суффиксов для данной строки

int *buildSuffixArray(char *txt, int n)

{

    // Структура для хранения суффиксов и их индексов

    struct suffix suffixes[n];

    // Сохраняем суффиксы и их индексы в массиве структур.

    // Структура нужна для сортировки суффиксов по алфавиту

    // и поддерживаем свои старые индексы при сортировке

    for (int i = 0; i < n; i++)

    {

        suffixes[i].index = i;

        suffixes[i].suff = (txt+i);

    }

    // Сортировка суффиксов с использованием функции сравнения

    // определено выше.

    sort(suffixes, suffixes+n, cmp);

    // Сохраняем индексы всех отсортированных суффиксов в массиве суффиксов

    int *suffixArr = new int[n];

    for (int i = 0; i < n; i++)

        suffixArr[i] = suffixes[i].index;

    // Возвращаем массив суффиксов

    return  suffixArr;

}

  
// Вспомогательная функция для печати массива заданного размера

void printArr(int arr[], int n)

{

    for(int i = 0; i < n; i++)

        cout << arr[i] << " ";

    cout << endl;

}

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

int main()

{

    char txt[] = "banana";

    int n = strlen(txt);

    int *suffixArr = buildSuffixArray(txt,  n);

    cout << "Following is suffix array for " << txt << endl;

    printArr(suffixArr, n);

    return 0;

}

// Этот код содержит только search () и main. Чтобы сделать его полным ходом
// приведенный выше код или см. https://ide.geeksforgeeks.org/oY7OkD

  
// Функция поиска на основе суффиксного массива для поиска по заданному шаблону
// 'pat' в данном тексте 'txt' с использованием суффиксного массива suffArr []

void search(char *pat, char *txt, int *suffArr, int n)

{

    int m = strlen(pat);  // получаем длину шаблона, необходимую для strncmp ()

    // Выполняем простой бинарный поиск патча в txt, используя

    // встроенный массив суффиксов

    int l = 0, r = n-1;  // Инициализируем левый и правый индексы

    while (l <= r)

    {

        // Посмотрим, является ли 'pat' префиксом среднего суффикса в массиве суффиксов

        int mid = l + (r - l)/2;

        int res = strncmp(pat, txt+suffArr[mid], m);

        // Если совпадение найдено в середине, вывести его и вернуть

        if (res == 0)

        {

            cout << "Pattern found at index " << suffArr[mid];

            return;

        }

        // Переместимся в левую половину, если шаблон по алфавиту меньше

        // средний суффикс

        if (res < 0) r = mid - 1;

        // Иначе переместимся на правую половину

        else l = mid + 1;

    }

    // Мы достигаем здесь, если оператор возврата в цикле не выполняется

    cout << "Pattern not found";

}

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

int main()

{

    char txt[] = "banana";  // текст

    char pat[] = "nan";   // шаблон для поиска в тексте

    // Построить массив суффиксов

    int n = strlen(txt);

    int *suffArr = buildSuffixArray(txt, n);

    // поиск патча в txt с использованием встроенного массива суффиксов

    search(pat, txt, suffArr, n);

    return 0;

}