Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4116239
  • 博文数量: 930
  • 博客积分: 12070
  • 博客等级: 上将
  • 技术积分: 11448
  • 用 户 组: 普通用户
  • 注册时间: 2008-08-15 16:57
文章分类

全部博文(930)

文章存档

2011年(60)

2010年(220)

2009年(371)

2008年(279)

分类: C/C++

2008-11-23 18:17:12

kmp算法
 
 
 设有主串s和子串t,子串t定位是指在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t

        传统的字符串模式匹配算法(也就是BF算法)就是对于主串和模式串双双自左向右,一个一个字符比较,如果不匹配,主串和模式串的位置指针都要回溯。这样的算法时间复杂度为Onm),其中nm分别为串s和串t的长度。

        KMP 算法是由KnuthMorrisPratt等人共同提出的,所以成为KnuthMorrisPratt算法,简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比,KMP算法的不同点是匹配过程中,主串的位置指针不会回溯,这样的结果使得算法时间复杂度只为Onm)。下面说说KMP算法的原理。

假设我们有个模式串为“abdabcde”存于数组t,我们要求的就是模式串的next值,见下表所示:


i

0

1

2

3

4

5

6

7

t[i]

a

b

d

a

b

c

d

e

next[i]

-1

0

0

0

1

2

0

0

        求模式tnext[i](称为失效函数)的公式如下:


next[i] =Screenshot11.png

( 上面的公式中非t字母和数字组成的为数组下标)

        应该如何理解next数组呢?在匹配过程中,如果出现不匹配的情况(当前模式串不匹配字符假定为t[i]),它所对应的next[i]的数值为接下来要匹配的模式串的字符的索引;也就是说,出现不匹配的情况时,模式串的索引指针要回溯到中next[i]所对应的位置,而主串的索引指针保持不变。

        特别的,next数组中的next[0]next[1]的取值是固定的,为了标识出首字母,需要假定next[0]为-1(取为-1是考虑到C语言中的数组索引以0开始)。在实现的时候,要实现公式中情况的处理需要些技巧,下面给出具体的实现:

# include 
#include 


typedef struct QString {
    char
*  cs;
    
int  len;
}String;


void GetNext(String s
, int   next []){
    
int  len  =  s . len;
    
int  i  =   0 ;
    
int  k  =   - 1 ;
    
next [ 0 =   - 1 ;
    
while (i  <  len - 1 ){
        
if (k ==- 1   ||  s . cs[i]  ==  s . cs[k]){
            i
++ ;
            k
++ ;
            
next [i]  =  k;
        }
else {
            k 
=   next [k];
        }
    }
}


int  KMPIndex(String s , String m){
    
int   next [m . len] , i = 0 , j = 0 ;
    
int  k;
    GetNext(m
, next );
    while (i < s . len   && j < m . len){
        
if (j ==- 1   ||  s . cs[i]  ==  m . cs[j]){
            i
++ ;
            j
++ ;
        }
else {
            j 
=   next [j];
        }
    }
    
if (j  >=  m . len) return  i - m . len;
    
else   return   - 1 ;
}


        KMP 算法也有需要改进的地方。对于模式串“aaaadd”在匹配时(假定被匹配串为“aaadddd”),可以看到,在匹配到索引3时,主串字符为“d”,模式串字符为“a”,如果按照上面的做法,这时模式串只会回溯一个索引,由于仍不匹配,模式串还会回溯一个索引,直到索引位置到了首字符,主串的索引指针才会前进一位,这样就会浪费一些不必要的比较时间。出现这种情况的原因是模式串中位置i的字符与next[i]对应的字符相同,需要修正next[i]next[i]对应的字符的索引。下面列出“aaaadd”修正的nextval数组的内容:

i

0

1

2

3

4

5

t[i]

a

a

a

a

d

d

next[i]

-1

0

1

2

3

0

nextval[i]

-1

-1

-1

-1

0

0

        修正函数如下:

void GetNextval(String s , int  nextval[]){
    
int  len  =  s . len , =   0 , =   - 1 ;
    nextval[
0 =   - 1 ;
    
while (i  <  len - 1 ){
        
if (k ==- 1   ||  s . cs[i]  ==  s . cs[k]){
            i
++ ;
            k
++ ;
            
if (s . cs[i]  !=  s . cs[k]){
                nextval[i] 
=  k;
            }
else    nextval[i]  =   nextval[k];            
        }
else {
            k 
=  nextval[k];
        }
    }
}


阅读(2070) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~