bm匹配算法 和kmp匹配算法
1.kmp算法[code] def compute_prefix_function(p): m = len(p) pi = [0] * m k = 0 for q in range(1, m): while k > 0 and p[k] != p[q]: k = pi[k - 1] if p[k] == p[q]: k = k + 1 pi[q] = k return pi def kmp_matcher(t, p): n = len(t) m = len(p) pi = compute_prefix_function(p) q = 0 for i in range(n): while q > ...
by cucugbgb - Python - 2010-11-03 03:54:16 阅读（3637） 回复（1）
其实看看textsearch.c你就清楚了.... #include linux/module.h> #include linux/kernel.h> #include linux/init.h> #include linux/types.h> #include linux/string.h> #include linux/init.h> #include linux/rcupdate.h> #include linux/err.h> #include linux/textsearch.h> static int o_search() { int pos; long err; struct ts_config *conf; struct ts_state state; const char *pattern = "chicken"; const cha...
[code]#!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern: j = pos[j] if pattern[j+1] == pattern: j = j + 1 pos = j return pos def kmp(ss, pattern): pos = next(pattern) ss_len = len(ss) pattern_len = len(pattern) j = -1 for i in range(ss_len): while j > -1 and pattern[j+1] != ss: j ...
字符串匹配是计算机的基本任务之一。 举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？ 许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称kmp）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。 这种算法不太容易理解，网上有很多解释，但读起来都很费劲。直到读到Jake Boxer的文章，我才真正理解这种算法。下面，我用自己的语言，试图...
##coding: utf-8 ##kmp算法是一个快速字符串查找匹配算法 ##思路是: 母串指针i,模式串指针j; ##能匹配时,i,j指针都向前走;不匹配时,i指针不动,j指针回溯 ## if s==m[j]: ## i+=1 ## j+=1 ## else: ## j回溯 ##j指针回溯,也就是模式串向前滑动,滑动距离要尽可能短,以免错过合适的匹配位置 ##(所有的教科书上都说是'尽可能长的距离'; ## 但我经过分析后认为,在保证i指针不动的情况下,滑动的距...
php 实现kmp算法 [code]kmp算法的PHP实现 * * @author zhaojiangwei 2011/10/22 10:28 */ Php代码 1. class kmp{ private $next = NULL; //模式串T的next数组 private $t = NULL; //模式串 private $str = NULL; //主串 public function kmp($str){ $this->str = str_split($str); $this->next = array(); ...
kmp算法是一种用于字符串匹配的算法,这个算法的高效之处在于当在某个位置匹配不成功的时候可以根据之前的匹配结果从模式字符串的另一个位置开始,而不必从头开始匹配字符串. 因此这个算法的关键在于,当某个位置的匹配不成功的时候,应该从模式字符串的哪一个位置开始新的比较.假设这个值存放在一个next数组中,其中next数组中的元素满足这个条件:next[j] = k,表示的是当模式字符串中的第j + 1个(这里是遵守标准C语言中数组元素从0开始...
#include "stdafx.h" #include "iostream.h" #include "stdio.h" #define Null 0 //定义串的链存储结构 typedef struct Chuck{ char ch; struct Chuck *next; }Chuck; typedef struct { Chuck *head,*tail; int length; }Hstring; void init_Hstring(Hstring &T); //删除pos结点后面length长度的字符串 void delete_pos(Hstring &S,Chuck *pos,int length); //pos结点后面插入length长度的字符串 void insert_pos(Hstring &...
