c - ボイヤー・ムーア・アルゴリズムの実装?

Question

CでBoyer-Moore文字列検索アルゴリズムの実例はありますか? いくつかのサイトを見てきましたが、ウィキペディアを含め、かなりバグがあるようです。

ありがとう。

Answer 1

部分文字列検索アルゴリズムに最適なサイト:

http://igm.univ-mlv.fr/~lecroq/string/

Answer 2

Bob Stout のSnippetsサイトには、Boyer-Moore-Horspool (Sunday のバリアントを含む) の実装がいくつかあります。BMHSRCH.Cでの Ray Gardner の実装は、私の知る限りバグがなく¹、間違いなく私が今まで見たり聞いたりした中で最も高速です。ただし、これを理解するのは最も簡単ではありません。彼はかなりトリッキーなコードを使用して、内部ループをできるだけ単純に保ちます。私の偏見かもしれませんが、PBMSRCH.Cのバージョン²の方が少し理解しやすいと思います (確かに少し遅いですが)。

¹制限内 -- 元々は MS-DOS 用に作成されたものであり、より多くのメモリを提供する環境用に書き直すことができます。
²これはどういうわけか「Pratt-Boyer-Moore」というラベルが付けられましたが、実際には、Boyer-Moore-Horspool の日曜日の変種です (私はその時点でそれを認識しておらず、公開していませんでしたが、実際に私が発明したと信じています)。日曜日の約1年前）。

Answer 3

これは、多くの奇妙なテスト ケースで強調した C90 の実装です。

#ifndef MAX
#define MAX(a,b)  ((a > b) ? (a) : (b))
#endif

void  fillBadCharIndexTable (
    /*----------------------------------------------------------------
    function:
       the table fits for 8 bit character only (including utf-8)
    parameters: */
    size_t  aBadCharIndexTable [],
    char const *  const pPattern,
    size_t  const patternLength)
    /*----------------------------------------------------------------*/
{
    size_t  i;
    size_t  remainingPatternLength = patternLength - 1;

    for (i = 0;  i < 256; ++i) {
        aBadCharIndexTable [i] = patternLength;
    }
    for (i = 0;  i < patternLength;  ++i) {
        aBadCharIndexTable [pPattern [i]] = remainingPatternLength--;
    }
}

void  fillGoodSuffixRuleTable (
    /*----------------------------------------------------------------
    function:
       the table fits for patterns of length < 256; for longer patterns ... (1 of)
       - increase the static size
       - use variable length arrays and >= C99 compilers
       - allocate (and finally release) heap according to demand
    parameters: */
    size_t  aGoodSuffixIndexTable [],
    char const *  const pPattern,
    size_t  const patternLength)
    /*----------------------------------------------------------------*/
{
    size_t  const highestPatternIndex = patternLength - 1;
    size_t  prefixLength = 1;

    /* complementary prefix length, i.e. difference from highest possible pattern index and prefix length */
    size_t  cplPrefixLength = highestPatternIndex;

    /* complementary length of recently inspected pattern substring which is simultaneously pattern prefix and suffix */
    size_t  cplPrefixSuffixLength = patternLength;

    /* too hard to explain in a C source ;-) */
    size_t  iRepeatedSuffixMax;

    aGoodSuffixIndexTable [cplPrefixLength] = patternLength;

    while (cplPrefixLength > 0) {
        if (!strncmp (pPattern,  pPattern + cplPrefixLength,  prefixLength)) {
            cplPrefixSuffixLength = cplPrefixLength;
        }

        aGoodSuffixIndexTable [--cplPrefixLength] = cplPrefixSuffixLength + prefixLength++;
    }

    if (pPattern [0] != pPattern [highestPatternIndex]) {
        aGoodSuffixIndexTable [highestPatternIndex] = highestPatternIndex;
    }

    for (iRepeatedSuffixMax = 1;  iRepeatedSuffixMax < highestPatternIndex;  ++iRepeatedSuffixMax) {
        size_t  iSuffix = highestPatternIndex;
        size_t  iRepeatedSuffix = iRepeatedSuffixMax;

        do {
            if (pPattern [iRepeatedSuffix] != pPattern [iSuffix]) {
                aGoodSuffixIndexTable [iSuffix] = highestPatternIndex - iRepeatedSuffix;
                break;
            }

            --iSuffix;
        } while (--iRepeatedSuffix > 0);
    }
}

char const *  boyerMoore (
    /*----------------------------------------------------------------
    function:
       find a pattern (needle) inside a text (haystack)
    parameters: */
    char const *  const pHaystack,
    size_t  const haystackLength,
    char const *  const pPattern)
    /*----------------------------------------------------------------*/
{
    size_t  const patternLength = strlen (pPattern);
    size_t  const highestPatternIndex = patternLength - 1;
    size_t  aBadCharIndexTable [256];
    size_t  aGoodSuffixIndexTable [256];

    if (*pPattern == '\0') {
        return pHaystack;
    }

    if (patternLength <= 1) {
        return strchr (pHaystack,  *pPattern);
    }

    if (patternLength >= sizeof aGoodSuffixIndexTable) {
        /* exit for too long patterns */
        return 0;
    }

    {
        char const *  pInHaystack = pHaystack + highestPatternIndex;

        /* search preparation */
        fillBadCharIndexTable (
            aBadCharIndexTable,
            pPattern,
            patternLength);
        fillGoodSuffixRuleTable (
            aGoodSuffixIndexTable,
            pPattern,
            patternLength);

        /* search execution */
        while (pInHaystack++ < pHaystack + haystackLength) {
            int  iPattern = (int) highestPatternIndex;

            while (*--pInHaystack == pPattern [iPattern]) {
                if (--iPattern < 0) {
                    return pInHaystack;
                }
            }

            pInHaystack += MAX (aBadCharIndexTable [*pInHaystack],  aGoodSuffixIndexTable [iPattern]);
        }
    }

    return 0;
}