Solution

Sort string suffix starting positions, then examine only adjacent entries:

def longestRepeated(): (Int, Int, Int) = {
  require(N >= 2)
  val suffixes = (0 until N).toArray.sortWith(before)
  var besti = suffixes(0)
  var bestj = suffixes(1)
  var bestk = 0
  var t = 1
  while (t < N) {
    val i = suffixes(t - 1)
    val j = suffixes(t)
    val k = longestFrom(i, j)
    if (k > bestk) {
      besti = i; bestj = j; bestk = k
    }
    t += 1
  }
  (besti, bestj, bestk)
}

The while loop retains a best triple among adjacent pairs already visited. All string suffix starting positions are distinct, and the adjacent-suffix characterization proves that considering these

N - 1

pairs suffices. The two definitions named longestRepeated in parts b and e are alternatives, not duplicate members of one software class.

Assuming a comparison sort using

O (N lo g N)

comparator calls, sorting takes

O (N lo g N (K + 1))

time, because each comparison scans characters. The final pass takes

O (N (K + 1))

. Thus overall time is $O (N lo g N (K + 1))$ , at worst $O (N^{2} lo g N)$ , with

O (N)

auxiliary storage for indices and ordinary sorting workspace. Merely storing indices does not make string suffix comparisons constant-time; claiming

O (N lo g N)

here would omit their cost. Faster suffix-array constructions require additional machinery beyond this comparator-based solution.

 Ancestors (12)

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 2 / e / Solution

 Ancestors (12)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)