那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

KMP算法的实现

KMP算法是一种用于字符串匹配的算法,这个算法的高效之处在于当在某个位置匹配不成功的时候可以根据之前的匹配结果从模式字符串的另一个位置开始,而不必从头开始匹配字符串.
因此这个算法的关键在于,当某个位置的匹配不成功的时候,应该从模式字符串的哪一个位置开始新的比较.假设这个值存放在一个next数组中,其中next数组中的元素满足这个条件:next[j] = k,表示的是当模式字符串中的第j + 1个(这里是遵守标准C语言中数组元素从0开始的约定,以下不再说明)发生匹配不成功的情况时,应该从模式字符串的第k + 1个字符开始新的匹配.如果已经得到了模式字符串的next数组,那么KMP算法的实现如下:

// KMP字符串模式匹配算法
// 输入: S是主串,T是模式串,pos是S中的起始位置
// 输出: 如果匹配成功返回起始位置,否则返回-1
int KMP(PString S, PString T, int pos)
{
    assert(NULL 
!= S);
    assert(NULL 
!= T);
    assert(pos 
>= 0);
    assert(pos 
< S->length);
    
    
if (S->length < T->length)
        
return -1;

    printf(
"主串\t = %s\n", S->str);
    printf(
"模式串\t = %s\n", T->str);

    
int *next = (int *)malloc(T->length * sizeof(int));
    
// 得到模式串的next数组
    GetNextArray(T, next);

    
int i, j;
    
for (i = pos, j = 0; i < S->length && j < T->length; )
    
{
        
// i是主串游标,j是模式串游标
        if (-1 == j ||                // 模式串游标已经回退到第一个位置
            S->str[i] == T->str[j]) // 当前字符匹配成功
        {
            
// 满足以上两种情况时两个游标都要向前进一步
            ++i;
            
++j;
        }

        
else                        //  匹配不成功,模式串游标回退到当前字符的next值
        {
            j 
= next[j];
        }

    }


    free(next);

    
if (j >= T->length)
    
{
        
// 匹配成功
        return i - T->length;
    }

    
else
    
{
        
// 匹配不成功
        return -1;
    }

}


下面看看如何得到next数组.
这是一个递推求解的过程,初始的情况是next[0] = -1.
假设在某一个时刻有如下的等式成立:str[0...k-1] = str[j - k...j - 1],那么next[j] = k,在这个前提下,继续进行下一个字符的匹配.
1)如果str[0...k] = str[j - k...j],那么next[j + 1] = next[j] + 1 = k + 1.
2)反之,如果上面的匹配不成立,那么就要从next[k]开始进行新的匹配,如果成功的话,那么:
next[j + 1] = next[next[j]] + 1 = next[k] + 1;
如果还是不能匹配成功就再从next[next[k]]的位置开始进行的新的匹配,直到匹配成功为止.如果这个过程一直进行下去都没有找到可以成功匹配的字符的话,那么next[j + 1] = 0,这时表示要从字符串的第一个位置开始新的匹配了.
用一个公式表示上述的算法,那么可以写作:
next[j] =
1)-1,当j = 0时;
2) Max{k | 0 <= k < j && str[0..k - 1] = str[j - k...j - 1]};
3)0,其他情况,此时匹配要从第一个位置重新开始.
寻找next数组的算法如下:

