网站 › 『 编程之美 』 › 一个类KMP的算法

Nisy 发表于 2014-9-29 18:31:54

一个类KMP的算法

看了一篇KMP算法的文章，对数学公式有点没绕明白，干脆自己琢磨琢磨吧。
Link: http://blog.csdn.net/yaochunnian/article/details/7059486

自己在纸上画了画，逻辑应该是找重复，简单实现了一个自己的逻辑，改天在继续研究。
我的想法是这样的
Test1 :
a a a b
0 0 1 2
Test2 :
a b a b c d
0 0 0 1 2 0
然后根据返回值 j，来判断如何处理。

void GetNextval(char const* pstr, int nlen, int* Value)   
{   
    int i = 1;
    int k = 0;
    int nMax = 0;
    memset( Value, 0, nlen * sizeof(int));
    while( i < nlen )   
    {   
      // "abaabac";
      if( *(pstr + i) == *(pstr) )   //循环的if部分   
      {
            nMax = k = 0;
            do
            {
                nMax ++;
                Value = nMax;
                k++;
            } while ( k < (nlen - i) &&
                *(pstr + i + k) == *(pstr + k) );

            i += k;
            continue;
      }
      i++;
    }
}

void GetNextvalEx(char const* pstr, int nlen, int* Value)   
{   
    int i = 1;
    int k = 0;
    int nMax = 0;
    memset( Value, 0, nlen * sizeof(int));
    while( i < nlen-1 )   
    {   
      // "aaaaaab";
      // "0012345";
      if( * pstr== *(pstr + i) )   //循环的if部分   
      {
            nMax = k = 0;
            do
            {
                ++k ;
                Value = ++nMax;
            } while ( i + k< nlen-1&&
                *(pstr + k) == *(pstr + i + k) );

            i += k;
            continue;
      }
      i++;
    }
}

int KmpSearch(char const* src, int len1, char const* dest, int len2, int const* Value, int pos)   
{   
    int i = pos;   
    int j = 0;
    int nIndex = 0;
    while ( i < len1 && j < len2 )   
    {   
      if( src == dest )   
      {   
            ++i;   
            ++j;   
      }   
      else   
      {   
            j = Value;
            if ( src != dest )
            {
                if ( j != 0 ) // j > 0
                  j = 0;
                ++i;
            }
      }   
    }   
    if( j == len2 )   
      nIndex = i-len2;   
    else   
      nIndex = -1;   

    return nIndex;
}

int   main()
{
    std::string src = "abababc";
    std::string prn = "abc";
    int* nextval = new int;
    GetNextval(prn.data(), prn.size(), nextval);
    int nIndex = KmpSearch(src.data(), src.size(), prn.data(), prn.size(), nextval, 0);
// delete ...
}

Nisy 发表于 2014-9-29 18:37:53

直接写的代码 转过来大家看下这样是否更好理解KMP的实现 没有做过测试 若有BUG还望反馈 ~

lucky_789 发表于 2014-9-29 21:08:32

果断顶！
那篇博文的原作者后来重新写了一篇，比较好理解了，关键是所谓的“前缀、后缀”，前后缀中间的部分为何不用证明不太明白，没学过数论。

lucky_789 发表于 2014-9-29 21:45:55

经测试，一切正常！

crackvip 发表于 2014-9-29 22:28:06

我也来占坐学习。。。

small-q 发表于 2014-9-29 23:42:35

学习啊!{:lol:}

hu251405204 发表于 2015-1-26 16:35:45

感谢楼主分享！

menglv 发表于 2015-6-2 18:30:24

居然在这里看到了nisy的kmp源码，测试一下。

查看完整版本: 一个类KMP的算法