string(10) "newsevents"
June 12, 2014

Detecting all repeated patterns in sequences using suffix arrays

  • May 24, 2024 till May 24, 2024
  • IIT, NCSR "Demokritos"
  • Main Lecture Room (IIT)

Pattern detection is a topic of great interest for many sciences. Suffix trees and suffix arrays are the most commonly used data structures for this purpose. For such purposes we have created the novel algorithm ARPaD, which uses the suffix array under a new perspective. With the use of the recursive algorithm ARPaD over the actual suffix array we can perform a fast analysis of any kind of sequences and detect all repeated patterns in linear time complexity. By introducing Longest Expected Repeated Pattern concept we have managed also to reduce the required space capacity of our method to linear for random sequences without any kind of prior knowledge or analysis. Furthermore, the novel process of Moving LERP makes feasible the fast analysis of any kind and size of sequences in linear time and space complexity.

Skip to content