@Test
public void searchForMatch() throws Exception {

  String[] testCases = {
    "a",
    "aa",
    "az",
    "za",
    "aaaaa",
    "CACAO",
    "banana",
    "tobeornottobe",
    "the quick brown fox jumps over the lazy dog.",
    "elephantelephantelephantelephantelephant",
    "011010011001011010010110011010010",
  };
  for (String testCase : testCases) {
    int size = testCase.length();
    byte[] bytes = testCase.getBytes(StandardCharsets.US_ASCII);
    RandomAccessObject input = new RandomAccessObject.RandomAccessByteArrayObject(bytes);
    RandomAccessObject suffixArray =
        new DivSuffixSorter(new RandomAccessObjectFactory.RandomAccessByteArrayObjectFactory())
            .suffixSort(input);
    // Test exact matches for every non-empty substring.
    for (int lo = 0; lo < size; ++lo) {
      for (int hi = lo + 1; hi <= size; ++hi) {
        byte[] query = Arrays.copyOfRange(bytes, lo, hi);
        int querySize = query.length;
        Assert.assertEquals(querySize, hi - lo);
        RandomAccessObject queryBuf = new RandomAccessObject.RandomAccessByteArrayObject(query);
        BsDiff.Match match = BsDiff.searchForMatch(suffixArray, input, queryBuf, 0, 0, size);
        Assert.assertEquals(querySize, match.length);
        Assert.assertTrue(match.start >= 0);
        Assert.assertTrue(match.start <= size - match.length);
        byte[] suffix = Arrays.copyOfRange(bytes, match.start, match.start + match.length);
        Assert.assertArrayEquals(query, suffix);
      }
    }
  }
}