Example Problems that can be done by suffix array
Problem 1.
Minimum lexicographic rotation of a string
Given string A, add the string to itself.
Compute the suffix array of only first half. (use the characters of second half also)
the smallest suffix gives the minimum lexicographic rotation of a string.
Problem 2.
You are given a text consisting of N characters (big and small letters of the English alphabet and
digits). A substring of this text is a subsequence of characters that appear on consecutive positions in the text. Given an integer K, find the length of the longest substring that appears in the text at least K times (1 ≤ N ≤ 16384).
Having the text's suffixes sorted, iterate with a variable i from 0 to N – K and compute the longest
common prefix of suffix i and suffix i + K – 1. The biggest prefix found during this operation represents
the problem's solution.
Read full article from Eureka!!: Suffix Array
No comments:
Post a Comment