Class ElementaryAlgorithms

java.lang.Object
  extended byElementaryAlgorithms

public class ElementaryAlgorithms
extends java.lang.Object

This class implements the elementary algorithms on words of Section 1.2. These include string-matching algorithms, subwords with longest common subwords and conjugacy with minimal cyclic conjugate and Lyndon factorization. Usage:
java ElementaryAlgorithms command word1 (opt) word2
where command can be one of
border to print the border array of word1
borderSharp to print the sharp border array of word1
circularMin to print the least conjugate of word1
lyndonFact to print the Lyndon factorization of word1
lcsArray to print the array of lengths of the longest common subwords of word1 and word2
lcs to print a longest common subword of word1 and word2
.


Constructor Summary
ElementaryAlgorithms()
           
 
Method Summary
static int[] border(java.lang.String x)
          Implements the algorithm Border(x) of Section 1.2.2.
static int[] borderSharp(java.lang.String x)
          Implements the algorithm BorderSharp(x) of Problem 1.2.1.
static int circularMin(java.lang.String x)
          Implements the algorithm CircularMin() of Section 1.2.5.
static boolean isSubword(java.lang.String x, java.lang.String y)
          Implements the algorithm IsSubword() of Section 1.2.4.
static java.lang.String lcs(java.lang.String x, java.lang.String y)
          Implements the algorithm LCS()() of Section 1.2.4.
static int lcsLength(java.lang.String x, java.lang.String y)
          Computes the length of a longest common subword of x and y.
static int[][] lcsLengthArray(java.lang.String x, java.lang.String y)
          Implements the algorithm LcsLengthArray() of Section 1.2.4.
static int longestCommonPrefix(java.lang.String x, java.lang.String y)
          Implements the algorithm LongestCommonPrefix() of Section 1.2.1.
static java.lang.String lyndonFact(java.lang.String x)
          Returns the Lyndon factorization of the word x in the form (fact1)(fact2)...
static int[] lyndonFactorization(java.lang.String x)
          Implements the function LyndonFactorization() of Section 1.2.5.
static int[] lyndonFactorizationR(java.lang.String x, int k)
          The same as lyndonFactorization concerning x[k..]
static void main(java.lang.String[] args)
           
static java.lang.String minConjugate(java.lang.String x)
          Returns the least conjugate of x.
static boolean naiveStringMatching(java.lang.String x, java.lang.String y)
          Implements the algorithm NaiveStringMatching(x,y) of Section 1.2.3.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ElementaryAlgorithms

public ElementaryAlgorithms()
Method Detail

border

public static int[] border(java.lang.String x)
Implements the algorithm Border(x) of Section 1.2.2. The border of a nonempty word x is the longest proper prefix of x which is also a suffix of x. Complexity: linear in the length of x. Actually, the number of comparisons is at most 2*|x|.

Returns:
the array b[] of border lengths, where b[i] is the length of the border of x[0..i-1]

borderSharp

public static int[] borderSharp(java.lang.String x)
Implements the algorithm BorderSharp(x) of Problem 1.2.1. Complexity: linear in |x|.

Returns:
the sharp border array of x. For a word x of length m, sb[m]=b[m] and for 1<=j<=m-1, sb[j] is the largest integer i such that x[0..i-1]=x[j-i..j-1] and x[j]!=x[i].

circularMin

public static int circularMin(java.lang.String x)
Implements the algorithm CircularMin() of Section 1.2.5. Complexity: linear in |x|.

Returns:
the index k such that x[k..k-1] is the least conjugate of x.

minConjugate

public static java.lang.String minConjugate(java.lang.String x)
Returns the least conjugate of x.


lyndonFactorization

public static int[] lyndonFactorization(java.lang.String x)
Implements the function LyndonFactorization() of Section 1.2.5. Complexity: O(|x|).

Returns:
the longest prefix of x which is a Lyndon word and its exponent in the factorization of x.

lyndonFactorizationR

public static int[] lyndonFactorizationR(java.lang.String x,
                                         int k)
The same as lyndonFactorization concerning x[k..].


lyndonFact

public static java.lang.String lyndonFact(java.lang.String x)
Returns the Lyndon factorization of the word x in the form (fact1)(fact2).... Complexity: O(|x|).


naiveStringMatching

public static boolean naiveStringMatching(java.lang.String x,
                                          java.lang.String y)
Implements the algorithm NaiveStringMatching(x,y) of Section 1.2.3. Complexity: O(|x|*|y|).

Returns:
true if x is a factor of y.

longestCommonPrefix

public static int longestCommonPrefix(java.lang.String x,
                                      java.lang.String y)
Implements the algorithm LongestCommonPrefix() of Section 1.2.1.

Returns:
the length of the longest common prefix of x and y.

isSubword

public static boolean isSubword(java.lang.String x,
                                java.lang.String y)
Implements the algorithm IsSubword() of Section 1.2.4. Complexity: Complexity: O(|y|).

Returns:
true if x is a subword of y.

lcsLength

public static int lcsLength(java.lang.String x,
                            java.lang.String y)
Computes the length of a longest common subword of x and y. Complexity: O(|x|*|y|).


lcsLengthArray

public static int[][] lcsLengthArray(java.lang.String x,
                                     java.lang.String y)
Implements the algorithm LcsLengthArray() of Section 1.2.4. Complexity: O(|x|*|y|).

Returns:
the array M[i][j] giving the length of a longest common subword of x[0..i-1] and y[0..j-1].

lcs

public static java.lang.String lcs(java.lang.String x,
                                   java.lang.String y)
Implements the algorithm LCS()() of Section 1.2.4. Complexity: O(|x|*|y|).

Returns:
a longest common subword of x[0..i-1] and y[0..j-1].

main

public static void main(java.lang.String[] args)