| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1182 人关注过本帖
标题:horspool算法问题,代码没问题,就是不太明白Horspool-Match函数的语句的意 ...
只看楼主 加入收藏
一条沙丁鱼
Rank: 1
等 级:新手上路
威 望:1
帖 子:44
专家分:7
注 册:2015-4-5
结帖率:100%
收藏
已结贴  问题点数:15 回复次数:3 
horspool算法问题,代码没问题,就是不太明白Horspool-Match函数的语句的意思,例如short skip[256],求此函数的详细注释
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;
const m=100;
const n=50;

int HorspoolMatch(char S[], int SSize,char T[], int TSize)
{
    if (TSize>SSize)
    {
        return -1;
    }

    short skip[256];
    int i;
    for(i = 0; i < 256; i++)
    {
        skip[i]=TSize;
    }
    for(i = 0; i<TSize - 1; i++)
    {
        skip[T[i]] = TSize - i - 1;
    }


    int pos = 0;
    while(pos <=SSize - TSize)
    {
        int j = TSize -1;
        while(j >= 0 && S[pos + j] == T[j])
        {
            j--;
        }
        if(j < 0 )
        {
            break;
        }
        pos = pos + skip[S[pos + TSize -1]];
    }
    return pos;
}

int main()
{
    char S[m];
    char T[n];
    int i,j;
    cout<<"请输入需要匹配的字符串:"<<endl;
    cin.getline(S,m-1);
    for(i=0;S[i]!=0;i++);
    cout<<"需要匹配的字符串的长度为"<<i<<endl;
    cout<<"请输入模板字符串:"<<endl;
    cin.getline(T,n-1);
    for(j=0;T[j]!=0;j++);
    cout<<"模板字符串的长度为"<<j<<endl;
    int k;
    k=HorspoolMatch(S,i,T,j);
    if(k==-1)
        cout<<"匹配失败"<<endl;
    else
        cout<<"匹配成功,匹配成功的位置为\n"<<k+1<<endl;
    return 0;
}
搜索更多相关主题的帖子: include return 
2015-05-31 14:22
一条沙丁鱼
Rank: 1
等 级:新手上路
威 望:1
帖 子:44
专家分:7
注 册:2015-4-5
收藏
得分:0 
没有大神知道是什么意思吗?我单步跟程序下来,发现skip中存储的是模板字符串的长度,但是删除它之后运行就不对了,改小数组大小也运行不对。它存在的意义在哪里?
2015-06-07 09:36
林月儿
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:湖南
等 级:版主
威 望:138
帖 子:2277
专家分:10647
注 册:2015-3-19
收藏
得分:11 
程序代码:
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;
const int m=100;                         //额。。。 
const int n=50;
//123456
//23
//skip:5432
int HorspoolMatch(char S[], int SSize,char T[], int TSize)
{
    if (TSize>SSize)
    {
        return -1;
    }

    short skip[256];
    int i;
    for(i = 0; i < 256; i++)
    {
        skip[i]=TSize;
    }                                                 
    for(i = 0; i<TSize - 1; i++)
    {
        skip[T[i]] = TSize - i - 1;               //######## 
    }
                                           //以上过程导致skip存储了模板下标值n-2到1(n为模板长度) 

    int pos = 0;
    while(pos <=SSize - TSize)              //当pos下标超过 SSize - TSize就不用继续如:1234找23,pos到3位置就停止继续的话,后面子串长度就不满足要求 
    {
        int j = TSize -1;
        while(j >= 0 && S[pos + j] == T[j])      //从pos位置比较遇到不一样的字符或者模板遍历完就停止 
        {
            j--;
        }
        if(j < 0 )                               //正常结束循环就是j<0说明遍历没有中断比较所有pos到pos+TSize位置的字符满足条件 跳出 
        {                                        //循环(外循环)返回pos 
            break;
        }
        pos = pos + skip[S[pos + TSize -1]];     //这里 内循环的退出条件是中途比较失败,pos加步长 
    }                                              //skip[S[pos + TSize -1]]联系 #######标记处附近分析过程,这里选择变步长目的是减少循环步骤具体过程可结合实例分析 
    return pos;
} 

int main()
{
    char S[m];
    char T[n];
    int i,j;
    cout<<"请输入需要匹配的字符串:"<<endl;
    cin.getline(S,m-1);
    for(i=0;S[i]!=0;i++);
    cout<<"需要匹配的字符串的长度为"<<i<<endl;
    cout<<"请输入模板字符串:"<<endl;
    cin.getline(T,n-1);
    for(j=0;T[j]!=0;j++);
    cout<<"模板字符串的长度为"<<j<<endl;
    int k;
    k=HorspoolMatch(S,i,T,j);
    if(k==-1)
        cout<<"匹配失败"<<endl;
    else
        cout<<"匹配成功,匹配成功的位置为\n"<<k+1<<endl;
    return 0;
}

剑栈风樯各苦辛,别时冰雪到时春
2015-06-07 11:07
一条沙丁鱼
Rank: 1
等 级:新手上路
威 望:1
帖 子:44
专家分:7
注 册:2015-4-5
收藏
得分:0 
回复 3楼 林月儿
不是吧,我单步跟程序出来,发现skip中一直存储着是模板的长度啊,就按你的例子,123456和23,skip中一直跟着是2啊
2015-06-11 23:31
快速回复:horspool算法问题,代码没问题,就是不太明白Horspool-Match函数的语句 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032885 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved