Suffix array: Difference between revisions

Revision as of 03:09, 5 October 2021

Revision as of 15:32, 21 October 2021

Line 1:

{{Infobox

{| class="infobox" style="width: 22em"

!| colspan="3"above style="font-size: 125%; text-align: center;" | Suffix array

| label1 = [[List of data structures|Type]]

|-

!| data1 = [[List ofArray data structuresstructure|TypeArray]]

!| label2 = Invented by

| colspan="2" | [[Array data structure|Array]]

{{!}}| data2 colspan="2" {{!}} {{harvtxt|Manber|Myers|1990}}

|-

!| colspan="3"header3 class="navbox-abovebelow" | [[Time complexity]]<br />in [[big O notation]]

! Invented by

| headerstyle = background:lavender

{{!}} colspan="2" {{!}} {{harvtxt|Manber|Myers|1990}}

| data4 =

|-

{{aligned table|cols=3|row1header=y|col1header=y|fullwidth=y

! colspan="3" class="navbox-abovebelow" | [[Time complexity]]<br />in [[big O notation]]

| | Average | Worst case

|-

<!-- -->

|

| AverageSpace

| Worst case

|-

! Space

| <math>\mathcal{O}(n)</math>

| <math>\mathcal{O}(n)</math>

<!-- -->

|-

!| Construction

| <math>\mathcal{O}(n)</math>

| <math>\mathcal{O}(n)</math>

|}}

}}

In [[computer science]], a '''suffix array''' is a sorted [[Array data structure|array]] of all [[Suffix (computer science)|suffixes]] of a [[String (computer science)|string]]. It is a data structure used in, among others, full text indices, data compression algorithms, and the field of [[bibliometrics]].