精华内容
下载资源
问答
  • 多模式字符串匹配算法---ac算法

    千次阅读 2015-03-27 09:54:46
    AC算法是Alfred V.Aho(《编译原理》(龙书)的作者),和Margaret J.Corasick于1974年提出(与KMP算法同年)的一个经典的多模式匹配算法,可以保证对于给定的长度为n的文本,和模式集合P{p1,p2,...pm},在O(n)时间...

    AC算法是Alfred V.Aho(《编译原理》(龙书)的作者),和Margaret J.Corasick于1974年提出(与KMP算法同年)的一个经典的多模式匹配算法,可以保证对于给定的长度为n的文本,和模式集合P{p1,p2,...pm},在O(n)时间复杂度内,找到文本中的所有目标模式,而与模式集合的规模m无关。正如KMP算法在单模式匹配方面的突出贡献一样,AC算法对于多模式匹配算法后续的发展也产生了深远的影响,而且更为重要的是,两者都是在对同一问题——模式串前缀的自包含问题的研究中,产生出来的,AC算法从某种程度上可以说是KMP算法在多模式环境下的扩展。,如果要用KMP算法匹配长度为n的文本中的m个模式,则需要为每一个模式维护一个next跳转表,在执行对文本的匹配过程中,我们需要关注所有这些next表的状态转移情况,这使得时间复杂度增长为O(mn),对于较大的模式集合来说,这样的时间增长可能是无法接受的。AC算法解决了这一问题,通过对模式集合P的预处理,去除了模式集合的规模对匹配算法速度的影响。

    要理解AC算法,仍然需要对KMP算法的透彻理解。这里我们还是以KMP算法中的老例子来说明前缀自包含如何在AC算法中发挥作用。对于模式串"abcabcacab",我们知道非前缀子串abc(abca)cab是模式串的一个前缀(abca)bcacab,而非前缀子串ab(cabca)cab不是模式串abcabcacab的前缀,根据此点,我们构造了next结构,实现在匹配失败时的跳转。而对于多模式环境,这个情况会发生一定的变化。这里以AC论文中的例子加以说明,对于模式集合P{he,she,his,hers},模式s(he)的非前缀子串he,实际上却是模式(he),(he)rs的前缀。如果目标串target[i...i+2]与模式she匹配,同时也意味着target[i+1...i+2]与he,hers这两个模式的头两个字符匹配,所以此时对于target[i+3],我们不需要回溯目标串的当前位置,而直接将其与he,hers两个模式的第3个字符对齐,然后直接向后继续执行匹配操作。

    经典的AC算法由三部分构成,goto表(转移表),fail表(失效表)和output表(输出表),goto表是由模式集合P中的所有模式构成的状态转移自动机,以上面的集合为例,其对应的goto结果如下,其中圆圈对应自动机的各个状态,边对应当前状态输入的字符。


    对于给定的集合P{p1,p2,...pm},构建goto表的步骤是,对于P中的每一个模式pi[1...j](1<=i<m+1),按照其包含的字母从前到后依次输入自动机,起始状态D[0],如果自动机的当前状态D[p],对于pi中的当前字母pi[k](1<=k<=j),没有可用的转移,则将状态机的总状态数smax+1,并将当前状态输入pi[k]后的转移位置,置为D[p][pi[k]] = smax,如果存在可用的转移方案D[p][pi[k]]=q,则转移到状态D[q],同时取出模式串的下一个字母pi[k+1],继续进行上面的判断过程。这里我们所说的没有可用的转移方案,等同于转移到状态机D的初始状态D[0],即对于自动机状态D[p],输入字符pi[k],有D[p][pi[k]]=0。理论介绍很繁琐,让我们以之前的模式集合P{he,she,his,hers}说明一下goto表的构建过程。

    第一步,将模式he加入goto表:


    第二步,将模式she加入goto表:


    第三步,将模式his加入goto表:


    第四步,将模式hers加入goto表:


    对于第一和第二步而言,两个模式没有重叠的前缀部分,所以每输入一个字符,都对应一个新状态。第三步时,我们发现,D[0][p3[1]]=D[0]['h']=1,所以对于新模式p3的首字母'h',我们不需要新增加一个状态,而只需将D的当前状态转移到D[1]即可。而对于模式p4其前两个字符he使状态机转移至状态D[2],所以其第三字符对应的状态D[8]就紧跟在D[2]之后。

    goto表构建完成之后,我们就要构建fail表,所谓的fail表就是当我们处在状态机的某个状态D[p]时,此时的输入字符c使得D[p][c]=0,那么我们应该转移到状态机的哪个位置来继续进行呢。以输入文本"shers"为例,当输入到字母e时,我们会发现匹配模式(she)rs,对应与状态机的状态D[5],然后输入字母r,此时我们发现D[6]['r']=0,对于字母r D[6]不存在有意义的跳转。此时我们不能跳转回状态D[0],这样就会丢掉可能的匹配s(hers)。我们发现s(he)的后缀he是模式(he)rs的一个前缀,所以当匹配模式she时,实际也已经匹配了模式hers的前缀he,此时我们可以将状态D[6]转移到hers中的前缀he在goto表中的对应状态D[2]处,再向后执行跳转匹配。这一跳转,就是AC算法中的fail跳转,要实现正确的fail跳转,还需要满足一系列条件,下面会逐一说明。

    对于模式串she,其在字母e之后发生了匹配失败,此时其对应的模式串(回溯到状态D[0])就是she。对于she来说,它有两个包含后缀(除字符串自身外的所有后缀),he和e,对于后缀he,将其输入自动机D,从状态D[0]可以转移到状态D[2],对于后缀e,没有可行的状态转移方案。所以对于状态D[5],如果对于新输入的字符c没有可行的转移方案,我们可以跳转到状态D[2],考察D[2][c]是否等于0.

    AC两人在论文中举出的例子,并不能涵盖在构建fail时遇到的所有情况,这里特别说明一下。前面我们说过,对于she的包含后缀e,没有可行的转移方案,此时如果模式串中还包含一个模式era,那么D[5]可不可以转移到状态D[10]去呢,实际上这是不行的,我们需要找到的是当前所有包含后缀中最长的满足条件者(拗口),如果D[5]对于失败的输入c优先转移到D[10],那么对于文本串shers,很显然会漏掉可能匹配hers,那么什么时机才应该转移到D[10]呢,当我们处理模式串hers时,处理到D[2]时对于之前的输入he,其最长的包含后缀是e,将e输入自动机,可以转移到D[10],所以在D[2]处发生匹配失败的时候才应该转移到D[10]。所以当我们在D[5]处匹配失败时,要先跳转到D[2]如果再没有可用的转移,再跳转到D[10]。


    这个例子同时说明,对于模式集合P的所有模式pi,我们需要处理的不仅是pi的所有包含后缀,而是pi的所有非前缀子串。以模式hers为例,其在2,8,9三个状态都可能发生匹配失败,所以我们要提取出hers的所有非前缀子串(e,er,r,ers,rs,s),然后按照这些子串的末尾字符所对应的自动机状态分组(上例就可以分组为{e}对应状态2,{er,r}对应状态8,{ers,rs,s}对应状态9),然后分别将这些组中的子串从D[0]开始执行状态转移,直到没有可行的转移方案,或者整个序列使状态机最终转移到一个合法状态为止。如果一组中的所有子串都不能使状态机转移到一个合法状态,则这组子串所对应的状态的fail值为0,如果存在可行的状态转移方案,则选择其中最长的子串经过转移后的最终状态,令其对应的组的状态的fail值与其相等。

    举例说明,当我们要处理模式串hers的fail表,假设已经构建好的goto表如前图所示,首先我们需要考察状态2,此时hers的输入字符是he,其所有包含后缀只有e,我们让e从D[0]开始转移,发现成功转移到D[10],所以fail[2]=10。然后我们考察状态8,此时hers的输入字符是her,所有包含后缀为er,r,因为我们要找到可以实现转移的最大包含后缀,所以我们先让er从D[0]开始转移,发现成功转移到D[11],所以fail[8]=11,这是虽然后缀e也可以成功转移到D[10],但是不是当前包含后缀分组中的子串所能实现的最长跳转,放弃。然后我们考察9,此时hers的输入字符串是hers,所有包含后缀为ers,rs,s,我们依次让其执行状态转换,发现s是可以实现转移的最长子串,转移到D[3],所以fail[9]=3。

    我在《KMP算法详解》一文中讲到过一个找当前位置最大包含前缀的笨方法,现在我们构建fail表的方法,就是那一方法在多模式环境下的重新演绎。对于长度为n的模式串p而言,其所有非前缀子串的总数有(n^2-n)/2个,如果将这些子串都要经过状态机执行状态转移,时间复杂度为O(n^3),所以用这种方法,计算包含m个模式的模式集合P的fail表的时间复杂度为O(mn^3),如果包含10000个模式,模式的平均长度为10,计算fail表的运算就是千万级别,严重影响AC算法的实用价值。不过还好Aho,Corasick在自己的论文中同时给出了一个与模式串总长度相关的线性时间算法,可以参考这篇文章,但是这个方法的正确性不那么显而易见。不过这并非就意味着蛮力法就没有什么价值了,蛮力法一方面容易理解,可以为我们探索更高效的算法提供灵感,另一方面也可以帮助我们验证高效算法的正确性。

    最后我们来说一下AC算法中的output表,在构建goto表的过程中,我们知道,状态2,5,7,9是输入的4个模式串的末尾部分,所以如果在执行匹配过程中,达到了如下四个状态,我们就知道对应的模式串被发现了。对于状态机D的某些状态,对应某个完整的模式串已经被发现,我们就用output表来记录这一信息。完成goto表的构建后,D中各状态对应的output表的情况如下:

    2 he

    5 she

    7 his

    9 hers

    但是这并不是我们最终的output表。下面以构建状态5的fail表为例,说明一下fail表的构建是如何影响output表的。首先根据之前我们的介绍,当我们开始计算D[5]的fail值时,我们要将模式she的所有包含后缀提取出来,包括he,e。这里我们需要注意,在output表中,状态5是一个输出状态。当我们用he在状态机中执行转移时,我们会成功转移到2,这里output[2]也是一个输出状态,这就意味着在发现模式串she的同时,实际上也发现了模式串he,所以如果通过某种转换,我们到达了状态5,则意味着我们发现了she和he两个模式,此时fail[5]=2,所以我们需要将output[2]所包含的输出字符串加入到output[5]中。完成goto和fail表构建后,我们所得到的最终output表为:

    2 he

    5 she,he

    7 his

    9 hers

    这实际上是一个后缀包含问题,也就是模式p1实际上是模式p2的后缀,所以当发现模式p2时,p1自然也被发现了。

    AC算法对文本进行匹配的具体步骤是。一开始,将i指向文本text[1...j]的起始位置,然后用text[i]从goto表的状态D[0]开始执行状态跳转。如果存在可行的跳转方案D[0][text[i]]=p,p!=0,则将i增加1,同时转移到状态D[p]。如果不存在可行的转移方案,则考察状态D[p]的fail值,如果fail[p]不等于0,则转移到D[fail[p]],再次查看D[fail[p]][text[i]]是否等于0,直到发现不为0的状态转移方案或者对于所有经历过的fail状态,对于当前输入text[i]都没有非0的转移方案为止,如果确实不存在非0的转移方案,则将i增加1,同时转移到D[0]继续执行跳转。在每次跳转到一个状态D[p]时(fail跳转不算),都需要查看一下output[p]是否指向可输出的模式串,如果有,说明当前位置匹配了某些模式串,将这些模式串输出。

    下面就是一个AC算法的简单示例,由于是示例程序,重在演示实现,所以做了一些简化,这里假设输入字符只包含小写英文字母(26个)。我用了一个二维数组来保存goto表信息,这样可以实现比较直接的跳转,缺点是浪费大量的内存空间。AC算法中goto表状态的数量,可以参考模式中所有的字符数,所以对于上万模式的应用场景,内存空间的占用会很惊人,如何既能存储如此多的状态,又能实现低成本的状态跳转,是一个需要研究的问题,后续我还会专门撰文介绍

    首先是程序中用到的goto,fail,output表结构和几个宏定义。

    1. #define ALPHABET_SIZE  26  
    2. #define MAXIUM_STATES 100  
    3.   
    4. int _goto[MAXIUM_STATES][ALPHABET_SIZE];  
    5. int _fail[MAXIUM_STATES];  
    6. set<string> _out[MAXIUM_STATES];//使用set是因为在生成fail表,同时更新out表过程中,有可能向同一位置多次插入同一个模式串  

    然后是计算goto表的算法。

    1. inline void BuildGoto(const vector<string>& patterns)  
    2. {  
    3.     unsigned int used_states;  
    4.     unsigned int t;  
    5.   
    6.     vector<string>::const_iterator vit;  
    7.     string::const_iterator sit;  
    8.   
    9.     for(vit = patterns.begin(), used_states = 0; vit != patterns.end(); ++vit)  
    10.     {  
    11.         for(sit = vit->begin(), t = 0; sit != vit->end(); ++sit)  
    12.         {  
    13.             if(_goto[t][(*sit)-'a'] == 0)  
    14.             {  
    15.                 _goto[t][(*sit)-'a'] = ++used_states;  
    16.                 t = used_states;  
    17.             }  
    18.             else  
    19.             {  
    20.                 t = _goto[t][(*sit)-'a'];  
    21.             }  
    22.         }  
    23.   
    24.         _out[t].insert(*vit);  
    25.     }  
    26. }  

    然后是计算fail表的算法。

    1. inline void BuildFail(const vector<string>& patterns)  
    2. {  
    3.     unsigned int t, m, last_state;  
    4.     unsigned int s[20];  
    5.   
    6.     vector<string>::const_iterator vit;  
    7.     string::const_iterator sit1, sit2, sit3;  
    8.   
    9.     for(vit = patterns.begin(); vit != patterns.end(); ++vit)  
    10.     {  
    11.         //先要找到输入的单词的各字母对应的状态转移表的状态号,由于状态转移表没有  
    12.         //记录各状态的前驱状态信息,该步暂时无法掠过  
    13.         t = 0;  
    14.         m = 0;  
    15.         sit1 = vit->begin();  
    16.   
    17.         while(sit1 != vit->end() && _goto[t][*sit1 - 'a'] != 0)  
    18.         {  
    19.             t = _goto[t][*sit1 - 'a'];  
    20.             ++sit1;  
    21.             s[m++] = t;  
    22.         }  
    23.   
    24.         for(sit1 = vit->begin() + 1; sit1 != vit->end(); ++sit1)  
    25.         {  
    26.             //此时的[sit2, sit1+1)就是当前模式的一个非前缀子串  
    27.             for(sit2 = vit->begin() + 1; sit2 != sit1 + 1; ++sit2)  
    28.             {  
    29.                 t = 0;  
    30.                 sit3 = sit2;  
    31.   
    32.                 //对该子串在goto表中执行状态转移  
    33.                 while(sit3 != sit1 + 1  && _goto[t][*sit3 - 'a'] != 0)  
    34.                 {  
    35.                     t = _goto[t][*sit3 - 'a'];  
    36.                     ++sit3;  
    37.                 }  
    38.   
    39.                 //当前子串可以使goto表转移到一个非0位置  
    40.                 if(sit3 == sit1 + 1)  
    41.                 {  
    42.                     //求出输入当前子串在goto表中所转移到的位置  
    43.                     last_state = s[sit3-vit->begin() - 1];  
    44.   
    45.                     //更新该位置的fail值,如果改为值得fail值为0,则用t值替换,因为对于sit1而言,是按照以其为末尾元素的非前缀  
    46.                     //子串的由长到短的顺寻在goto表中寻找非0状态转移的,而满足条件的t是这里免得最长子串  
    47.                     if(_fail[last_state] == 0)  
    48.                     {  
    49.                         _fail[last_state] = t;  
    50.                     }  
    51.   
    52.                     //如果两者都标识完整的模式串  
    53.                     if(_out[last_state].size() > 0 && _out[t].size() > 0)  
    54.                     {  
    55.                         //将out[t]内的模式串全部加入out[last_state]中  
    56.                         for(set<string>::const_iterator cit = _out[t].begin(); cit != _out[t].end(); ++cit)  
    57.                         {  
    58.                             _out[last_state].insert(*cit);  
    59.                         }  
    60.                     }  
    61.                 }  
    62.             }  
    63.         }  
    64.     }  
    65. }  

    然后是执行多模式匹配的AC算法。

    1. void AC(const string& text, const vector<string>& patterns)  
    2. {  
    3.     unsigned int t = 0;  
    4.     string::const_iterator sit = text.begin();  
    5.   
    6.     BuildGoto(patterns);  
    7.     BuildFail(patterns);  
    8.   
    9.     //每次循环中,t都是*sit的前置状态  
    10.     while(sit != text.end())  
    11.     {  
    12.         //检查是否发现了匹配模式,如果有,将匹配输出  
    13.         if(_out[t].size() > 0)  
    14.         {  
    15.             cout << (sit - text.begin() - 1) << ": ";  
    16.   
    17.             for(set<string>::const_iterator cit = _out[t].begin(); cit != _out[t].end(); ++cit)  
    18.             {  
    19.                 cout << (*cit) << ", ";  
    20.             }  
    21.   
    22.             cout << '\n';  
    23.         }  
    24.   
    25.         if(_goto[t][*sit - 'a'] == 0)  
    26.         {  
    27.             t = _fail[t];  
    28.   
    29.             //找到可以实现非0跳转的fail状态转移  
    30.             while(t != 0 && _goto[t][*sit - 'a'] == 0)  
    31.             {  
    32.                 t = _fail[t];  
    33.             }  
    34.   
    35.             if(t == 0)  
    36.             {  
    37.                 //跳过那些在初始状态不能实现非0状态跳转的字母输入  
    38.                 if(_goto[0][*sit - 'a'] == 0)  
    39.                 {  
    40.                     ++sit;  
    41.                 }  
    42.   
    43.                 continue;  
    44.             }  
    45.         }  
    46.   
    47.         t = _goto[t][*sit - 'a'];  
    48.         ++sit;  
    49.     }  
    50. }  

    后记:

    • KMP算法依然是解读AC算法的重要线索,前缀,子串,后缀永远和模式匹配纠缠在一起。
    • AC状态机实际上更适合用Trie结构来存储。
    • 可以将算法中使用到的goto,fail,output三张表以离线的方式计算出来保存在一个文件中,当AC算法启动时,直接从文件中读取三个表的内容,这样可以有效减少每次AC算法启动时都需要构建三个表所花费的时间。
    展开全文
  • 前阵在项目中要求实现bbs发帖时扫描是否有过滤词汇的功能,过滤词汇表是已经给出的,可能会很大,这样如果用正则表达式或者直接一次次字符串匹配效率都会比较差,最后给出的算法描述如下,只需要扫描一遍发帖内容...

    前阵在项目中要求实现bbs发帖时扫描是否有过滤词汇的功能,过滤词汇表是已经给出的,可能会很大,这样如果用正则表达式或者直接一次次字符串匹配效率都会比较差,最后给出的算法描述如下,只需要扫描一遍发帖内容即可。


    Initialize:

    Put the banned words in a HashSet called bannedWordsSet and put the first characters and the length of every banned word in a HashMap called bannedWordsFirstChar. Since HashMap in Java doesn’t allow duplicate keys, different lengths of the banned words whose first characters are the same are put in a HashSet.

     

    Process:

    Iterate the text from the beginning. Check every character of the text. If current character is in the bannedWordsFirstChar, it’s possible that a sub string from current position is a banned word. Get the possible lengths from bannedWordsFirstChar, and for every possible length, extract the sub string according to the current length and check if it is in the bannedWordsSet. If we get a hit, a banned word is found in the text, the start position is the current position and the length is the current length. Else, go to next possible length. If all possible lengths are processed, go to next character of the text.

     

    Algorithm analysis:

    Suppose the text length is m, and there are n banned words. The time needs of the initialize stage is a*n, a is a constant including the time store a word into HashSet, extract the first character of the word and store the character and the length into HashMap. The time needs of the process stage is b*m, where b is a constant including the time look up a character in the HashMap and if hit plus the time used to extract the sub string and look it up in the HashSet. So b must be smaller than or equal to the time needed to process the character which has most possible length values.

    So, the total time complexity of the algorithm is O(a*n + b*m), where a and b are some constants.

     

    Possible Improvements:

    It is supposed that look up in the HashSet and HashMap needs a constant time. So the performance of the HashSet and HashMap is very important in the algorithm. A hash function fits for Chinese strings may contribute a better performance.

     

    Performance analysis:


    展开全文
  • 字符串匹配算法知多少?

    千次阅读 多人点赞 2021-07-03 10:00:09
    一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢? 想到是很正常的,谁让它那么优秀呢。 BF算法 不要被事物的表面现象所迷惑,这个算法全称:Brute Force,有个拉风的中文名:暴力匹配算法...

    在这里插入图片描述

    一说到字符串匹配算法,不知道会有多少小伙伴不由自主的想起那个kmp算法呢?

    想到是很正常的,谁让它那么优秀呢。


    BF算法

    不要被事物的表面现象所迷惑,这个算法全称:Brute Force,有个拉风的中文名:暴力匹配算法。

    能想明白了吧。

    如果模式串长度为 m,主串长度为 n,那在主串中,就会有 n-m+1 个长度为 m 的子串,我们只需要暴力地对比这 n-m+1 个子串与模式串,就可以找出主串与模式串匹配的子串。

    1、从头开始往后遍历匹配;
    2、遇上不对了,就回头,把子串和主串的匹配头后移一位
    3、重复以上。直到找到或确定找不到。
    

    复杂度很高啊,但是在实际开发中也是比较常用的。为什么呢?
    真当天天都有成千上万个字符的主串让我们去匹配吗?一般都比较短,而且,统计意义上,算法执行效率不会真的到M*N的地步。

    理论还是要结合实际的。

    还有另一个原因,就是它好写。当然kmp现在更好写,因为封装好了。
    我说的是类似的场景,没有封装好的函数时候,好写,好改。


    RK算法

    RK 算法的思路是这样的:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了(这里先不考虑哈希冲突的问题,后面我们会讲到)。因为哈希值是一个数字,数字之间比较是否相等是非常快速的,所以模式串和子串比较的效率就提高了。

    有没有方法可以提高哈希算法计算子串哈希值的效率呢?

    我们假设要匹配的字符串的字符集中只包含 K 个字符,我们可以用一个 K 进制数来表示一个子串,这个 K 进制数转化成十进制数,作为子串的哈希值。

    比如要处理的字符串只包含 a~z 这 26 个小写字母,那我们就用二十六进制来表示一个字符串。我们把 a~z 这 26 个字符映射到 0~25 这 26 个数字,a 就表示 0,b 就表示 1,以此类推,z 表示 25。

    在这里插入图片描述

    这里有一个小细节需要注意,那就是 26^(m-1) 这部分的计算,我们可以通过查表的方法来提高效率。我们事先计算好 26^0、26^1、26^2……26^(m-1),并且存储在一个长度为 m 的数组中

    模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1),总共需要比较 n-m+1 个子串的哈希值,所以,这部分的时间复杂度也是 O(n)。所以,RK 算法整体的时间复杂度就是 O(n)。

    但是呢,还有一个很致命的问题,叫做数值过大。
    以幂增的速度是非常快的,用不了多久int就hold不住了啊,那要怎么办?难道我们前面所做的努力都白费了?

    其实不然。
    比方说我们可以改乘为加,当我们匹配到一样的哈希值的时候,再打开子串进行比对,因为相加的话是会有哈西冲突的。

    此外,我们还可以加点优化,一边对主串构建,一边对子串进行匹配,如果一样的话就不继续计算后面的hash了。
    该省的时候就要省,该花的时候就要花。


    编辑器中的全局替换方法:BM算法

    用过吗?比方说要在我这篇博客里找出全部的“主串”这个词,有没有想过其底层的原理?

    这是一个性能优于KMP的算法。

    坏字符

    BM 算法的匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配的。

    我们从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符(主串中的字符)

    在这里插入图片描述

    这时候该如何操作呢?我们去子串中寻找这个坏字符,如果找到了,就让两个字符的位置对上,继续往后,如果没有找到,就将整个子串移动到坏字符后面。

    很显然,这会儿没找到。

    在这里插入图片描述

    接下来该怎么滑呢?又是个坏字符。
    但是在子串中找到了那个坏字符,那就将两个字符的位置对上。

    在这里插入图片描述

    模式串中有对应的坏字符时,让模式串中 最靠右 的对应字符与坏字符相对。

    在这里插入图片描述

    但是呢,用这个规则还是不太够用的,有些个特殊情况吧,它会导致不但不会向后滑动模式串,还有可能会倒推、

    比如说主串:kkkkkkkkkkkkkkkkkk,模式串是 akk


    好后缀规则

    在这里插入图片描述

    如果模式串中存在已经匹配成功的好后缀,则把目标串与好后缀对齐,然后从模式串的最尾元素开始往前匹配。

    在这里插入图片描述

    如果无法找到匹配好的后缀,找一个匹配的最长的前缀,让目标串与最长的前缀对齐:
    在这里插入图片描述

    在这里插入图片描述

    如果完全不存在和好后缀匹配的子串,则右移整个模式串


    代码实现

    难顶,我一定会回来的

    // a,b 表示主串和模式串;n,m 表示主串和模式串的长度。
    public int bm(char[] a, int n, char[] b, int m) {
      int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
      generateBC(b, m, bc); // 构建坏字符哈希表
      int[] suffix = new int[m];
      boolean[] prefix = new boolean[m];
      generateGS(b, m, suffix, prefix);
      int i = 0; // j 表示主串与模式串匹配的第一个字符
      while (i <= n - m) {
        int j;
        for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
          if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
        }
        if (j < 0) {
          return i; // 匹配成功,返回主串与模式串第一个匹配的字符的位置
        }
        int x = j - bc[(int)a[i+j]];
        int y = 0;
        if (j < m-1) { // 如果有好后缀的话
          y = moveByGS(j, m, suffix, prefix);
        }
        i = i + Math.max(x, y);
      }
      return -1;
    }
     
    // j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
    private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
      int k = m - 1 - j; // 好后缀长度
      if (suffix[k] != -1) return j - suffix[k] +1;
      for (int r = j+2; r <= m-1; ++r) {
        if (prefix[m-r] == true) {
          return r;
        }
      }
      return m;
    }
    

    KMP算法

    【C++】算法集锦(10)通俗讲kmp算法

    展开全文
  • 模式字符串匹配 算法综述: Sundy算法四目前最快的字符串匹配算法,本文在sunday基础上做了一些改进(或者改变),能在一定程度上提高sunday算法的运行效率,较有限,但也算是一种思路。 Sunday算法: 从前往后...

    最近看了几个字符串匹配算法,偶然想到对Sunday算法的一种可能的改进(改变)

    问题描述:

    单模式字符串匹配

    算法综述:

    Sundy算法四目前最快的字符串匹配算法,本文在sunday基础上做了一些改进(或者改变),能在一定程度上提高sunday算法的运行效率,较有限,但也算是一种思路。

    Sunday算法:

    从前往后匹配,每次匹配不成功,关注的是尾部的后一字符(设该字符为x)是否在模式串中出现。若出现,移动模式串,使x与模式串中最后一次出现的该字符(下标最大)对齐;若没出现过,移动模式串使其头字符与x的下一字符对齐。总体思想是尽可能大步长地往后移动模式串。

    本文新提出SundayEvening算法:

    总体思想依然是尽可能大步长后移模式串。SundayEvening算法每次从后往前匹配,每次匹配不成功,不只关注尾部后一字符(设为x),也关注当前匹配不成功的字符(设为y)。因为:当尾x在模式串中,而y不在模式传中时,sunday算法可能没有找到最大移动步长。

    SundayEvening的做法是,每当y匹配不成功,若y在模式串中则计算移动模式串使其相应字符与y对齐时的步长,若y不在字符串中,计算移动模式串使其头部与y后一字符对齐时的步长,总之,可以计算出按y来移动模式串的步长。再来看x,当x不在字符串中时,操作与sunday算法一致,若x在字符串中,计算按x移动的步长,与上述按y移动的步长比较,取较大的来进行移动。这样就尽可能的获得了较大的移动步长。而SundayEvening从后往前匹配显然也有助于获得更大步长(y靠后的概率大)。

    Sunday和SundayEvening的比较:

    SundayEvening算法通过两种措施①从后向前匹配②比较步长选较大者,提高了获得最大步长的可能性。但是会增加一些比较操作。当模式串长度极大或极小时,效率与sunday基本无差别,但是在中间某一区域内,SundayEvening算法可以获得约百分10到百分之15的效率提升。(测试数据为随机字符串,字符范围为ascii码中96个可打印字符)。

    代码实现:

    代码中写了三个算法:Sunday、KMP、SundayEvening(为了比较,将KMP一同写出)

    测试数据:随机字符串(字符范围为96个可打印字符)

    测试串长度:1000000000

    模式串长度:10

    测试结果与模式串长度、文本串长度、字符范围均有关系,文本串较小或模式串较大时效率与Sunday算法基本无差(但貌似不会低于Sunday)。

    一次测试的结果:效率提升百分之14

    具体代码:

     

    #pragma once
    #include<iostream>
    #include<Windows.h>
    #include<stdlib.h>
    #include<time.h>
    using namespace std;
    #define random(x) (rand()%x) 
    
    //*********************KMP算法:***********************
    
    void getNext(const unsigned char shortList[], int next[], int shortLength)
    {
    	next[0] = -1;
    	int pointer = -1;//初始值是前面子串的前缀长度(前面子串前缀后第一个元素位置)
    	//pointer最终指向添加shortList[index]之前的子串的最长前缀后的第一个元素
    	int index = 0;//next数组指针,从1开始为next[index]赋值
    	while (index <= shortLength - 1)
    	{
    		if (pointer == -1 || shortList[index] == shortList[pointer])
    		{
    			pointer++;//前缀长度++(位置后移一位)
    			index++;
    			//if (shortList[index] == shortList[pointer])//index不匹配,若pionter位置与他相同,也一定不匹配,应避免这种pointer
    			//	next[index] = next[pointer];//从头开始,每个index都不与他对应的pointer位置元素相同,所以若出现相同,只需一次向前迭代即可保证不同了
    			//else
    			next[index] = pointer;//不同,不匹配就跳到pointer位置看shortList[pointer]是否匹配
    		}
    		else
    			//从未加shortList[index]之前的子串的前缀中,寻找更小的前缀(前缀的前缀),该前缀与后缀的后缀相同,然后看能不能匹配
    			pointer = next[pointer];
    	}
    }
    
    int KMP(const unsigned char longList[], const unsigned char shortList[], int next[], long  longLength, int shortLength)
    {
    	int lp = 0;//longList中的指针
    	int sp = 0;//shortList中的指针
    	while (lp < longLength && sp < shortLength)
    	{
    		if (sp == -1 || longList[lp] == shortList[sp])//都不匹配重新检查,或者匹配
    		{
    			lp++;
    			sp++;
    		}
    		else//取前面与 #lp之前子串的某后缀# 相同的某前缀后的第一个元素
    		{
    			sp = next[sp];
    		}
    	}
    	if (sp == shortLength)
    		return(lp - shortLength);
    	else
    		return -1;
    }
    
    /
    /
    
    //*********************Suday算法:***********************
    
    void GetMaxIndex(int maxindex[], const unsigned char* shortList, const int shortLength)
    {
    	for (int i = 0; i < 256; i++)
    		maxindex[i] = -1;
    	for (int i = 0; i < shortLength; i++)
    	{
    		if (maxindex[shortList[i]] < i)
    			maxindex[shortList[i]] = i;
    	}
    }
    
    int Sunday(const unsigned char shortList[], const unsigned char longList[], int maxindex[], const int shortLength, const long  longLength)
    {
    	int lp = 0;//longList指针
    	int sp = 0;//shortList指针
    	int lhead = lp - sp;//longList中与shortList首元素对齐的元素下标
    	int lrear = lhead + shortLength - 1;//longList中与shortList尾元素对齐的元素下标
    	int result = -1;//longList中shortList的位置
    	while (lrear < longLength)
    	{
    		if (shortList[sp] == longList[lp])
    		{
    			if (lp == lrear)
    				return lhead;
    			lp++;
    			sp++;
    		}
    		else if (lrear + 1 >= longLength)//检查到末尾了,跳出循环
    			break;
    		else if (maxindex[longList[lrear + 1]] == -1)//后一字符不在shortList中
    		{
    			lp = lrear + 2;
    			sp = 0;
    			lhead = lp;
    			lrear = lhead + shortLength - 1;
    		}
    		else//后一字符串在shortList中
    		{
    			lhead = lrear + 1 - maxindex[longList[lrear + 1]];
    			lrear = lhead + shortLength - 1;
    			lp = lhead;
    			sp = 0;
    		}
    	}
    	return result;
    }
    
    
    /
    //***********************Sunday改进算法*************************
    
    int SundayEvening(const unsigned char shortList[], const unsigned char longList[], int maxindex[], const int shortLength, const long  longLength)
    {
    
    	int lhead = 0;//longList中与shortList首元素对齐的元素下标
    	int lrear = shortLength - 1;//longList中与shortList尾元素对齐的元素下标
    	int lp = lrear;//longList指针
    	int sp = shortLength - 1;//shortList指针
    	int result = -1;//longList中shortList的位置
    	int step = 0;//前移的数目
    	while (lrear < longLength)
    	{
    		if (shortList[sp] == longList[lp])
    		{
    			if (lp == lhead)
    				return lhead;
    			lp--;
    			sp--;
    		}
    		else if (lrear + 1 >= longLength)//检查到末尾了,跳出循环
    			break;
    		else if (maxindex[longList[lrear + 1]] == -1)//后一字符不在shortList中
    		{
    			lhead = lrear + 2;
    			lrear = lhead + shortLength - 1;
    			sp = shortLength - 1;
    			lp = lrear;
    		}
    		else
    		{
    			if (lrear + 1 - maxindex[longList[lrear + 1]] < lp - lhead + 1)
    			{
    				lhead += lp - lhead + 1;
    				lrear = lhead + shortLength - 1;
    				lp = lrear;
    				sp = shortLength - 1;
    			}
    			else
    			{
    				lhead = lrear + 1 - maxindex[longList[lrear + 1]];
    				lrear = lhead + shortLength - 1;
    				lp = lrear;
    				sp = shortLength - 1;
    			}
    
    		}
    	}
    	return result;
    }
    
    
    
    
    void main()
    {
    	srand((int)time(0));
    
    	int shortLength = 10;
    	long longLength = 1000000000;
    	unsigned char* shortList = new unsigned char[shortLength];
    	unsigned char* longList = new unsigned char[longLength];
    	for (long i = 0; i < shortLength; i++)
    	{
    		int a = random(96);
    		unsigned char c = a;
    		shortList[i] = c;
    	}
    	for (long i = 0; i < longLength - shortLength; i++)
    	{
    		char c = random(96);
    		longList[i] = c;
    	}
    	for (long i = 0; i < shortLength; i++)
    		longList[i + longLength - shortLength] = shortList[i];
    
    	DWORD start_time = GetTickCount();
    
    	int maxindex[256];//存shortList中出现有的字符在shortList中最后一次出现的位置,同时也标记那些字符出现在了shortList中
    	GetMaxIndex(maxindex, shortList, shortLength);
    	int Sunday_result = Sunday(shortList, longList, maxindex, shortLength, longLength);
    	DWORD Sunday_end_time = GetTickCount();
    
    	if (Sunday_result < 0)
    		cout << "未在文本串中找到模式串!" << endl;
    	else
    		cout << "模式串在文本串中的起始下标为:" << Sunday_result << endl;
    
    	cout << "The Sunday run time is:" << (Sunday_end_time - start_time) << "ms!" << endl;//输出运行时间
    
    	int *next = new int[shortLength];
    	//next[index]存index前面子串中前缀后的第一个元素位置,不匹配时换这个位置的元素看是否匹配
    	//next是对应子串最长前缀长度数组的右移(左端补-1)
    	getNext(shortList, next, shortLength);
    	int KMP_result = KMP(longList, shortList, next, longLength, shortLength);
    	if (KMP_result < 0)
    		cout << "未在文本串中找到模式串!" << endl;
    	else
    		cout << "模式串在文本串中的起始下标为:" << KMP_result << endl;
    
    
    	DWORD KMP_end_time = GetTickCount();
    	cout << "The KMP run time is:" << (KMP_end_time - Sunday_end_time) << "ms!" << endl;//输出运行时间
    
    	GetMaxIndex(maxindex, shortList, shortLength);
    	int Sunday2_result = SundayEvening(shortList, longList, maxindex, shortLength, longLength);
    	DWORD Sunday2_end_time = GetTickCount();
    
    	if (Sunday2_result < 0)
    		cout << "未在文本串中找到模式串!" << endl;
    	else
    		cout << "模式串在文本串中的起始下标为:" << Sunday2_result << endl;
    
    	cout << "The SundayEvening run time is:" << (Sunday2_end_time - KMP_end_time) << "ms!" << endl;//输出运行时间
    
    	cout << "提高了:" << 1 - (double)(Sunday2_end_time - KMP_end_time) / (Sunday_end_time - start_time) << endl;
    
    	system("pause");
    }


     

     

    展开全文
  • 字符串匹配算法

    千次阅读 2017-03-05 19:58:29
    字符串匹配算法字符串匹配算法 朴素字符串匹配算法 Rabin-Karp算法 有限自动机算法 KMP算法 笔面高频题 单词间的逆序调整 前n字符后移 两字字符按照字典序最小拼接 判断两个字符串是否互为旋转词朴素字符串匹配算法/...
  • 字符串匹配算法多模式串)

    千次阅读 2019-02-23 22:35:40
    上一篇了解了单模式串匹配算法,现在来学习多模式串匹配算法,首先需要了解Trie树 Trie树的概念 Trie树也叫字典树或者前缀树,它是一个树形的结构。是一种专门用来处理字符串匹配的数据结构,用来解决在一组字符串中...
  • 字符串匹配算法综述

    万次阅读 多人点赞 2018-07-22 21:39:23
    字符串匹配算法综述 字符串匹配算法综述:BF、RK、KMP、BM、Sunday 字符串匹配算法,是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目。此算法通常输入为原字符串(string)和子串(pattern),要求...
  • 字符串匹配 -- 朴素字符串匹配算法

    千次阅读 2013-07-26 11:29:51
    朴素字符串匹配算法 参考资料:算法导论 朴素字符串匹配 它用一个循环来找出所有有效位移,该循环对 n - m + 1 个可能的每一个 s 值检查条件 P [ 1.. m ] = T [ s+ 1 .. s + m ] 。 这种朴素的字符串匹配过程可以...
  • 字符串匹配算法(单模式串)

    千次阅读 2019-02-17 22:37:22
    本文是数据结构与算法之美的学习笔记 字符串的匹配我们在平时工作中经常用到,每个语言中都有其对应的字符串的匹配方法,比如...多模式串匹配算法(Trie树,AC自动机) BF(Brute Force)算法 基础概念:如果我...
  • KMP字符串匹配算法(一)—模式匹配 KMP是一种通过对“模式串P”进行预处理之后,利用预处理信息来在“文本T”中寻找匹配的算法,这里的“模式串P”和“文本T”可以是任何意义下的可进行”相等“比较的元素集。通常...
  • 字符串匹配算法 之 朴素字符串匹配

    千次阅读 2016-07-04 19:49:25
    前言字符串匹配问题的形式定义: 文本(Text)是一个长度为 n 的字符串:T; 模式(Pattern)是一个长度为 m 且 m≤n 的字符串:P; T 和 P 中的元素都属于有限的字母表 Σ 表; 有效位移 (Valid Shift): 如果 0≤ s ≤n-m...
  • 大多数据结构课本中,涉及的内容即模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • 算法 字符串匹配算法

    2017-05-23 11:46:31
    1. 朴素的模式匹配算法Native String Matching Algorithm朴素的模式匹配算法又称为暴力匹配算法(Brute Force Algorithm),采用遍历的方式进行匹配,滑动窗口总是1,会产生很重复的比较,容易理解,但效率低。...
  • 朴素的字符串匹配算法即暴风(Brute Force)算法,又称暴力匹配算法(BF 算法),其本质是暴力枚举,主要特点有: 没有预处理阶段; 滑动窗口总是后移 1 位; 对模式中的字符的比较顺序不限定,可以从前到后,也...
  • 相信大家对快捷键ctrl+F是做什么用的都应该很熟悉了,无论是文本编辑、网页浏览等程序上它都意味着字符串搜索,我们提供一个关键字,它将找到当前页面上的所有该关键字所在的位置。关键字称为模式串,在文本T中寻找...
  • 一、字符串匹配算法KMPKMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,...
  • KMP字符串匹配算法思悟

    千次阅读 2018-04-06 11:08:12
    KMP字符串匹配算法思悟 本文细致分析了KMP算法高效的原因以及KMP算法的实现原理; 源码github地址(这是我自己实现的相关算法(目前有排序算法和KMP算法),其中用到的数据结构也是自己实现的一套API,包括链表、...
  • 全套字符串匹配算法

    千次阅读 2015-10-17 20:13:50
    字符串匹配算法有很种,但是真正在数据结构算法书上的方法无外乎就只有BF暴力搜索和KMP搜索两种。就算是算法导论上面,也只是除了以上两种方法外还有一种RK算法。这里对其他比较流行的算法进行一一的介绍
  • /*字符串匹配算法 BF算法或者简单算法*/ #include #include #include <string.h> int BF(char S[],char T[]){ int i=0,j=0;//i指向S,j指向T int length_s=strlen(S),length_t=strlen(T); //printf("%
  • KMP算法:最长字符串匹配算法 查找模式串在目标串中的位置 例如:目标串"asdasdaabbccaabsesdf" 模式串:“aabbccaabse” 则返回6,表示从索引下标是6开始匹配。(假设模式串索引为6‘a’的前缀:(a、aa、aab、aabb、...
  • 字符串匹配算法–BM算法
  • 字符串匹配算法(BM)

    万次阅读 多人点赞 2019-06-22 04:12:15
    文章目录1. BM(Boyer-Moore)算法 1. BM(Boyer-Moore)算法 思想:有模式串中不存在的字符,那么肯定不匹配,往后移动几位,提高效率 BM原理:坏字符规则,好后缀规则 ...
  • Python实现字符串匹配算法

    千次阅读 2015-01-04 16:17:15
    字符串匹配是一个经典的问题,即如何在一个给定的z字符串中查找一个给定的值。这里给出了最原始的蛮力字符串匹配算法以及Horspool算法的实现,后者是利用时空权衡中输入增强技术对原始的蛮力算法进行改进。
  • BM算法相比较KMP算法较容易理解,两个算法都是字符串匹配算法,只不过KMP是前缀匹配算法,而BM 是后缀匹配算法,KMP主要依赖next[], 而BM主要依赖bs[], gs[]也就是我们常说的坏字符和好后缀。首先说明一点,BM字符...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,451
精华内容 40,180
关键字:

多模式字符串匹配算法