随笔 - 25, 文章 - 0, 评论 - 6, 引用 - 0
数据加载中……

KMP 匹配算法

一:BF算法
     如果让你写字符串的模式匹配,你可能会很快的写出朴素的bf算法,至少问题是解决了,我想大家很清楚的知道它的时间复杂度为O(MN),原因很简单,主串和模式串失配的时候,我们总是将模式串的第一位与主串的下一个字符进行比较,所以复杂度高在主串每次失配的时候都要回溯,图我就省略了。

 二:KMP算法
   刚才我们也说了,主串每次都要回溯,从而提高了时间复杂度,那么能不能在“主串”和“模式串”失配的情况下,主串不回溯呢?而是让”模式串“向右滑动一定的距离,对上号后继续进行下一轮的匹配,从而做到时间复杂度为O(M+N)呢?所以kmp算法就是用来处理这件事情的。


代码:
#pragma once

#include <iostream>

//                --- 朴素匹配算法 --- 

int NaiveMatch(const char * txt, const char * pat)  
{
    int  nTxtLength = strlen(txt);
    int  nPatLength = strlen(pat);
    int  nTxt = 0;
    int  nPat = 0;
    int nCount = 0; // 计数

    while (nTxt <= nTxtLength - nPatLength && nPat < nPatLength)  
    {
        ++nCount;

        if (pat[nPat] == txt[nTxt+nPat])
        {
            ++nPat;
        }
        else
        {
            ++nTxt;
            nPat = 0;
        }
    }

    std::cout << "NaiveMatch, compare counts: " << nCount << std::endl;

    return  (nPat == nPatLength ? nTxt : -1);




//                --- KMP 匹配算法 ---

void GetNext(const char* pattern, int next[])
{
    next[0] = 0;

    int j = 0;
    for (int i = 1; i < strlen(pattern); i++)
    {
        while( j > 0 && pattern[j] != pattern[i] )
        {
            j = next[j-1];
        }

        if (pattern[j] == pattern[i])
            j++;

        next[i] = j;
    }
}

int KMPMatch(const char* src, const char* pattern, int next[])
{
    int nSrc = 0;
    int nPattern = 0;
    int nCount = 0; // 计数

    while(nSrc < strlen(src) && nPattern < strlen(pattern))
    {
        ++nCount;
        if (0 == nPattern || src[nSrc] == pattern[nPattern])
        {
            ++nPattern;
            ++nSrc;
        }
        else
        {
            nPattern = next[nPattern];
        }
    }

    std::cout << "KMP, compare counts: " << nCount << std::endl;

    return (nPattern == strlen(pattern) ? nSrc - nPattern : -1);
}



#define PRINT_RESLUT(v) { if(-1 == (v)) std::cout << "No Find!"; else std::cout << "Position = " << (v); std::cout << std::endl << std::endl; }

int main()
{
    const char* Src        = "abc1aabc1aabc1aaababc1aababc1aabc1aaabc1aabc1aababc1aaabaabcbc1aa";
    const char* Pattern = "abaabc";

    int nPos = -1; // 保存匹配到的位置

    /// 朴素匹配算法
    nPos = NaiveMatch(Src, Pattern);
    PRINT_RESLUT(nPos);

    /// KMP匹配算法
    int next[6] = {0};
    GetNext(Pattern, next);
    nPos = KMPMatch(Src, Pattern, next);
    PRINT_RESLUT(nPos);
   
   system("pause");
   return 0;     
}

运行结果:


疑惑:为什么KMP的效率会更低?

posted on 2013-03-20 19:06 chenjt3533 阅读(266) 评论(0)  编辑 收藏 引用 所属分类: C/C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理