Вывести K-й символ в отсортированных составных подстроках строки

// C / C ++ программа для печати K-го символа
// в отсортированных составных подстроках
#include <bits/stdc++.h>

using namespace std;

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

struct suffix

{

    int index;  // Для сохранения исходного индекса

    int rank[2]; // Для сохранения рангов и рядом

                 // ранг пары

};

  
// Функция сравнения, используемая sort () для сравнения
// два суффикса. Сравнивает две пары, возвращает 1, если
// первая пара меньше

int cmp(struct suffix a, struct suffix b)

{

    return (a.rank[0] == b.rank[0])?

           (a.rank[1] < b.rank[1] ?1: 0):

           (a.rank[0] < b.rank[0] ?1: 0);

}

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

vector<int> buildSuffixArray(string txt, int n)

{

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

    struct suffix suffixes[n];

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

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

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

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

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

    {

        suffixes[i].index = i;

        suffixes[i].rank[0] = txt[i] - 'a';

        suffixes[i].rank[1] = ((i+1) < n)?

                              (txt[i + 1] - 'a'): -1;

    }

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

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

    sort(suffixes, suffixes+n, cmp);

    // На этом этапе все суффиксы отсортированы по

    // до первых 2 символов. Давайте разберем суффиксы

    // в соответствии с первыми 4 символами, затем первым

    // 8 и т. Д.

    int ind[n];  // Этот массив необходим для получения

                 // индекс в суффиксах [] из оригинала

                 // показатель. Это отображение необходимо, чтобы получить

                 // следующий суффикс.

    for (int k = 4; k < 2*n; k = k*2)

    {

        // Присвоение значений ранга и индекса первому суффиксу

        int rank = 0;

        int prev_rank = suffixes[0].rank[0];

        suffixes[0].rank[0] = rank;

        ind[suffixes[0].index] = 0;

        // Присвоение ранга суффиксам

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

        {

            // Если первый и следующий ряды совпадают с

            // присвоение предыдущего суффикса в массиве

            // тот же новый ранг этого суффикса

            if (suffixes[i].rank[0] == prev_rank &&

               suffixes[i].rank[1] == suffixes[i-1].rank[1])

            {

                prev_rank = suffixes[i].rank[0];

                suffixes[i].rank[0] = rank;

            }

            else // Иначе увеличиваем ранг и присваиваем

            {

                prev_rank = suffixes[i].rank[0];

                suffixes[i].rank[0] = ++rank;

            }

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

        }

        // Назначаем следующий ранг каждому суффиксу

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

        {

            int nextindex = suffixes[i].index + k/2;

            suffixes[i].rank[1] = (nextindex < n)?

                      suffixes[ind[nextindex]].rank[0]: -1;

        }

        // Сортировка суффиксов по первым k символам

        sort(suffixes, suffixes+n, cmp);

    }

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

    // массив

    vector<int>suffixArr;

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

        suffixArr.push_back(suffixes[i].index);

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

    return  suffixArr;

}

  
/ * Для построения и возврата LCP * /

vector<int> kasai(string txt, vector<int> suffixArr)

{

    int n = suffixArr.size();

    // Хранить массив LCP

    vector<int> lcp(n, 0);

    // Вспомогательный массив для хранения обратного суффиксного массива

    // элементы. Например, если суффиксArr [0] равен 5,

    // invSuff [5] будет хранить 0. Это используется для получения следующего

    // строка суффикса из массива суффиксов.

    vector<int> invSuff(n, 0);

    // Заполняем значения в invSuff []

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

        invSuff[suffixArr[i]] = i;

    // Инициализируем длину предыдущего LCP

    int k = 0;

    // Обрабатываем все суффиксы один за другим, начиная с

    // первый суффикс в txt []

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

    {

        / * Если текущий суффикс равен n-1, то мы не

           есть следующая подстрока для рассмотрения. Так что lcp не

           определенный для этой подстроки, мы ставим ноль. * /

        if (invSuff[i] == n-1)

        {

            k = 0;

            continue;

        }

        / * j содержит индекс следующей подстроки

           считаться для сравнения с настоящим

           подстрока, т.е. следующая строка в массиве суффиксов * /

        int j = suffixArr[invSuff[i]+1];

        // Непосредственно начать сопоставление с k-го индекса как

        // будет соответствовать не менее k-1 символов

        while (i+k<n && j+k<n && txt[i+k]==txt[j+k])

            k++;

        lcp[invSuff[i]] = k; // lcp для настоящего суффикса.

        // Удаление начального символа из строки.

        if (k>0)

            k--;

    }

    // возвращаем построенный массив lcp

    return lcp;

}

  
// Утилита для получения суммы первых N чисел

int sumOfFirstN(int N)

{

    return (N * (N + 1)) / 2;

}

  
// Возвращает K-й символ в отсортированном сцепленном
// подстроки str

char printKthCharInConcatSubstring(string str, int K)

{

    int n = str.length();

    // вычисляем массив суффиксов и массив lcp

    vector<int> suffixArr = buildSuffixArray(str, n);

    vector<int> lcp = kasai(str, suffixArr);

    for (int i = 0; i < lcp.size(); i++)

     {

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

         // (n - suffixArr [i]) - длина текущего

         // максимальная подстрока lcp [i] будет длиной

         // общая подстрока

        int charToSkip = sumOfFirstN(n - suffixArr[i]) -

                         sumOfFirstN(lcp[i]);

        / * если символы больше K, это означает

            K-й символ принадлежит подстроке

            соответствует текущему lcp [i] * /

        if (K <= charToSkip)

        {

            // цикл от текущего значения lcp до текущего

            // длина строки

            for (int j = lcp[i] + 1; j <= (n-suffixArr[i]); j++)

            {

                int curSubstringLen = j;

                / * Снова уменьшаем K на текущую подстроку

                   длина один за другим, и когда она становится меньше,

                    вывести Kth символ текущей строки * /

                if (K <= curSubstringLen)

                    return str[(suffixArr[i] + K - 1)];

                else

                    K -= curSubstringLen;

            }

            break;

        }

        else

            K -= charToSkip;

     }

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    string str = "banana";

    int K = 10;

    cout << printKthCharInConcatSubstring(str, K);

    return 0;

}