Chinaunix

标题: LINUX内核中的BM算法函数有API可以用不？【已解决】 [打印本页]

作者: zuii 时间: 2009-05-16 15:45
标题: LINUX内核中的BM算法函数有API可以用不？【已解决】
不知道怎样才能直接调用bm_find函数，大家给点提示？谢了先

说明看这里：http://blog.chinaunix.net/u1/53217/showart_1934058.html

代码：

/*
* the boyer-moore algorithm
* for text search of rules cotent
* by zuii||williamzuii@163.com
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BM_TEST

#define LEN 256

/*
* BMMatch()
* match once for each call,if match succeed,return 0
* or else,return the index for the next match
*
*/
int BMMatch(const char *src,const char *pattern,int idx,int po[])
{
const int slen=strlen(src);
int i=strlen(pattern)-1;
int j=idx+i;
int nidx;

if(j > slen)
      return -1;

for(;i>=0;i--,j--){
      if(src[j] != pattern[i])
         break;
}

if(i < 0)
      return 0; /* match succeed */
else if(po[src[j]] > 0) /* the charector is contained in pattern */
      nidx=idx+(i-po[src[j]]);
else /* the charector is not contained in pattern */
      nidx=idx+i+1;

return nidx;
}

/*
* BMSearch()
* --- the interface of the text search algorithm---Boyer-moore
* Arguments:
*    src:the long text for matching with pattern
*    pattern: the pattern text use to match with src
*    n: the beginning char for matching in src
* Return:
*    0: matching succeed
*    -1:matching failed
*/
int BMSearch(const char *src,const char *pattern,int n)
{
int po[LEN]={0};
int i,idx=-2,nidx=n;
int plen=strlen(pattern);
if((n+strlen(pattern)) > strlen(src)){
      printf("Ivalid search!\n");
      return -1;
}

/* assistant array */
for(i=0;i < plen;i++)
      po[pattern[i]]=i;

/* the first time to match */
idx=BMMatch(src,pattern,n,po);

/* start looping */
while(idx != -1 && idx != 0){
      nidx=idx;
      idx=BMMatch(src,pattern,nidx,po);
}

/* return 0 or -1 */
return idx;
}

#ifdef BM_TEST
int main(int argc,char **argv)
{
if(BMSearch("it's a test!Oh yeah!","test",4) == 0){
      printf("Succeed!\n");
}else{
      printf("No content!\n");
}

//getch();

return 0;
}
#endif

[ 本帖最后由 zuii 于 2009-5-20 20:08 编辑 ]

作者: zuii 时间: 2009-05-16 18:50
天呢，怎么都没人理啊？

作者: zx_wing 时间: 2009-05-16 23:45

原帖由 zuii 于 2009-5-16 15:45 发表
不知道怎样才能直接调用bm_find函数，大家给点提示？谢了先

我没用过，帮你看你了一下，你无法直接用。
内核BM的实现时作为module实现提供给textsearch用的，你只能通过textsearch提供出的接口间接调用，textsearch.c最上面的注释已经告诉你怎么用了。例如：
* conf = textsearch_prepare("bm", pattern, strlen(pattern),
* GFP_KERNEL, TS_AUTOLOAD);

这里第一个参数"bm"指定search时使用BM算法

作者: zuii 时间: 2009-05-17 15:17
先谢谢。。。马上试试

作者: zuii 时间: 2009-05-20 20:06
解决咯。。。网上找了代码然后自己修改了，改出来一个API 呵呵。。。拿出来需要的朋友可以研究下...

作者: flyfrogs 时间: 2011-10-31 18:04
谢谢楼主分享，
09年到现在很久了，楼主的代码运行可良好？

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)