C++実現文字列マッチングKMPアルゴリズム

13927 ワード

文書ディレクトリ
  • 1. 概要
  • 2. コード実装
  • 3. コードテスト
  • 1.概要
    Kmpアルゴリズムの紹介と思想は以下の2つの文章を参照する:文字列マッチングKMPアルゴリズムアルゴリズム)分かりやすい文字列マッチングKMPアルゴリズムとnext値アルゴリズムを求める
    2.コード実装
    int cTest::findstr1(const char *src, const char *des)
    {
        int srlen = strlen(src);
        int delen = strlen(des);
        int i = 0, j = 0, k = 0;
        for (int i = 0; i <= srlen - delen; i++)
        {
            /* code */
            for (k = i, j = 0; j < delen; ++k, ++j)
            {
                /* code */
                if (src[k] != des[j])
                    break;
            }
            if (j >= delen)
                return i;
        }
        return -1;
    }
    void cTest::subNext_kmp(const char *des, int *next)
    {
        next[0] = -1;
        int i = 0, k = -1;
        while (des[i] != '\0')
        {
            /* code */
            if (k == -1 || des[k] == des[i])
                next[++i] = ++k;
            else
                k = next[k];
        }
    }
    int cTest::findstr2(const char *src, const char *des, int* next)
    {
        int slen = strlen(src);
        int dlen = strlen(des);
        int i = 0, j = 0;
        while (i < slen && j < dlen)
        {
            /* code */
            if (j==-1 || src[i] == des[j])
            {
                ++i;
                ++j;
            }
            else
                /* code */
                j = next[j];
        }
        if (des[j] == '\0')
            return i - j;
        return -1;
    }
    

    3.コードテスト
    int main(int argc, char* argv[])
    {
        char s[] = "abcabaaaabaabcac";
        char p[] = "abaabcac";
        cout << ctestptr.findstr1(s, p) << endl;
        //shared_ptr next(new int[sizeof(p)],[](int* p){delete[] p;});
        int *next = (int *)malloc(sizeof(int) * sizeof(p));
        ctestptr.subNext_kmp(p, next);
        for (int i = 0; i < strlen(p); ++i)
            cout << next[i];
        cout << endl;
        cout << ctestptr.findstr2(s, p, next) << endl;
        free(next);
    }