/*优于KMP算法的 BM改进算法——SUNDAY算法*/
例:
Hello, world. There is a word! No, it's two word.
word
H不等于w,patt移动。src[i+ patt_len]为o,next[‘o’]为4,移动四步到’o’。o不等于w,patt再移动4为o。o不等于w,再次移动到There前面的空格那,src[i + patt_len]为’r’,next[‘r’]为2,移动两步到’h’,再移动->’ ’->’a’,next[‘r’]为2。patt移动w,之后的o、r、d都匹配了。
-
#include <stdio.h>
-
#include <string.h>
-
-
void SUNDAY(char*src, char *patt)
-
{
-
size_t patt_len = strlen(patt),src_len = strlen(src);
-
size_t next[256], i, m, match_len,succ = 0;
-
char*match_str;
-
-
for(i=0;i<256; i++) //初始化next数组
-
{
-
next[i] = patt_len + 1;
-
}
-
for(i=0;i<patt_len; i++) //匹配到patternstring中的某个字符需要往后移动的步数
-
{
-
next[patt[i]] = patt_len - i;
-
}
-
-
m = src_len - patt_len + 1;
-
for(i=0;i<m; i += next[src[i + patt_len]]) //根据src[i+ patt_len]这个字符判断移动的步数
-
{
-
if(src[i]== *patt)
-
{
-
match_str = src + i + 1;
-
match_len = 1;
-
do
-
{
-
if(match_len== patt_len)
-
{
-
printf("Match at %dn", i);
-
succ = 1;
-
break;
-
}
-
}
-
while(*match_str++== patt[match_len++]);
-
}
-
}
-
if(!succ)
-
{
-
printf("Hasnot matchn");
-
}
-
}
-
-
int main()
-
{
-
charsrc[100] = "Hello, world. There is a word! No, it's two word.";
-
charpatt[10] = "word";
-
SUNDAY(src, patt);
-
return0;
-
}
2011-05-12 20:24 发表于百度空间,今搬至CU。
阅读(724) | 评论(0) | 转发(0) |