java - 后缀数组的二分查找

Question

我的代码正确计算了间隔的起始位置，但没有正确计算结束位置:

    int left;
    int bot = 0; int top = textLength;

    while(bot != top)
    {
        int mid = (bot+top)/2;

        if(pattern.compareTo(text.substring(suffixArray.get(mid))) > 0) bot = mid + 1;
        else top = mid;
    }

    left = bot;



    int right;
    bot = left; top = textLength;

    while(bot != top)
    {
        int mid = (bot+top)/2;

        if(pattern.compareTo(text.substring(suffixArray.get(mid))) < 0) top = mid;
        else bot = mid+1;
    }

    right = bot;

我将它与互联网上的几个伪代码进行了比较，但我真的不明白为什么它不起作用。我错过了什么？

Answer 1

对right的搜索仅在>=而不是>中有所不同

    if(pattern.compareTo(text.substring(suffixArray.get(mid))) >= 0) bot = mid + 1;
    else top = mid;

所以我想

right = bot;

指向下一个更高的值。

所以最好先检查是否所有都已订购:

String old = text.substring(suffixArray.get(0));
for (int i = 1; i < textLength; ++i) {
    String next = text.substring(suffixArray.get(i));
    if (old.compareTo(next) >= 0) {
        System.err.printf("Wrong order at [%d] '%s' >= [%d] '%s'%n",
            i - 1, old, i, next);
    }
    old = next;
}