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

Question

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

#include<iostream>
#include<string.h>
#include<utility>
#include<algorithm>

using namespace std;

struct xx
{
string x;
short int d;
int lcp;
};

bool compare(const xx a,const xx b)
{
return a.x<b.x;
}

int findlcp(string a,string b)
{
int i=0,j=0,k=0;
while(i<a.length() && j<b.length())
{
if(a[i]==b[j])
{
k++;
i++;
j++;
}
else
{
break;
}
}
return k;
}

int main()
{
string a="banana";
xx b[100];
a=a+'$';
int len=a.length();
for(int i=0;i<len;i++)
{
b[i].x=a.substr(i);
b[i].d=i+1;
}
sort(b,b+len,compare);
for(int i=0;i<len;i++)
cout<<b[i].x<<" "<<b[i].d<<endl;
b[0].lcp=0;
b[1].lcp=0;
for(int i=2;i<len;i++)
{
b[i].lcp=findlcp(b[i].x,b[i-1].x);
}
for(int i=0;i<len;i++)
cout<<b[i].d<<" "<<b[i].lcp<<endl;
}

Это реализация
Суффикс Массив. Что мой вопрос в конструкции статьи Википедии дается как o (n) в худшем случае

Итак, в моей конструкции:

Я сортирую все суффиксы строки, используя сортировку stl. Это может быть как минимум O (nlogn) в худшем случае. Так что здесь я нарушаю конструкцию O (n).
Второй заключается в построении самый длинный общий префиксный массив конструкция дана O (n). Но я думаю, что моя реализация в O (n ^ 2)

Так что для 1-го, т.е. для сортировки

Если я использую сортировать по количеству я могу уменьшиться до O (n). Если я использую сортировку по счетчику, это правильно? Правильно ли мое понимание? Дайте мне знать, если мое понимание неверно
И есть ли способ найти LCP за O (n) время?

2

c++suffix-array time-complexity

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Во-первых, относительно ваших двух утверждений:

1) Я сортирую все суффиксы строки, используя сортировку stl. Это может быть как минимум O (nlogn) в худшем случае. Так что здесь я нарушаю O (n) конструкцию.

Сложность std::sort здесь хуже чем O (n log n). Причина в том, что O (n log n) предполагает наличие O (n log n) отдельных сравнений, и что каждое сравнение выполняется за O (1) раз. Последнее предположение неверно, потому что вы сортируете строки, а не атомарные элементы (например, символы или целые числа).

Поскольку длина строковых элементов, являющихся подстроками основной строки, равна O (n), можно с уверенностью сказать, что сложность алгоритма сортировки в худшем случае равна O (n).² войти n).

2) Второй заключается в построении самого длинного общего префиксного массива, который задается O (n). Но я думаю, что моя реализация в O (n ^ 2)

Да, ваша конструкция массива LCP O (n²) потому что вы работаете lcp функция n == len раз, и ваш lcp функция требует O (min (len (x), len (y))) времени для пары строк x, y.

Далее по поводу ваших вопросов:

Если я использую сортировку отсчета, я могу уменьшить до O (n). Если я использую сортировку по счету, это правильно? Мое понимание верно? Дайте мне знать, если мое понимание неверно.

К сожалению, ваше понимание неверно. Счетная сортировка является линейной, если за O (1) вы можете получить доступ к атомарному ключу для каждого элемента, который вы хотите отсортировать. Опять же, элементы имеют длину O (n) символов, поэтому это не сработает.

И есть ли способ найти LCP за O (n) время?

Да. Современные алгоритмы вычисления массива суффиксов, включая алгоритм DC (также известный как алгоритм Skew), предоставляют методы для вычисления массива LCP вместе с массивом суффиксов и делают это за O (n) времени.

Ссылка для алгоритма DC — Юха Кярккяйнен, Питер Сандерс: Построение массива простых суффиксов линейной работы, Автоматы, Языки и программирование
Конспект лекций в области компьютерных наук, том 2719, 2003, стр. 943-955 (DOI 10.1007 / 3-540-45061-0_73). (Но это не единственный алгоритм, который позволяет вам делать это за линейное время.)

Вы также можете взглянуть на реализации с открытым исходным кодом, упомянутые в этом посте SO: Каков текущий современный алгоритм построения массива суффиксов?. Многие из используемых здесь алгоритмов позволяют создавать массивы LCP с линейным временем в дополнение к конструкции массивов суффиксов (но не все реализации могут включать в себя реализацию этого; я не уверен).

Если вы согласны с примерами на Java, вы также можете посмотреть на код для jSuffixArrays. Он включает в себя, среди прочего, реализацию алгоритма постоянного тока наряду с построением массива LCP за линейное время.

4