//  得到字符串的next数组
void  GetNextArray(PString pstr,  int  next[])
{
    assert(NULL 
!=  pstr); 
    assert(NULL 
!=  next);
    assert(pstr
-> length  >   0 );

    
//  第一个字符的next值是-1,因为C中的数组是从0开始的
    next[ 0 =   - 1 ;
    
for  ( int  i  =   0 , j  =   - 1 ; i  <  pstr -> length  -   1 ; )
    
{
        
//  i是主串的游标,j是模式串的游标
        
//  这里的主串和模式串都是同一个字符串
         if  ( - 1   ==  j  ||                          //  如果模式串游标已经回退到第一个字符
            pstr -> str[i]  ==  pstr -> str[j])     //  如果匹配成功
         {
            
//  两个游标都向前走一步
             ++ i;
            
++ j;
            
//  存放当前的next值为此时模式串的游标值
            next[i]  =  j;
        }

        
else                                  //  匹配不成功j就回退到上一个next值
         {
            j 
=  next[j];
        }

    }

}



完整的算法如下:
/* *******************************************************************
    created:    2006/07/02
    filename:     KMP.cpp
    author:        李创
                
http://www.cppblog.com/converse/
                
                参考资料: 严蔚敏<<数据结构>>

    purpose:    KMP字符串匹配算法的演示
********************************************************************
*/


#include 
< stdio.h >
#include 
< stdlib.h >
#include 
< assert.h >
#include 
< string .h >

#define  MAX_LEN_OF_STR    30             //  字符串的最大长度

typedef 
struct  String                 //  这里需要的字符串数组,存放字符串及其长度
{
    
char     str[MAX_LEN_OF_STR];     //  字符数组
     int         length;                     //  字符串的实际长度
}
String,  * PString;

//  得到字符串的next数组
void  GetNextArray(PString pstr,  int  next[])
{
    assert(NULL 
!=  pstr); 
    assert(NULL 
!=  next);
    assert(pstr
-> length  >   0 );

    
//  第一个字符的next值是-1,因为C中的数组是从0开始的
    next[ 0 =   - 1 ;
    
for  ( int  i  =   0 , j  =   - 1 ; i  <  pstr -> length  -   1 ; )
    
{
        
//  i是主串的游标,j是模式串的游标
        
//  这里的主串和模式串都是同一个字符串
         if  ( - 1   ==  j  ||                          //  如果模式串游标已经回退到第一个字符
            pstr -> str[i]  ==  pstr -> str[j])     //  如果匹配成功
         {
            
//  两个游标都向前走一步
             ++ i;
            
++ j;
            
//  存放当前的next值为此时模式串的游标值
            next[i]  =  j;
        }

        
else                                  //  匹配不成功j就回退到上一个next值
         {
            j 
=  next[j];
        }

    }

}


//  KMP字符串模式匹配算法
//  输入: S是主串,T是模式串,pos是S中的起始位置
//  输出: 如果匹配成功返回起始位置,否则返回-1
int  KMP(PString S, PString T,  int  pos)
{
    assert(NULL 
!=  S);
    assert(NULL 
!=  T);
    assert(pos 
>=   0 );
    assert(pos 
<  S -> length);
    
    
if  (S -> length  <  T -> length)
        
return   - 1 ;

    printf(
" 主串\t = %s\n " , S -> str);
    printf(
" 模式串\t = %s\n " , T -> str);

    
int   * next  =  ( int   * )malloc(T -> length  *   sizeof ( int ));
    
//  得到模式串的next数组
    GetNextArray(T, next);

    
int  i, j;
    
for  (i  =  pos, j  =   0 ; i  <  S -> length  &&  j  <  T -> length; )
    
{
        
//  i是主串游标,j是模式串游标
         if  ( - 1   ==  j  ||                  //  模式串游标已经回退到第一个位置
            S -> str[i]  ==  T -> str[j])  //  当前字符匹配成功
         {
            
//  满足以上两种情况时两个游标都要向前进一步
             ++ i;
            
++ j;
        }

        
else                          //   匹配不成功,模式串游标回退到当前字符的next值
         {
            j 
=  next[j];
        }

    }


    free(next);

    
if  (j  >=  T -> length)
    
{
        
//  匹配成功
         return  i  -  T -> length;
    }

    
else
    
{
        
//  匹配不成功
         return   - 1 ;
    }

}

posted on 2006-07-05 17:44 那谁 阅读(7250) 评论(8)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: KMP算法的实现  回复  更多评论   

数据结构课程上给过的算法.
说实话,我一直不能从书上那简单的描述中理解这个算法,直到现在仍然如此,惭愧.
2006-07-05 18:13 | LOGOS

# re: KMP算法的实现  回复  更多评论   

没关系,我也是花了好长时间才整明白的,自己实现一下估计就能清楚好多了~~
2006-07-05 18:18 | 创系

# re: KMP算法的实现  回复  更多评论   

求next函数其实就是自己和自己比一次。。kmp最重要就是求next函数了。。画画图模拟一下,应该比较容易理解的:)
2006-07-08 12:18 |

# re: KMP算法的实现  回复  更多评论   

收藏
2006-12-08 15:12 | todaygood

# re: KMP算法的实现  回复  更多评论   

2011-10-07 19:16 | kol

# re: KMP算法的实现  回复  更多评论   

这个应该有简单的算法吧 ~~ 不用这么多的函数 ~~
2011-10-07 19:25 | kol

# re: KMP算法的实现  回复  更多评论   

算法貌似错了
计算
bacbabababacaca
ababaca 的时候
前缀是
-1 0 -1 0 -1 3 -1
结果 next[-1] 越界了
2012-04-26 12:01 | Davis

# re: KMP算法的实现  回复  更多评论   

哦,不好意思,看错了
2012-04-26 12:11 | Davis

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理