注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

简约男人

简约,不能简单

 
 
 

日志

 
 
关于我

一个过分渴望被理解的人其实就是一个软弱的人, 勇往直前的力量来自斩钉截铁的决心,不是来自别人的理解.

网易考拉推荐

Horspool串匹配算法  

2009-10-12 15:41:03|  分类: 算法学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Horspool算法
这个算法是由R.Nigel Horspool在1980年提出的。其滑动思想非常简单,就是从后往前匹配模式串,若在某一位失去匹配,此位对应的文本串字符为c,那就将模式串向右滑动,使模式
串之前最近的c对准这一位,再从新从后往前检查。那如果之前找不到c怎么办?那好极了,直接将整个模式串滑过这一位。
例如:

文本串:abdabaca
模式串:baca

倒数第2位失去匹配,模式串之前又没有d,那模式串就可以整个滑过,变成这样:

文本串:abdabaca
模式串:   baca

发现倒数第1位就失去匹配,之前1位有c,那就向右滑动1位:

文本串:abdabaca
模式串:    baca

实现代码:

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

int  Horspool_match(const string & S,const string & M,int pos);

int main( )
{
    string S="abcdefghabcdefghhiijiklmabc";
    string T="hhiij";
    int    pos = Horspool_match(S,T,3);
   
    cout<<"\n"<<pos<<endl;
    system("pause");
    return 0;
}

int  Horspool_match(const string & S,const string & M,int pos)
{
    int  S_len = S.size();
    int  M_len = M.size();
    int  Mi = M_len-1,Si= pos+Mi;//这里的串的第1个元素下标是0

    if( (S_len-pos) < M_len )
        return -1;

    while ( (Mi>-1) && (Si<S_len) )
    {
        if (S[Si] == M[Mi])
        {
            --Mi;
            --Si;
        }
        else
        {
           do{ Mi--; } while( (S[Si]!=M[Mi]) || (Mi>-1) );
           Mi = M_len - 1;
           Si += M_len - 1;
        }
    }

    if(Si < S_len)    return(Si + 1);
    else              return -1;
}

  评论这张
 
阅读(3727)| 评论(6)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017