Linuxカーネル内のKMP実装コードをユーザースペースに移行

オリジナル:http://www.yuanma.org/data/2007/0420/article_2535.htm
C/C++言語プログラミングでは、一般的な文字列検索操作は標準ライブラリのstrstr()関数によって行われます.これは、通常、文字列の検索操作が多くないため、効率的な問題は発生しません.実際,この関数の時間的複雑さは楽観的ではない.長さnの文字列から長さmのサブ文字列を検索する場合、このstrstr()関数の最悪の時間複雑度はO(n*m)であり、サブ文字列長mが大きくなるにつれてstrstr()関数の時間複雑度もそれに応じて倍増し、より効率的なアルゴリズムはないか.
KMP(Knuth-Morris-Pratt)アルゴリズムは,パターン文字列中の対応する文字における遡及インデックスを予め計算することにより,パターンマッチング時の不要な遡及動作を回避し,効率を向上させ,時間的複雑さをO(m+n)に変えた.もっと詳しい内容については、Google先生に教えてもらうのはいい主義です.
KMPアルゴリズムの詳細」という文章の説明は透徹していて、見る価値がある.
KMPアルゴリズムは,各文字の遡及インデックスを保存するため,空間的複雑度がやや増加する.
sizeof(idx)*length(pattern)
また,nが比較的小さい場合,遡及インデックスの確立に導入されるO(m)個の時間的複雑さは容易ではないかもしれない.これらの条件により、KMPアルゴリズムは、nとmの両方が比較的大きく、ネットワーク侵入検出システムやQoSシステムなど、文字列検索操作が比較的頻繁な環境に適用される.
実際にLinux 2.6版カーネルは2.6.14からstringというiptablesマッチング(match)モジュールを導入し、KMP、BM(Boyer-Moore)、FSM(finite state machine)アルゴリズムを提供し、キーワードベースのネットワークフィルタリングを実現することができる.
このアルゴリズムを学習する過程で、Linuxカーネルの実装コードをユーザー空間に移した.
#include <assert.h>
#include <stdio.h>

void kmp_init(const char *patn, int len, int *next)
{
        int i, j;

        assert(patn != NULL && len > 0 && next != NULL);
        next[0] = 0;
        for (i = 1, j = 0; i < len; i ++) {
                while (j > 0 && patn[j] != patn[i])
                        j = next[j - 1];
                if (patn[j] == patn[i])
                        j ++;
                next[i] = j;
        }
}

int kmp_find(const char *text, int text_len, const char *patn,
                int patn_len, int *next)
{
        int i, j;

        assert(text != NULL && text_len > 0 && patn != NULL && patn_len > 0
                        && next != NULL);
        for (i = 0, j = 0; i < text_len; i ++ ) {
                while (j > 0 && text[i] != patn[j])
                        j = next[j - 1];
                if (text[i] == patn[j])
                        j ++;
                if (j == patn_len)
                        return i + 1 - patn_len;
        }

        return -1;
}

int main(int argc, char *argv[])
{
        int *next;
        int i, pos, len = strlen(argv[2]);

        if (argc < 3) {
                printf("Usage: %s text pattern/n", argv[0]);
                return 1;
        }

        next = calloc(strlen(argv[2]), sizeof(int));
        kmp_init(argv[2], strlen(argv[2]), next);
        printf("next array:/n");
        for (i = 0; i < len; i ++)
                printf("/t%c", argv[2][i]);
        printf("/n");
        for (i = 0; i < len; i ++)
                printf("/t%d", next[i]);
        printf("/n");

        pos = kmp_find(argv[1], strlen(argv[1]), argv[2], strlen(argv[2]), next);
        printf("find result:/n");
        if (pos < 0) {
                printf("None found!/n");
        } else {
                printf("%s/n", argv[1]);
                for (i = 0; i < pos; i ++)
                        printf(" ");
                printf("^/n");
        }

        return 0;
}