Class ElementaryAlgorithms

java.lang.Object
  ElementaryAlgorithms

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)