c++ - 使用 Boyer-Moore-Horspool 向后搜索

Question

我已经实现了 Boyer-Moore-Horspool 搜索算法，当我想在我的文本中向前搜索时它工作得很好。我正在尝试使其向后工作，但似乎无法正确处理。

是否有使用 BMH 向后搜索的示例？

作为参考，这是我的代码：

POSITION_T cDocument::FindNext(std::string needle, POSITION_T start)
{
    size_t buffersize = mBuffer.GetByteSize() ;
    size_t needlesize = needle.length() ;
    vector<int> badchars(256, -1) ;

    BadCharHueristic(needle, badchars) ;

    size_t s = mBuffer.ConvertPositionToByte(start) ;
    while(s <= (buffersize - needlesize))
    {
        ssize_t j = needlesize - 1 ;

        while(j >= 0 && needle[j] == mBuffer.GetByte(s + j))
        {
            j-- ;
        }

        if(j < 0)
        {
            // s holds our position in bytes
            return mBuffer.ConvertByteToPosition(s) ;
        }
        else
        {
            ssize_t b = j - badchars[mBuffer.GetByte(s + j)] ;
            s += Max(1, b) ;
        }
    }

    return GetTextSize() ;
}

标签： c++stringalgorithmsearchpattern-matching

Answer 1

//Java Solution

public static int findLastBoore(char[] text, char[] pattern) {

    int n = text.length;
    int m = pattern.length;

    if (m == 0) return 0;
    Map<Character, Integer> last = new HashMap<Character, Integer>();
    
    for (int i = 0; i < n; i++) {
        last.put(text[i], -1);
    }
    for (int k = 0; k < m; k++){
        last.put(pattern[k], k);
    }   
    int i = n - m;
    int k = 0;

    while (i > 0) {
        if (text[i] == pattern[k]) {
            if (k == m - 1) return i;
            i++;
            k++;
        } else {
            // Step backwards when there is a mismatch
            i-= m - Math.max(k + 1, last.get(text[i]));
            k = 0;
        }
        
    }
    return -1;
}

`