随笔-20  评论-16  文章-36  trackbacks-0
KMP算法的Fail函数
KMP算法真的是很强大，特别是Fail()的思想，它可以解决许多字符串内重复子串的问题，包括回文，前缀后缀匹配等。比如POJ的2406 Power Strings 1961 Period 2752 Seek the Name, Seek the Fame，都是利用了Fail()的值与字符下标的关系来解决的。

    下面是Fail()函数的实现代码：

void fail(char a[], int b[]){
    int len= strlen(a);   
    for( int i= 1; i< len; i++ ){
        int j= b[i-1];
        while( (*(a+i)!=*(a+j+1) && (j>=0)) ) j= b[j];
        if(*(a+i)==*(a+j+1)) b[i]= j+1;
        else b[i]= -1;
    } 
}
posted on 2009-03-13 14:07 古月残辉 阅读(969) 评论(0)  编辑 收藏 引用 所属分类: Theory

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 古月残辉