RISC JKU

at.jku.risc.stout.urau.algo

Class RigidityFncSubstring



  • public class RigidityFncSubstring
    extends RigidityFnc
    Implementation for rigidity function with substring matching.
    Let m be the number of left term atoms and n be the number of right term atoms.
    Time complexity = O(m * n)
    Space complexity = O(max(m, n))

    This implementation reuses all the allocated objects for performance reasons. That's why the space complexity will become the maximum of all m's and n's. O(max(m1, ..., mk, n1, ..., nk))

    Possible optimization:
         trim off the matching items at the beginning
         while start <= m_end and start <= n_end and X[start] = Y[start]
             start := start + 1
         trim off the matching items at the end
         while start <= m_end and start <= n_end and X[m_end] = Y[n_end]
             m_end := m_end - 1
             n_end := n_end - 1
     
    Author:
    Alexander Baumgartner