Boyer-Moore算法的伪代码

Boyer-Moore算法是一种用于字符串匹配的高效算法。下面是Boyer-Moore算法的伪代码：

function BoyerMoore(text, pattern):
    n = length of text
    m = length of pattern
    if m > n:
        return -1

    // 初始化坏字符表
    badCharTable = createBadCharTable(pattern)

    // 初始化好后缀表
    goodSuffixTable = createGoodSuffixTable(pattern)

    // 开始匹配
    i = m - 1
    while i < n:
        j = m - 1
        while j >= 0 and text[i] == pattern[j]:
            i = i - 1
            j = j - 1
        if j == -1:
            return i + 1
        else:
            // 计算坏字符位移
            badCharShift = calculateBadCharShift(j, text[i], badCharTable)
            // 计算好后缀位移
            goodSuffixShift = calculateGoodSuffixShift(j, pattern, goodSuffixTable)
            // 取较大的位移
            shift = max(badCharShift, goodSuffixShift)
            i = i + shift

    return -1

function createBadCharTable(pattern):
    table = empty table
    m = length of pattern
    for i = 0 to m - 2:
        table[pattern[i]] = m - 1 - i
    return table

function createGoodSuffixTable(pattern):
    table = empty table
    m = length of pattern
    suffixes = findSuffixes(pattern)
    for i = 0 to m - 1:
        table[i] = m
    for i = m - 1 to 0:
        if suffixes[i] == i + 1:
            for j = 0 to m - 1 - i:
                if table[j] == m:
                    table[j] = m - 1 - i
    for i = 0 to m - 2:
        table[m - 1 - suffixes[i]] = m - 1 - i
    return table

function findSuffixes(pattern):
    m = length of pattern
    suffixes = empty array
    suffixes[m - 1] = m
    g = m - 1
    for i = m - 2 to 0:
        if i > g and suffixes[i + m - 1 - f] < i - g:
            suffixes[i] = suffixes[i + m - 1 - f]
        else:
            if i < g:
                g = i
            f = i
            while g >= 0 and pattern[g] == pattern[g + m - 1 - f]:
                g = g - 1
            suffixes[i] = f - g
    return suffixes

function calculateBadCharShift(j, char, badCharTable):
    if char in badCharTable:
        return j - badCharTable[char]
    else:
        return j + 1

function calculateGoodSuffixShift(j, pattern, goodSuffixTable):
    m = length of pattern
    k = m - 1 - j
    if goodSuffixTable[k] != m:
        return m - 1 - goodSuffixTable[k]
    else:
        for r = j + 2 to m - 1:
            if isPrefix(pattern, r):
                return m - r
        return m

function isPrefix(pattern, p):
    m = length of pattern
    k = 0
    for i = p to m - 1:
        if pattern[i] != pattern[k]:
            return False
        k = k + 1
    return True