• In R, implement a function SuffixArray() to create a suffix array from a string.

• Input:

  • a DNAString

• Output:

  • a vector of integers

• In R, implement a function InverseSuffixArray() to create an inverse suffix array from a suffix array.

• Input:

  • a vector of integers representing suffix array

• Output:

  • a vector of integers

• In R, implement a function LCPArray() according to pseudocode.

• Input:

  • a DNAString representing analyzed string
  • a vector of integers representing a suffix array
  • a vector of integers representing an inverse suffix array

• Output:

  • a vector of integers

LCPArray(text, SA, ISA)
1   LCP[1] <- -1
2   LCP[m + 1] <- -1
3   l <- 0
4   for i <- 1 to m
5     j <- ISA[i]
6     if j > 1 then
7       k <- SA[j - 1]
8       while text[k + l] = text[i + l] do
9         l <- l + 1
10      LCP[j] <- l
11      l <- max{l - 1, 0}
12  return LCP

Hint: The text will be indexed at m + 1 position, that does not exist. Add one character at the end of the text (in general use $, for DNAString in R use +).

• In R, implement a function BinarySearchSA() according to the following pseudocode.

• Input:

  • a vector of integers representing a suffix array
  • a DNAString representing a pattern to be found
  • a DNAString representing a text to be searched

• Output:

• a vector of two integers (start and end indexes of suffix array, where the pattern was found)

BinarySearchSA(Pattern, Text, SuffixArray)
1   minIndex <- 1
2   maxIndex <- length (Text)
3   while minIndex < maxIndex
4     midlIndex <- floor(minIndex + maxIndex) / 2
5     if Pattern <= suffix of Text starting at position SuffixArray(midlIndex)
6       maxIndex <- midlIndex
7     else
8       minIndex <- midlIndex + 1
9   First <- minIndex
10  maxIndex <- length(Text)
11  while maxIndex > minIndex
12    midlIndex <- floor(minIndex + maxIndex) / 2
13    if suffix of Text starting at position SuffixArray(midlIndex) <= Pattern
14      minIndex <- midlIndex + 1
15    else
16      maxInd <- midlIndex
17  Last <- maxIndex - 1
18  if Last < First
19    return('Pattern does not appear in Text')
20  else
21    return First, Last

git clone <fork repository address>

git remote add upstream https://github.com/mpa-prg/exercise_10.git

git add <file_name>

git commit

git push origin main