Рубрики

Подсчет отдельных подстрок строки с использованием Suffix Array

Для заданной строки длиной n строчных букв алфавита нам нужно подсчитать общее количество различных подстрок этой строки.
Примеры:

Input  : str = “ababa”
Output : 10
Total number of distinct substring are 10, which are,
"", "a", "b", "ab", "ba", "aba", "bab", "abab", "baba"
and "ababa"

Мы обсудили решение на основе суффикса Trie в следующем посте:
Подсчет различных подстрок строки с использованием суффикса Три

Мы можем решить эту проблему, используя суффиксный массив и концепцию самого длинного общего префикса. Суффиксный массив — это отсортированный массив всех суффиксов данной строки.
Для строки «ababa» используются суффиксы: «ababa», «baba», «aba», «ba», «a». Получив эти суффиксы в отсортированном виде, мы получим наш суффиксный массив как [4, 2, 0, 3, 1]
Затем мы вычисляем массив lcp, используя алгоритм Касая . Для строки «ababa» массив lcp равен [1, 3, 0, 2, 0]

После построения обоих массивов мы рассчитываем общее количество различных подстрок, помня этот факт: если мы просмотрим префиксы каждого суффикса строки, мы охватим все подстроки этой строки.
Мы объясним процедуру для приведенного выше примера,

String  = “ababa”
Suffixes in sorted order : “a”, “aba”, “ababa”,
                            “ba”, “baba”
Initializing distinct substring count by length
of first suffix, 
Count = length(“a”) = 1        
Substrings taken in consideration : “a”

Now we consider each consecutive pair of suffix, 
lcp("a", "aba") = "a".
All characters that are not part of the longest 
common prefix contribute to a distinct substring. 
In the above case, they are 'b' and ‘a'. So they 
should be added to Count.
Count += length(“aba”) - lcp(“a”, “aba”) 
Count  = 3    
Substrings taken in consideration : “aba”, “ab”

Similarly for next pair also,
Count += length(“ababa”) - lcp(“aba”, “ababa”)
Count = 5
Substrings taken in consideration : “ababa”, “abab”

Count += length(“ba”) - lcp(“ababa”, “ba”)
Count = 7
Substrings taken in consideration : “ba”, “b”

Count += length(“baba”) - lcp(“ba”, “baba”)
Count = 9
Substrings taken in consideration : “baba”, “bab”

We finally add 1 for empty string.
count = 10

Выше идея реализована в следующем коде.

// C ++ код для подсчета общего количества различных подстрок
// строки
#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;

}

  
// метод, возвращающий счетчик общей подстроки

int countDistinctSubstring(string txt)

{

    int n = txt.length();

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

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

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

  

    // n - суффиксArr [i] будет длиной суффикса

    // в i-й позиции при инициализации массива суффиксов

    // считать с длиной первого суффикса отсортированного

    // суффиксы

    int result = n - suffixArr[0];

  

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

  

        // вычитаем lcp из длины суффикса

        result += (n - suffixArr[i]) - lcp[i - 1];

  

    result++;  // Для пустой строки

    return result;

}

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

int main()

{

    string txt = "ababa";

    cout << countDistinctSubstring(txt);

    return 0;

}

Выход:

10

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Подсчет отдельных подстрок строки с использованием Suffix Array

0.00 (0%) 0 votes