posts - 3,  comments - 28,  trackbacks - 0

看了两三天的KMP算法,一直看的迷迷糊糊的.现在把这些资料贴在这里...以备日后之需
 
1.串的模式匹配的改进算法(这个网站对我的理解帮助很大,特别是右边的那块说明部分,以前自己脑筋老是转不过来) http://cist.dhu.edu.cn/kejian/%CA%FD%BE%DD%BD%E1%B9%B9%BE%AB%C6%B7%BF%CE%B3%CC/%D4%DA%CF%DF%D1%A7%CF%B0/text/chapter04/section3/c5.htm

2.KMP 算法的注记 http://www.cublog.cn/u/20/showart_136705.html 

3.KMP算法中推导next[],nextval[]--手记 http://jiasimon040510.t8log.ccut.cn/blog-htm-do-showone-tid-6983.html


4.算法原理:

在匹配过和中,当主串中第i个字符与模式串中第j个字符“失配”时(s[i]!=t[j]),将模式串尽量向右移动,让模式串中第k(k<j)个字符与si对齐继续比较,

要让这个条件成立,那么在k之前的k个t字符[0 到 k-1]必须在i之前的k个s字符[i-k 到 i-1]相匹配即:

   t[0, 1, 2...k-1] == s[i-k, i-k+1, i-k+2...i-1]     ---(1)

而由之前的部分匹配成功的结果可知:
  
   t[0, 1, 2...j-1] == s[i-j, i-j+1, i-j+2...i-1]     ---(2)
==>
   t[j-k, j-k+1, j-k+2...j-1] == s[i-k, i-k+1, i-k+2...i-1]   --(3)

由(1)与(3)可得:

   t[0, 1, 2...k-1] == t[j-k, j-k+1, j-k+2...j-1]     ---(4)

求出k值,就是next[j]的值了

总之,相对我来说,算法不是很好懂.但是大家看到我这么笨的人到最后都能明白一二.大家就更没有理由看不懂了,祝大家成功附上我的测试源码:



#include 
< iostream >

using   namespace  std;


void  GetNext( char  t[],  int  next[])
{
    
int  j  =   0 ;
    
int  k  =   - 1 ;
    next[j] 
=  k;
    
int  tlen  =  strlen(t);

    
while (j < tlen)
    
{
        
if (k  ==   - 1   ||  t[j]  ==  t[k])
        
{
            j
++ ;
            k
++ ;
            
if (t[j]  ==  t[k])
            
{
                next[j] 
=  next[k];
            }

            
else
                next[j] 
=  k;
        }

        
else
        
{
            k 
=  next[k];
        }

    }

}



int  KMP( char  s[],  char  t[],  int  pos,  int  next[])
{
    
int  slen  =  strlen(s);
    
int  tlen  =  strlen(t);
    
int  i  =   0 ;
    
int  j  =   0 ;

    
while (i < slen  &&  j < tlen)
    
{
        
if (j  ==   - 1   ||  s[i]  ==  t[j])
        
{
            i
++ ;
            j
++ ;
        }

        
else
        
{
            j 
=  next[j];    
        }

    }


    
if (j  ==  tlen)
    
{
        
return  i - tlen;
    }

    
else
        
return   - 1 ;
}


int  main ( int  argc,  char   ** argv)
{
    
    
char  s[]  =   " aaaabaabaaabaaabaaaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabacb " ;
    
    
char  t[]  =   " aabaaa " ;

    
int  next[ 20 ] = { 0 } ;
    GetNext(t, next);    
    
for ( int  i = 0 ; i < 20 ; i ++ )
        cout
<< " next[ " << i << " ]:   " << next[i] << endl;
    
    cout
<< KMP(s, t,  0 , next) << endl;
}
posted on 2006-11-10 01:51 猪头饼 阅读(1277) 评论(0)  编辑 收藏 引用 所属分类: 算法/数据结构

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


<2010年12月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

积分与排名

  • 积分 - 5956
  • 排名 - 1291

最新评论

阅读排行榜

评论排行榜