转自:http://blog.csdn.net/wincol/article/details/4795369
我想说一句“我日,我讨厌KMP!”。
KMP虽然经典,但是理解起来极其复杂,好不容易理解好了,便起码来巨麻烦!
老子就是今天图书馆在写了几个小时才勉强写了一个有bug的、效率不高的KMP,特别是计算next数组的部分。
其实,比KMP算法速度快的算法大把大把,而且理解起来更简单,为何非要抓住KMP呢?笔试出现字符串模式匹配时直接上sunday算法,既简单又高效,何乐而不为?
说实话,想到sunday算法的那个人,绝对是发散思维,绝对牛。当我在被KMP折磨的够呛的时候,我就琢磨,有没有别的好算法呢??琢磨了半天也没想出个所以然来。笨啊,脑子不够发散。
下面贴上一位兄弟写的算法总结,很简单(建议KMP部分就不用看了,看了费脑子)。
参见:http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html
趁着做Presentation的功夫,顺便做一个总结
字符串匹配:
---willamette
在匹配串中寻找模式串是否出现,注意和最长公共子序列相区别(LCS: Longest Common Substring)
-: Brute Force(BF或蛮力搜索) 算法:
这是世界上最简单的算法了。
首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。
速度最慢。
那么,怎么改进呢?
我们注意到Brute Force 算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢?
当然是可以的。
我们也注意到,Brute Force 是很不intelligent 的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^
注意,蛮力搜索算法虽然速度慢,但其很通用,文章最后会有一些更多的关于蛮力搜索的信息。
-: KMP算法
首先介绍的就是KMP 算法。
原始论文:Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.
这个算法实在是太有名了,大学上的算法课程除了最笨的Brute Force 算法,然后就介绍了KMP 算法。也难怪,呵呵。谁让Knuth D.E. 这么world famous 呢,不仅拿了图灵奖,而且还写出了计算机界的Bible <The Art of Computer Programming>( 业内人士一般简称TAOCP).稍稍提一下,有个叫H.A.Simon 的家伙,不仅拿了Turing Award ,顺手拿了个Nobel Economics Award ,做了AI 的爸爸,还是Chicago Univ 的Politics PhD ,可谓全才。
KMP 的思想是这样的:
利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离
比如
模式串ababac 这个时候我们发现在c 处不匹配,然后我们看c 前面那串字符串的最大相等前后缀,然后再来移动
下面的两个都是模式串,没有写出来匹配串
原始位置 ababa c
移动之后 aba bac
因为后缀是已经匹配了的,而前缀和后缀是相等的,所以直接把前缀移动到原来后缀处,再从原来的c 处,也就是现在的第二个b 处进行比较。 这就是KMP 。
-:Horspool算法
Horspool 算法。
当然,有市场就有竞争,字符串匹配这么大一个市场,不可能让BF 和KMP 全部占了,于是又出现了几个强劲的对手。
第一个登场的是
论文:Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506
Horspool 算法的思想很简单的。不过有个创新之处就是模式串是从右向左进行比较的。很好很强大,为后来的算法影响很大。
匹配串:abcbc sdxzcxx
模式串:cbcac
这个时候我们从右向左进行对暗号,c-c ,恩对上了,第二个b-a ,不对啊,我们应该怎么办?难道就这么放弃么。于是,模式串从不匹配的那个字符开始从右向左寻找匹配串中不匹配的字符b 的位置,结果发现居然有,赶快对上赶快对上,别耽误了。
匹配串:abcbcsd xzcxx
模式串: cbcac
然后继续从最右边的字符从右向左进行比较。这时候,我们发现了,d-c 不匹配啊,而且模式穿里面没有噢,没办法,只好移动一个模式串长度的单位了。
匹配串:abcbcsdxzcxx
模式串: cbcac
-:Boyer-Moore算法
第二个上来的是Boyer-Moore 算法。
是一个很复杂的算法,当然,虽然理论上时间复杂度和KMP 差不多,但是实际上却比KMP 快数倍,可见实践是检验真理的唯一标准。
原始论文:R.S.Boyer, J.S.Moore, A fast string searching algorithm , Communications of the ACM,20(10):762-772 ,1977
分为两步预处理,第一个是bad-character heuristics ,也就是当出现错误匹配的时候,移位,基本上就是做的Horspool 那一套。
第二个就是good-suffix heuristics ,当出现错误匹配的时候,我还要从不匹配点向左看啊,以前匹配的那段子字符串是不是在模式串本身中还有重复的啊,有重复的话,那么我就直接把重复的那段和匹配串中已经匹配的那一段对齐就是了。再比较
匹配串:abaccba bbazz
模式串:cbadcba
我们看到已经匹配好了cba ,但是c-d 不匹配,这个时候我们发现既可以采用bad-character heuristics ,也可以使用good-suffix heuristics( 模式串:cba dcba ) ,在这种情况下,邪不压正。毅然投奔good 。移动得到
匹配串:abaccbabbaz z
模式串: cbadcba
可是,我们有时候也发现,已经匹配好的那一部分其实并没有再有重复了的啊。这个时候,我们发现已经匹配好的那串字符串有一部分在开头重新出现了,那么,赶快,对齐吧。
匹配串:abacccb bbazz
模式串:cbadccb
然后得到
匹配串:abacccbbbazz
模式串: cbadccb
当两种Good-Suffix 出现的时候,取移动距离最大的那个。
(
对于BM算法,好规则和坏规则,这里讲的不够明确,下面推荐一个讲解非常优秀的文章,可谓图文并茂啊,而且还是个MM写的。
Boyer-Moore 经典单模式匹配算法
http://blog.csdn.net/iJuliet/archive/2009/05/19/4200771.aspx
)
-:Sunday算法
最后一个是Sunday 算法,实际上比Boyer-Moore 还快,呵呵。长江后浪推前浪。
原始论文:Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990
看原始论文的题目,D.M. Sunday 貌似是故意想气气Boyer-Moore 两位大牛似的。呵呵。不过实际上的确Sunday 算法的确比BM 算法要快,而且更简单。
Sunday 的算法思想和Horspool 有些相似,但是。当出现不匹配的时候,却不是去找匹配串中不匹配的字符在模式串的位置,而是直接找最右边对齐的右一位的那个字符在模式串的位置。
比如:
匹配串:abcbc zdxzc
模式串:zbcac
恩,这里我们看到b-a 没有对上,我们就看匹配串中的z 在模式串的位置,然后,嘿嘿。
匹配串:abcbczdxzc
模式串: zbcac
如果模式串中的没有那个字符怎么办呢?很简单,跳过去呗。
匹配串:abcbc edxzcs
模式串:zbcac
e 不在模式串中出现
那么我们就
匹配串:abcbcedxzcs
模式串: zbcac
(2009/10/20补充)
RK算法
某一天在图书馆的一本算法分析设计书上翻到的。思路很新颖!和大家分享下。
在串匹配的简单算法中,把文本每m个字符构成的字符段作为一个字段,和模式进行匹配检查。如果能对一个长度为m的字符
串赋以一个Hash函数。那么显然只有那些与模式具有相同hash函数值的文本中的字符串才有可能与模式匹配,这是必要条件
,而没有必要去考虑文本中所有长度为m的字段,因而大大提高了串匹配的速度。因此RK算法的思想和KMP,BM,Sunday等思
路迥然不同!
(事实上,之前的串匹配方法,是将模式串的一个一个字符作为小的特征去分别进行匹配,而RK算法则是将串整体作为一个
特征!难就难在单个字符的特征很容易想得到,整体作为一个特征就没那么容易想得到了)
如果把整体作为一个特征,那么如何快速的求出这个整体特征的特征值??
模式串的特征值仅需求一次即可。对于文本中的任意m个字符构成的字串如何快速的求特征就是个难点了。
抛砖引玉,这里给出一个简单的特征计算。 将字符串的每一个字符看做一个数,那么这个字符串的就是一个数字数组,通
过积分向量可以快速任意一个长度子字符串的向量和。可以把字符串的对应的字符数组的元素和看做这个字符串整体特征。
这个特征是可以再O(1)的时间内求出的。其实原始的RK算法里面是把字符串看做一个26进制数在计算特征的。这里就不啰
嗦了,有兴趣的可以深入查找
aabsee sds 模式串 ees
ees
发现 see向量和 == ees的向量和
然后就对see和ees做逐个字符的比较。发现不匹配继续往下走
aabsees ds 模式串 ees
ees
发现 ees向量和 == ees的向量和
然后就对ees和ees做逐个字符的比较。发现匹配OK。
另外还有 字符串匹配自动机 后缀树算法(分在线和非在线两种)等 见如下文章。不能说那个比那个更好,各个算法都有自己的优势及最佳应用场合。参考:
http://blog.csdn.net/yifan403/archive/2009/06/16/4272793.aspx
另外,关于多模式字符串匹配 有AC算法(字符串匹配自动机思想) WM算法(BM在多模式的推广应用)
参考:
http://blog.csdn.net/ijuliet/category/498465.aspx 该女子的blog有很多好文章。
/**********************华丽分割线******************************/
附上sunday代码:
http://hi.baidu.com/kmj0217/blog/item/6f837f2f3da097311e3089cb.html
|
|
|
// 第三个代码实现,貌似比较高效
http://hi.baidu.com/azuryy/blog/item/10d3d3460b97af0e6b63e5cd.html
头文件定义:
/* Sunday.h */
class Sunday
{
public:
Sunday();
~Sunday();
public:
int find(const char* pattern, const char* text);
private:
void preCompute(const char* pattern);
private:
//Let's assume all characters are all ASCII
static const int ASSIZE = 128;
int _td[ASSIZE] ;
int _patLength;
int _textLength;
};
源文件
/* Sunday.cpp */
Sunday::Sunday()
{
}
Sunday::~Sunday()
{
}
void Sunday::preCompute(const char* pattern)
{
for(int i = 0; i < ASSIZE; i++ )
_td[i] = _patLength + 1;
const char* p;
for ( p = pattern; *p; p++)
_td[*p] = _patLength - (p - pattern);
}
int Sunday::find(const char* pattern, const char* text)
{
_patLength = strlen( pattern );
_textLength = strlen( text );
if ( _patLength <= 0 || _textLength <= 0)
return -1;
preCompute( pattern );
const char *t, *p, *tx = text;
while (tx + _patLength <= text + _textLength)
{
for (p = pattern, t = tx; *p; ++p, ++t)
{
if (*p != *t)
break;
}
if (*p == 0)
return tx-text;
tx += _td[tx[_patLength]];
}
return -1;
}
简单测试下:
int main()
{
char* text = "blog.csdn,blog.net";
char* pattern = "csdn,blog" ;
Sunday sunday;
printf("The First Occurence at: %d/n",sunday.find(pattern,text));
return 1;
}
////////////////////////////////////////////
strstr的实现。
需要说明的是strstr是C语言提供的使用Brute Force实现的字符串匹配,简单、通用是其最大的优点。时间复杂度是O(mn)
// 下面是Microsoft的实现
//经典算法
//比KMP算法简单,没有KMP算法高效
char * __cdecl strstr (
const char * str1,
const char * str2
)
{
char *cp = (char *) str1;
char *s1, *s2;
if ( !*str2 )
return((char *)str1);
while (*cp)
{
s1 = cp;
s2 = (char *) str2;
while ( *s1 && *s2 && !(*s1-*s2) )
s1++, s2++;
if (!*s2)
return(cp);
cp++;
}
return(NULL);
}
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/whoismickey/archive/2009/02/08/3869367.aspx
strstr
下载strstr和测试程序 ,
下载后执行 :
unzip testStrstr.zip
cd testStrstr
make test
相关推荐
各种字符串匹配方法的总结,通俗易懂,五脏俱全
第一部分、KMP算法初解 1、普通字符串匹配BF算法与KMP算法的时间复杂度比较 2、BF算法与KMP算法的区别 3、BF算法为什么要回溯 4、KMP 算法思想 5、next数组的含义 第二部分、next数组求法的来龙去脉与KMP算法的源码
本文给大家介绍的是C++实现字符串匹配的暴力算法,蛮力解法意味着我们需要检查每一个文本串中的字符是否和匹配串相匹配,在文本量不大的情况下还是可以得到很好的效果,所以蛮力法的字符串匹配仍然是得到了实际生活...
实验二 串模式匹配算法(串实验) 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法...
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数: ...
10种排序算法总结.doc
该算法通过中文主动干扰技术有效地避开了目前经典的中文字符串匹配算法存在的问题,使得包含这类算法的内容安全过滤/网络入侵检测手段失效,完成了恶意夹杂字符的中文关键词匹配。结果表明,用柔性中文字符串匹配...
1、传统的字符串匹配算法 /* * 从s中第sIndex位置开始匹配p * 若匹配成功,返回s中模式串p的起始index * 若匹配失败,返回-1 */ int index(const std::string &s, const std::string &p, const int sIndex = 0)...
网上大神的总结,从trie树谈到后缀树,常用的字符串匹配算法
两年ACM竞赛所有算法总结,这里包含最短路、最小生成树、动态规划、字符串匹配、博弈、大数、Hash、排序、二分匹配、并查集、最大流、欧拉函数、扩展欧几里得等
基本的字符串位置查找方法 Python 查找字符串使用 变量....朴素匹配算法是对目标字符串和模板字符串的一一匹配。如果匹配得上,下标向右移一位, 否则清空并重新开始匹配。 target = 'abb aba' pattern = 'aba' def ma
1.串匹配问题 给定一段文本,在该文本中查找并定位任意给定字符串。 要求: (1)实现BF算法; (2) 实现BF算法的改进算法:KMP算法 2.采用分治法求解最大连续子序列和问题 给定一个有n(n≥1)个整数的序列...
[原网页] 程序员编程艺术第三十~三十一章:字符串转换成整数,通配符字符串匹配 [原网页] 程序员编程艺术第二十八~二十九章:最大连续乘积子串、字符串编辑距离 [原网页] 数据挖掘中所需的概率论与数理统计知识、...
本文给大家介绍的是C++实现two sum问题的暴力算法,蛮力解法意味着我们需要检查每一个数字与后面是否可以组成target,在数字量不大的情况下还是可以得到很好的效果,所以蛮力法的字符串匹配仍然是得到了实际生活中的...
本次课程设计为了巩固上学期在软件安全课程上所学的安全知识,包括堆栈溢出、整数溢出等等,同时考察了一些课外的新事物,例如字符串匹配与CFG控制流程图的同源性检测。根本目的是让同学们加深对软件安全本门学科的...
KMP算法即字符串匹配算法,C语言中KMP可以避免指针回溯从而达到高效,接下来就来总结一下C语言中实现KMP算法的实例讲解
简介:这份资源是我以前偶然...递归,拷贝一个目录或者文件到指定路径下,简单的txt转换xml,字母排序(A-Z)(先大写,后小写),列出某文件夹及其子文件夹下面的文件,并可根据扩展名过滤,字符串匹配的算法,写入日志。
| KARP-RABIN 字符串匹配 32 | 基于 KARP-RABIN 的字符块匹配 32 | 函数名: STRSTR 32 | BM 算法的改进的算法 SUNDAY ALGORITHM 32 | 最短公共祖先(两个长字符串) 33 | 最短公共祖先(多个短字符串) 33 ...