精确字符匹配的常见算法的解析.docx

精确字符匹配的常见算法的解析从上到下依次是对应KMP，BM，HORSPOOL，SUNDAY算法的文献出处D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of Computing 6, 2, 323-350 (1977)R.S. Boyer, J.S. Moore: A Fast String Searching Algorithm. Communications of the ACM, 20, 10, 762-772 (1977)R.N. Horspool: Practical Fast Searching in Strings. Software - Practice and Experience 10, 501-506 (1980)D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132-142 (1990)KMP算法：KMP就是串匹配算法 运用自动机原理 比如说 我们在S中找P 设Pababbaaba 我们将P对自己匹配 下面是求的过程:依次记下匹配失败的那一位 2ababbaaba .ababbaaba1 3ababbaaba .ababbaaba1 4ababbaaba .ababbaaba2 5ababbaaba .ababbaaba3 6ababbaaba .ababbaaba1 7ababbaaba .ababbaaba2 8ababbaaba .ababbaaba2 9ababbaaba .ababbaaba3 得到Next数组0,1,1,2,3,1,2,2,3 主过程： 1i:=1 j:=1 2若(jm)或(in)转4否则转3 3若j=0或ai=bj则【inc(i)inc(j)转2】否则【j:=nextj转2】 4若jm则return(i-m)否则return -1; 若返回1表示失败，否则表示在i-m处成功BM算法BM算法也是一种快速串匹配算法，BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比较顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。为方便讨论，BM算法的关键是，对给定的模式Tt0t1tm定义一个从字符到正整数的映射：dist：1,2,m+1函数dist称为滑动距离函数，它给出了正文中可能出现的任意字符在模式中的位置。函数dist定义如下：m jj为c在模式中的下标，以后面的为准dist（c）m+1若c不在模式中或c = tm例如，Tpattern，则dist（p）= 6 0 = 6, dist（a）= 6 1 =5, dist（t）= 6 4 =2，dist（e）= 2，dist（r）= 1, dist（n）= 6 + 1 = 7。BM算法的基本思想是：假设将主串中自位置i起往左的一个子串与模式进行从右到左的匹配过程中，若发现不匹配，则下次应从主串的i + dist(si)位置开始重新进行新一轮的匹配，其效果相当于把模式和主串向右滑过一段距离dist（si），即跳过dist（si）个字符而无需进行比较。下面是一个BM算法的匹配过程，主串S =ababcabcacbab，模式T=abcac。因为在实际应用中，字符表中的大部分字符不出现在模式串中，所以应用BM算法可以大大加快串匹配的速度。下面是BM算法的实现，测试代码可以照搬KMP算法部分，把调用KMP函数换成调用BM函数便可。#include using namespace std;int Dist(char *t,char ch)int len = strlen(t);int i = len - 1;if(ch = ti)return len;i-;while(i = 0)if(ch = ti)return len - 1 - i;elsei-;return len;int BM(char *s,char *t)int n = strlen(s);int m = strlen(t);int i = m-1;int j = m-1;while(j=0 & in)if(si = tj)i-;j-;elsei += Dist(t,si);j = m-1;if(j 0)return i+1;return -1;Horspool算法这个算法是由R.Nigel Horspool在1980年提出的。其滑动思想非常简单，就是从后往前匹配模式串，若在某一位失去匹配，此位对应的文本串字符为c，那就将模式串向右滑动，使模式串之前最近的c对准这一位，再从新从后往前检查。那如果之前找不到c怎么办？那好极了，直接将整个模式串滑过这一位。例如：文本串：abdabaca模式串：baca倒数第2位失去匹配，模式串之前又没有d，那模式串就可以整个滑过，变成这样：文本串：abdabaca模式串： baca发现倒数第1位就失去匹配，之前1位有c，那就向右滑动1位：文本串：abdabaca模式串： baca实现代码：#include #include #include #include using namespace std;int Horspool_match(const string & S,const string & M,int pos);int main( ) string S=abcdefghabcdefghhiijiklmabc; string T=hhiij; int pos = Horspool_match(S,T,3); coutnposendl; system(pause); return 0;int Horspool_match(const string & S,const string & M,int pos) int S_len = S.size(); int M_len = M.size(); int Mi = M_len-1,Si= pos+Mi;/这里的串的第1个元素下标是0 if( (S_len-pos) -1) & (Si-1) ); Mi = M_len - 1; Si += M_len - 1; if(Si S_len) return(Si + 1); else return -1;SUNDAY算法：BM算法的改进的算法SUNDAY-Boyer-Moore-Horspool-SundayAglorithmBM算法优于KMPSUNDAY算法描述：字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法则往往比KMP算法快上35倍。但是BM算法还不是最快的算法，这里介绍一种比BM算法更快一些的查找算法即Sunday算法。例如我们要在substringsearchingalgorithm查找search，刚开始时，把子串与文本左边对齐：substringsearchingalgorithmsearch结果在第二个字符处发现不匹配，于是要把子串往后移动。但是该移动多少呢？这就是各种算法各显神通的地方了，最简单的做法是移动一个字符位置；KMP是利用已经匹配部分的信息来移动；BM算法是做反向比较，并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字符（上图中的i)。显然，不管移动多少，这个字符是肯定要参加下一步的比较的，也就是说，如果下一步匹配到了，这个字符必须在子串内。所以，可以移动子串，使子串中的最右边的这个字符与它对齐。现在子串search中并不存在i，则说明可以直接跳过一大片，从i之后的那个字符开始作下一步的比较，如下图：substringsearchingalgorithmsearch比较的结果，第一个字符就不匹配，再看子串后面的那个字符，是r,它在子串中出现在倒数第三位，于是把子串向前移动三位，使两个r对齐，如下：substringsearchingalgorithmsearch哈！这次匹配成功了！回顾整个过程，我们只移动了两次子串就找到了匹配位置，可以证明，用这个算法，每一步的移动量都比BM算法要大，所以肯定比BM算法更快。#include#include#include#include#include#include#includeusingnamespacestd;main()char*text=newchar100;text=substringsearchingalgorithmsearch;char*patt=newchar10;patt=search;size_ttemp256;size_t*shift=temp;size_tpatt_size=strlen(patt);coutsize:patt_sizeendl;for(size_ti=0;i256;i+)*(shift+i)=patt_size+1;/所有值赋于7，对这题而言for(i=0;ishiftr=6-3=3;移动三步/shifts=6步,shitfe=5以此类推*/size_ttext_size=strlen(text);size_tlimit=text_size-i+1;for(i=0;i这个s为第10位，从0开始算如果