RISC JKU

at.jku.risc.stout.urau.algo

Class RigidityFncSubsequence



  • public class RigidityFncSubsequence
    extends RigidityFnc
    Implementation for rigidity function with subsequence matching.
    Let m be the number of left term atoms and n be the number of right term atoms.
    Time complexity = Exponential worst case (back tracking) but should be OK in average case
    Space complexity = O(m * n)

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