LCP Array

Loading...

来自 University of California San Diego 的课程

Algorithms on Strings

460 个评分

University of California San Diego

Algorithms on Strings

460 个评分

课程 4（共 6 门，Specialization 数据结构与算法）

World and internet is full of textual information. We search for information using textual queries, we read websites, books, e-mails. All those are strings from the point of view of computer science. To make sense of all that information and make search efficient, search engines use many string algorithms. Moreover, the emerging field of personalized medicine uses many search algorithms to find disease-causing mutations in the human genome.

从本节课中

Constructing Suffix Arrays and Suffix Trees

In this module we continue studying algorithmic challenges of the string algorithms. You will learn an O(n log n) algorithm for suffix array construction and a linear time algorithm for construction of suffix tree from a suffix array. You will also implement these algorithms and the Knuth-Morris-Pratt algorithm in the last Programming Assignment in this course.

Suffix Array and Suffix Tree8:59

Computing the LCP Array6:00

Construct Suffix Tree from Suffix Array and LCP Array6:38

与讲师见面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

So we define LCP array and let's consider suffix array A of string

S in the raw form that is that A[0] is a suffix, A[1] is a suffix and

so on up to A[S-1], all those are suffixes of S in lexicographic order.

Then LCP array of string S is the array LCP small of size length of S-1.

It contains fewer elements than the suffix array and then the string itself.

Besides that, each element lcp[i] is just equal to the longest common prefix length.

Between A[i] and A[i+1].

So it's the longest common prefix of two neighboring elements in the suffix

array and what we want is to compute the values of this array.

For example if we have our string ababaa$.

Then, we first compute the longest common prefix of $, and a$, which is 0.

Then, we compute the longest common prefix of a$ and aa$, which is a of length 1.

Then it's again a of length 1.

Then it's aba of length 3.

Then it's empty.

And then it's ba of length 2.

so the LCP array for this string is 0, 1,1, 3, 0, 2.

And the central LCP array property which will enable us to compute it fast is that

for any end assist i and j In the suffix array, where i is less than j.

The longest common prefix between A[i] and A[j] which are far from each other,

is not bigger than the LCP of i,

which is basically the longest common prefix of i and the next element.

So what I'm saying with this Lemma is that the LCP

of two neighboring elements is always at least as big

as the LCP of the first one of them with any of the next elements.

And the same goes the other way.

The LCP of two neighboring elements is at least the same

as LCP of the second of them with any of the previous ones.

And to see that let's look at some hypothetical example that we have some

long suffix array and elements i and i+1 are here.

And also there is some element j farther in the suffix array.

And we see that really the common prefix of suffixes i and i+1 is pretty long.

It's not so long with suffix j, it's only of length two.

But this example doesn't yet prove anything.

So maybe for some other situation with a suffix number i+1, it could be solved that

the common prefix of i and j will be bigger than common prefix of i and i+1.

So let's suppose that, and

we don't know what is suffix i + 1, so we just replace it with many x.

X is an unknown letter.

We know that the LCP of i and j is equal to 2.

So let's consider k which is the length of the longest

common prefix of A[i] and A[i + 1].

And we suppose that it is smaller than 2 in this case.

So how can that be?

One variant is if A[i + 1] is shorter than 2,

and then A[i + 1] is actually a prefix of A[i].

But in this case, A[i+1] is smaller than Ai which contradicts the property of

the suffix array.

That the suffixes are sorted.

And if suffix i+1 is sufficiently long then it follows that it's kth character

is different from the kth character of both ith suffix and jth suffix.

And in this case there are again two cases.

In the first case is that this character in suffix i+1 is bigger

than the corresponding one in strings i and j.

But from this it immediately follows that suffix i+1 is bigger

than suffix j which contradicts the suffix array properties, so it is impossible.

And another case is that this character is

less than the corresponding character in both strings i and j.

But in this case it immediately follows that A[i] is bigger than

A[i + 1] which again contradicts the suffix array property.

So in all cases we found the contradiction.

And so, it is not possible that the longest common prefix of i and

j is bigger than the longest common prefix of i and i+1.

And we proved the LCP array property because for

this symmetric case, the proof is a null x.

Now how do we compute the LCP array?

One variant is to go for each i, compare A[i] and

A[i+1] character by character and compute the LCP directly.

But this will work in linear time for each i.

And in total it will be length of the string squared.

And we want to compute everything in linear time.

So how to do this faster, and you will learn that in the next video.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取