程序包 edu.princeton.cs.algs4

类 SuffixArrayX

  • public class SuffixArrayX
extends java.lang.Object
    The SuffixArrayX class represents a suffix array of a string of length n. It supports the selecting the ith smallest suffix, getting the index of the ith smallest suffix, computing the length of the longest common prefix between the ith smallest suffix and the i-1st smallest suffix, and determining the rank of a query string (which is the number of suffixes strictly less than the query string).

    This implementation uses 3-way radix quicksort to sort the array of suffixes. For a simpler (but less efficient) implementations of the same API, see SuffixArray. The index and length operations takes constant time in the worst case. The lcp operation takes time proportional to the length of the longest common prefix. The select operation takes time proportional to the length of the suffix and should be used primarily for debugging.

    This implementation uses '\0' as a sentinel and assumes that the charater '\0' does not appear in the text.

    In practice, this algorithm runs very fast. However, in the worst-case it can be very poor (e.g., a string consisting of N copies of the same character. We do not shuffle the array of suffixes before sorting because shuffling is relatively expensive and a pathologial input for which the suffixes start out in a bad order (e.g., sorted) is likely to be a bad input for this algorithm with or without the shuffle.

    For additional documentation, see Section 6.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • 构造器概要

      构造器 
      构造器 说明
      SuffixArrayX​(java.lang.String text)
      Initializes a suffix array for the given text string.

    • 方法概要

      修饰符和类型 方法 说明
      int index​(int i)
      Returns the index into the original string of the ith smallest suffix.
      int lcp​(int i)
      Returns the length of the longest common prefix of the ith smallest suffix and the i-1st smallest suffix.
      int length()
      Returns the length of the input string.
      static void main​(java.lang.String[] args)
      Unit tests the SuffixArrayx data type.
      int rank​(java.lang.String query)
      Returns the number of suffixes strictly less than the query string.
      java.lang.String select​(int i)
      Returns the ith smallest suffix as a string.

      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • 构造器详细资料

      • SuffixArrayX

        public SuffixArrayX​(java.lang.String text)
        Initializes a suffix array for the given text string.
        参数:
        text - the input string

    • 方法详细资料

      • length

        public int length()
        Returns the length of the input string.
        返回:
        the length of the input string

      • index

        public int index​(int i)
        Returns the index into the original string of the ith smallest suffix. That is, text.substring(sa.index(i)) is the i smallest suffix.
        参数:
        i - an integer between 0 and n-1
        返回:
        the index into the original string of the ith smallest suffix
        抛出:
        java.lang.IllegalArgumentException - unless 0 <=i < n

      • lcp

        public int lcp​(int i)
        Returns the length of the longest common prefix of the ith smallest suffix and the i-1st smallest suffix.
        参数:
        i - an integer between 1 and n-1
        返回:
        the length of the longest common prefix of the ith smallest suffix and the i-1st smallest suffix.
        抛出:
        java.lang.IllegalArgumentException - unless 1 <= i < n

      • select

        public java.lang.String select​(int i)
        Returns the ith smallest suffix as a string.
        参数:
        i - the index
        返回:
        the i smallest suffix as a string
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < n

      • rank

        public int rank​(java.lang.String query)
        Returns the number of suffixes strictly less than the query string. We note that rank(select(i)) equals i for each i between 0 and n-1.
        参数:
        query - the query string
        返回:
        the number of suffixes strictly less than query

      • main

        public static void main​(java.lang.String[] args)
        Unit tests the SuffixArrayx data type.
        参数:
        args - the command-line arguments