2894. Суффиксный массив

 

Дана строка, требуется построить суффиксный массив для этой строки. Суффиксный массив – лексикографически отсортированный массив всех суффиксов строки. Каждый суффикс задается целым числом – позицией начала.

Строка s лексикографически меньше строки t, если существует такое i, что si < ti и si = tj для всех j < i. Или, если такого i не существует и строка s короче строки t.

Здесь si - код i-го символа строки s.

 

Вход. Одна строка – английский литературный текст. Длина текста не превосходит 105. Коды всех символов в тексте от 32 до 127.

 

Выход. Выведите n чисел – суффиксный массив данной строки.

 

Пример входа

99 bottles of beer.

 

Пример выхода

14 3 11 19 2 1 15 4 16 17 9 13 8 12 5 18 10 7 6

 

 

РЕШЕНИЕ

суффиксный массив

 

Анализ алгоритма

Задачу можно решить наивным методом: отсортировав все суффиксы входной строки при помощи функции сортировки sort.

Оценка сложности алгоритма O(n2logn), так как сложность самой сортировки O(nlogn), а для сравнения двух строк требуется время O(n).

 

Реализация алгоритма

Объявим входную строку s и суффиксный массив id.

 

#define MAX 100010

char s[MAX];

int id[MAX];

 

Функция сортировки. Сравниваются суффиксы, начинающиеся в позициях s[a] и s[b].

 

bool cmp(const int &a, const int &b)

{

  return strcmp(s + a, s + b) < 0;

}

 

Основная часть программы. Читаем входную строку s. Инициализируем массив id.

 

gets(s); len = strlen(s);

for(i = 0; i < len; i++) id[i] = i;

 

Сортируем массив id, сравнивая соответствующие суффиксы строк.

 

sort(id,id+len,cmp);

 

Выводим суффиксный массив.

 

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

  printf("%d ",id[i]+1);

 

 

Реализация алгоритма – построение суффиксного массива

 

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

 

// Structure to store information of a suffix

struct suffix

{

  int index; // To store original index

  int rank[2]; // To store ranks and next rank pair

};

 

// A comparison function used by sort() to compare two suffixes

// Compares two pairs, returns 1 if first pair is smaller

int cmp(suffix a, suffix b)

{

  if (a.rank[0] == b.rank[0]) return a.rank[1] < b.rank[1];

  return a.rank[0] < b.rank[0];

}

 

// This is the main function that takes a string 'txt' of size n as an

// argument, builds and return the suffix array for the given string

vector<int> buildSuffixArray(char *txt)

{

  int n = strlen(txt);

  // A structure to store suffixes and their indexes

  vector<suffix> suffixes(n);

 

  // Store suffixes and their indexes in an array of structures.

  // The structure is needed to sort the suffixes alphabatically

  // and maintain their old indexes while sorting

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

  {

    suffixes[i].index = i;

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

    suffixes[i].rank[1] = ((i+1) < n) ? (txt[i + 1]) : -1;

  }

 

  // Sort the suffixes using the comparison function

  // defined above.

  sort(suffixes.begin(), suffixes.end(), cmp);

 

  // At this point, all suffixes are sorted according to first

  // 2 characters.  Let us sort suffixes according to first 4

  // characters, then first 8 and so on

  vector<int> ind(n);

 

  // This array is needed to get the index in suffixes[]

  // from original index.  This mapping is needed to get

  // next suffix.

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

  {

    // Assigning rank and index values to first suffix

    int rank = 0;

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

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

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

 

    // Assigning rank to suffixes

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

    {

      // If first rank and next ranks are same as that of previous

      // suffix in array, assign the same new rank to this suffix

      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 // Otherwise increment rank and assign

      {

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

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

      }

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

    }

 

    // Assign next rank to every suffix

    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;

    }

 

    // Sort the suffixes according to first k characters

    sort(suffixes.begin(), suffixes.end(), cmp);

  }

 

  // Store indexes of all sorted suffixes in the suffix array

  vector<int> suffixArr(n);

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

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

 

  // Return the suffix array

  return suffixArr;

}

 

// A utility function to print an array of given size

void printArr(vector<int> &arr)

{

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

    printf("%d ",arr[i]+1);

  printf("\n");

}

 

char s[100010];

 

// Driver program to test above functions

int main(void)

{

  gets(s);

  int n = strlen(s);

 

  vector<int> suffixArr = buildSuffixArray(s);

 

  printArr(suffixArr);

  return 0;

}