Cyclic word equality problem:
  given two strings A and B with n letters.
  How many letter comparisons are necessary
  to decide, if A and B are equal under cyclic rotation?

  This means: does there exist a shift s, such that for all 0<=k<n
              there is A[ k ] = B[ (k+s) MOD n ] ?

You get an upper bound using string matching.
 let   TEXT = A[0], A[1], ... A[n-1], A[0], A[1], ... A[n-2]
 and   PATTERN = B

So one has:
  Number of comparisons for cyclic equality of word with length n  <=
  Number of comparisons for string matching (exists the pattern in the
  string) with text-length 2n-1 and pattern-length n.

-------------------------------------------------------------------------
Solution:
  The following perl-program gives a solution which need at most 2n-2
  letter comparisons. This is better than the general pattern matching
  bound.

Question:
  Why is this algorithm correct?
-------------------------------------------------------------------------
#!/software/bin/perl -w

# Cyclic Equivalence of Words
#
# Maximal number of compares are 2*n - 2.
# a maximal pair: aaaaaab, aaaaaba
# The algorithm needs an ordered alphabet.
# three-fold compares must be used to reach the upper bound.
#
# Ref: Maxime Crochemore, Wojciech Rytter
#      Text Algorithms
#      Oxford Univ. Press, 1994
#      pp 363
#
#      Gusfield
#      Algorithms on Strings, Trees, and ...
#      (Algorithms for Biologists)
#      Aplications for Prefix Trees

$w1 = $ARGV[0];    # Word 1
$w2 = $ARGV[1];    # Word 2

$len = length $w1;
if ($len != length($w2))
{
  print "$w1 $w2 :: are not cyclic equal (different length)\n";
}
else
{
  $dw1 = $w1 . $w1;
  $dw2 = $w2 . $w2;
  $n1 = 0;
  $n2 = 0;
  $compares = 0;
  while ($n1 < $len && $n2 < $len)
  {
     $k = 0;
     while ($k < $len && substr($dw1,$n1+$k,1) eq substr($dw2,$n2+$k,1))
     {
        $k ++;
	$compares ++;
     }


     if ($k == $len)
     {
        print "$w1 $w2 :: are cyclic Equal ! $compares compares used.\n";
	exit 0;
     }
     elsif (substr($dw1,$n1+$k,1) lt substr($dw2,$n2+$k,1))  # compared already
     {
	$n1 += $k+1;
     }
     else
     {
	$n2 += $k+1;
     }

  }
  print "$w1 $w2 :: are not cyclic equal. $compares compares used.\n";
}