Electronic Joint Business

Solution for E-Business

字符串查找算法 (一)暴力查找算法(BF)

对数据库开发和文本处理软件而言,字符串匹配(String matching)可谓至关重要。幸运的是,在所有的现代程序设计语言和代码库中,字符串处理函数比比皆是,它们对我们的日常工作大有裨益。字符串算法主要可分为几大类。字符串查找就是其中之一,我们要做的就是回答此模式串是否在文本中出现过。 概述 进行字符串查找时,最基本的方法就是“暴力(brute force)”法,通常来说,所有名字里含有“暴力(brute force)”二字的算法都很慢。 暴力算法核心思想是:T 是长度为 N 文本串,P 是长度为 M 模式串。 首先将 S[1] 和 P[1] 比较,若相等,则再比较 S[2] 和 P[2],如果一直到P[M]为止等相等,则匹配成功;若 S[1] 和 P[1] 不等,则 P 向右移动一个字符的位置,再依次进行比较。这意味着需要检查文本中的每个字符与模式串(通常比文本短)的匹配情况。。算法是效率最低的算法。 该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M*N)。 图解 暴力字符串匹配的原理十分简单。我们必须检查文本(text)的首字符与模式串(pattern)的首字符是否匹配,如下图所示。 要是它们不匹配,我们就后移至文本的第二个字符。然后拿文本的第二字符与模式串的首字符相比较。要是它们又不匹配,我们就继续后移,直到获得匹配,或是达到文本的末端为止。 如果它们相匹配,我们就后移至模式串的第二字符,拿它与文本的“下一”字符相比较, 显然不能仅因为找到文本中的某一字符与模式串的首字符相匹配,就说文本里有模式串。我们必须后移,以便确认文本中是否包含整个模式串。 实现 char* BruteSearch(const char* text,const char * pattern) {    int len = strlen(pattern);    for( ; *text ; text ++)   […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.