#include<stdio.h>
#include<string.h>
//unsigned short jump(char c);
int search(char*, char*);
int char_index(char,char*);
int main(void)
{
//char* pattern = "norn";
//char* pattern = "grow";
//char* pattern = "corn";
char* pattern = "door to door";
//char* target = "okas from acornorn grow";
char* target = "he went door to door";
printf("%s\n",search(pattern,target)?"find":"not find");
return 0;
}
int char_index(char c, char* pattern)
{
char* tmp = pattern;
while(*tmp){
if(*tmp == c){
return tmp-pattern+1;
}
tmp++;
}
return 0;
}
/**
* Boyer-Moore fast string searching algorithm
*/
int search(char* pattern, char* target)
{
int len = strlen(pattern);
//int jump = 0;
// 如果cur指向的字符不等于pattern的最后一个字符,则cur右移pattern的长度个字符
while(*cur){ // 如果cur指向的字符等于pattern的最后一个字符,那么依次比较cur-1和pattern的倒数第二个字符,
// 如果仍然相同,依次类推,如果pattern中的字符全部被匹配,那么匹配成功
if(*cur != pattern[len-1]){ // 如果迭代过程中出现字符不匹配的情况,那cur指针么依据被查找串中不匹配的字符在pattern中的位置移动
cur += (len-char_index(*cur, pattern)); // 如果被查找串中不匹配的字符不在pattern中,那么cur移动pattern的长度个位置
}else{ // 如果被查找串中不匹配的字符在pattern中,那么cur先指向该字符,然后移动的距离 = 该字符在pattern中的位置到pattern末尾的距离
int i = 1;
printf("\n%c",*cur);
while(1){
//字符在pattern中的位置到pattern末尾的距离 == 被查找串移动的距离
if(*(cur-i) == pattern[len-1-i]){
printf("%c",*(cur-i));
if(i++ == len-1){
printf("\n");
printf("from position %d\n", cur-target-(len-1));
return 1;
}
}else{
cur -= i;
break;
}
}
}
}
return 0;
}
分享到:
相关推荐
在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上,提出了一种更加快速的串匹配算法Quick Boyer-Moore(QBM)。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置...
这事boyer-moore算法的C语言编程实现,该算法实现字符串的匹配和定位
很多的网上Boyer-Moore算法比较不全,本人上传的Boyer-Moore算法相当完整,界面也会美观,只要有vs2010运行即可。
用Boyer-Moore实现字符串匹配问题。算法中有坏字符移动表和好后缀移动表的创建方法。代码有注视供参考。
Boyer-Moore字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串(关键字)进行预处理,而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小...
boyer-moore算法的c#描述,可以方便的实现模式匹配
boyer-moore的算法实现,希望有所帮助
Boyer-Moore字符串搜索算法.ppt
使用Boyer-Moore-Horspool-Sunday 算法进行字符串匹配的系列函数
比Boyer-Moore更快的字符串查找算法
Boyer-moore-string-search 在C中的实现。 该算法从右到左向后执行匹配,并通过迭代匹配,模式移位,匹配,移位等进行操作。移位量是通过应用以下两个规则来计算的: 不良品格规则良好的后缀规则实际的偏移量是其中...
cpp代码-boyer-Moore算法实现
usage:四种字符串匹配算法的实现(Sunday、KMP、Boyer-Moore、horspool)的测试 各文件说明: search_string.h 头文件,包含了对各个函数的声明; search_string.c 包含了头文件中所有函数的具体实现; search_...
%% Boyer-Moore 多数投票算法% Boyer-Moore Vote Algorithm 解决了多数票问题% 线性时间 O(n) 和对数空间 O(\log n)。 多数票% 问题是确定在任何给定的选择序列中% 有一个选择出现次数比所有其他选择都多,如果是...
streamsearch是的模块,它允许使用Boyer-Moore-Horspool算法搜索流。 该模块主要基于的Hongli Lai的Streaming Boyer-Moore-Horspool C ++实现。 要求 -v0.8.0或更高版本 安装 npm install streamsearch 例子 var...
(1)"好后缀"的位置以最后一个字符为准 (2)如果"好后缀"在搜索词中只出现一次,则它的上一次出现位置为 -1 (3)如果"好后缀"有多个,则除了最长的那个
核心算法基于Boyer-Moore字符串搜索算法,并基于此算法在大型文件上执行快速搜索,支持多种选项,从而进一步提高了查找所需内容的机会。 概述 相对搜索是一种用于查找常规方法无法找到的数据的方法。 不同之处在于...
Boyer-Moore字符串匹配 出于教育目的,Boyer-Moore字符串匹配算法的Rust实现。 我先前的Python实现(作为学术项目的一部分)可以在找到。 该可视化在支持ANSI转义序列的终端上起作用。 还需要支持Unicode字符的字体...