KMP算法的理论推导
改进的模式匹配算法的理论分析
设
T = t0 t1 … t s-1 t s t s+1 t s+2 … t s+j-1 t s+j t s+j+1 … t n-1
P = p0 p1 p2 … p j-1 p m-1．
若在匹配过程中出现了如下情况：
t s t s+1t s+2… t s+j-1= p0p1p2… p j-1，(1)但t s+j ≠ p j．也就是说，在匹配过程出现了：
T t0 t1 … t s-1t s t s+1t s+2… t s+j-1t s+j t s+j+1… t s+m-1 … t n-1
‖ ‖ ‖ … ‖ ?
P p0p1p2 … p j-1p j p j-1… p m-1
则本次匹配失败．
由朴素的模式匹配算法，我们需要下一趟匹配，即需要验证下式是否成立：
t s+1t s+2… t s+j-1 t s+j … t s+m?= p0p1 … p j-2p j-1… p m-1(2)如果（2）式成立，则匹配成功，返回s+1；否则需要再下一趟的匹配：t s+2t s+3… t s+j-1t s+j… t s+m+1?= p0p1… p j-3p j-2 …p m-1 (2')以此类推．
下面给出两个互逆的条件
p0p1… p j-2 = p1p2 …p j-1 (3)
p0p1… p j-2 ≠p1p2 …p j-1 (3')显然，这两个条件能且只能满足一个．下面并分情况讨论：【1】如果(3) 式成立，则由(1) (2) (3) 式，可以断定p0 p1 …p j-2 = t s+1 t s+2 … t s+j-1成立，即在（3）式条件下，对(2) 式的验证只需要从p j-
和t s+j 开始逐个往后比较，而不必从p0 和t s+2 开始．
1
【2】如果(3') 式成立，则由(1) (2) (3') 式，可以断定p0 p1 …p j-2 ≠t s+1 t s+2 … t s+j-1成立，即在(3')式条件下，(2)式一定不能成立，应该直接进行下下次验证，即对(2') 进行验证．
对于(2')，也引进两个互逆的条件
p0p1… p j-3 = p2p3 …p j-1 (4)
p0p1… p j-3 ≠p2p3 …p j-1 (4')这两个条件也是只能满足一个，分情况讨论：
【2.1】如果(4) 式成立，则由(1) (2') (4)，可以断定p0 p1 …p j-3 = t s+2 t s+3 … t s+j-1成立，即：对(2') 式的判断从p j-2和t s+j开始逐个往后比较，而不必从p0和t s+2开始．
【2.2】如果(4')式成立，则由(1) (2') (4')，可断定p0 p1 …p j-3 ≠t s+2 t s+2… t s+j-1成立，即(2')一定不成立，应该开始再下一次的判断，即：t s+3 t s+4 … t s+j-1 t s+j … t s+m+2 ?= p0 p1 … p j-4 p j-3 …p m-1没必要再往下做了，下面把刚才的两次匹配过程总结一下，找出规律来：
【1】如果(3) 式成立，则对(2)式的验证可以从p j-1和t s+j开始继续往后进行，而不必从p0和t s+1开始．
【2】如果(3') 成立，则需要进行下下次匹配【见(2')式】：
【3】如果(3') 和(4) 式成立，则对(2') 式的验证可以从p j-2和t s+j开始继续往后进行，而不必从p0和t s+1开始．
【4】如果(3') 和(4') 式成立，则需要进行下下下次匹配：t s+3 t s+4 … t s+j-1 t s+j … t s+m+2 ?= p0 p1 … p j-4 p j-3 …p m-1
由刚才总结的第【3】种情况，我们可以设想存在一个k，使得
p0p1… p j-2 ≠p1p2 …p j-1 (3')
p0p1… p j-3 ≠p2p3 …p j-1 (4')
… … … …
p0p1… p k ≠p j-k-1p j-k …p j-1 (5')
p0p1… p k-1 = p j-k p j-k+1 …p j-1 (6)显然，如果这样的k 存在，则0 <= k < j-1（当k == 0 时，(6)式的左右都为空串）．
再由刚才总结的第【2】和【4】种情况可知：如果(3') (4') …(5') 都成立，哪些判断不用做了呢？这需要发现(2)、(2') 的变化规律．刚才，由(3') 式，则(2) 式不用再判断了；由(4') 式，则(2') 式不用再判断了．换句话说，根据(5') 式，
●当k = j – 2时【(3')式成立】，(2)式不用判断了；
●当k = j – 3时【(4')式成立】，(2')式不用判断了；
●… …
由此可以推出：当k时，下面的(7) 式不用判断了
t s+j-k-1t s+j-k… t s+j-1t s+j… t s+j-k+m-2 ?= p0p1… p k p k+1… p m-1 (7)也就是说，当k 时，也就是(5') 成立时，(7) 式子不用判断了．此时需继续判断如下的(8) 式是否成立
t s+j-k t s+j-k+1… t s+j-1t s+j… t s+j-k+m-1?= p0p1… p k-1p k… p m-1 (8)由(6) 式和(8) 式，再考虑到(1) 式并改写(1) 式
t s t s+1… t s+j-k t s+j-k+1… t s+j-1= p0p1… p j-k p j-k+1 …p j-1(1)可以断定：p0 p1 …p k-1 = t s+j-k t s+j-k+1 … t s+j-1，因此，下次比较从p k和
t s+j开始即可．
综上：若在上述的失配情况下，且存在最大的正整数k，换句话说，当k = j-2, j-3, …, k 时，(5') 式都是成立的．但是，当k-1 时，(5') 不再成立，而(6) 式成立，则下一次的比较从p k和t s+j开始即可．那么，这样的k 是否存在？如何确定呢？
下面把刚才的问题再次重述一下，从而明确我们要做的具体任务：若t s t s+1 t s+2 … t s+j-1 = p0 p1 p2 … p j-1，但t s+j p j，则本次匹配失败．则我们用一个next向量来确定k，也就是说，当模式P 中第j 个字符p j与目标T 中第s+j 个字符t s+j失配时，应当用模式P 中字符p k （next[j] = k）与目标T 中的t s+j继续进行比较．那么k 怎么求呢？
下面介绍确定k 的方法．
显然，k的取值是由(5') 和(6) 式确定．进一步发现，k的取值只与模式P有关，和目标T无关，因此把next向量称为模式的特征向量（描述了模式的一个特征，和主串无关）．
由上述分析可知，next[j] 的值可以按如s下的公式来计算：
next[j]={?1,j=0;
k,0 示例：若P = "abaabcac"，则 设在进行某一趟匹配比较时在模式P 的第j 位失配： ●如果j > 0，那么在下一趟比较时模式串P的起始比较字符是 p k，即p next(j)，而目标串T 的指针不回溯，仍指向刚才失配的字符； ●如果j = 0，则目标串T 的指针进一，模式串P 指针回到字符 p0，继续进行下一趟匹配比较． 上述两种情况就是KMP算法的核心内容。假设next[ ] 已知，则KMP算法的C++代码如下： int AString::fastFind(const AString& pat, int next[ ],int k) const { // 从k 开始寻找pat 在this 串中匹配的位置。若找到，函数 // 返回pat 在this 串中开始位置，否则函数返回-1。数组 // next[ ] 存放pat 的next[j] 值。 int posP = 0,posT = k;// 两个串的扫描指针 int lengthP = pat.curLength;// 模式串长度 int lengthT = curLength;// 目标串长度 while (posP < lengthP && posT < lengthT) if (posP == -1 || pat.ch[posP] == ch[posT]) { posP++; posT++; }// 对应字符匹配 else posP = next[posP];// 求pat下趟比较位置 if (posP < lengthP) return -1;// 匹配失败 else return posT-lengthP;// 匹配成功 } 此算法的时间复杂度取决于while循环．由于是无回溯的算法， 执行循环时，目标串字符比较有进无退，要么执行posT和posP进1，要么查找next[ ] 数组进行模式位置的右移，然后继续向后比较．字符的比较次数最多为O(n)，不超过目标的长度． 举例：利用next特征向量进行匹配处理 刚才的KMP算法是在next[ ] 已知的情况下进行的。那么next[ ]是如何计算的呢？ 由刚才的计算next[ ] 的推导公式发现，我们还无法让计算机来实现，这是因为从公式中（如下） next[j]={?1,j=0; k,0 红色部分只给出了k应满足的条件，还没有给出具体算法，所以我们也无法用计算机语言写出来。 那么，我们怎么把这段话用算法写出来呢？下面：首先分析并推导，然后给出算法和代码。 计算next特征向量的理论推导 设模式P = p0 p1 p2 …p m-1，由m个字符组成，而next特征向量为next = n0 n1 n2 … n m-1，表示了模式的字符分布特征． 由next[j] 的定义，计算next[j] 就是要在串P j = p0 p1 p2 …p j-1中找出最长且相等的前缀子串P k 和后缀子串P-k ，其中： P k = p0 p1 p2 …p k-1，P-k = p j-k p j-k+1 p j-k+2…p j-1用递推的思想：假设next[j] = k 是已知的，则P k = P-k，即： p0 p1 …p k-1= p j-k p j-k+1 …p j-1，(9)则，计算next[j+1]需先验证 p0 p1 …p k-1p k?= p j-k p j-k+1 …p j-1p j，(10)由(9)式可知，若验证(10)式，只需验证 p k?= p j(11)下面分情况讨论： 【1】若(11)式成立，即p k = p j，则(11)式成立，即： next[j+1] = k + 1 = next[j] + 1 (12)【那么，为什么next[j+1] 不能是k+2，或更大呢？】假设next[j+1] = k + 2，则p0 p1 …p k-1 p k p k+1 = p j-k-1 p j-k p j-k+1 …p j-1 p j，这说明p0 p1 …p k-1 p k = p j-k-1 p j-k p j-k+1 …p j-1，从而说明next[j] = k + 1，和已知矛盾，故当next[j] = k时，next[j+1] <= k+1．【证毕】 【2】若(11)式不成立，即p k≠ p j，由(9)式可知： p0 p1 … p j-k-1p j-k p j-k+1 … p j-1p j ‖ ‖ ‖ ? p0 p1 … p k-1p k 此问题转换成了在p0 p1 … p k-1中寻找下一次要与p j进行比较的字符p h，即：是否存在最大的正整数h，使得 p0 p1 … p h ≠p k-h-1 p k-h … p k-1，(13) p0 p1 …p h-1= p k-h p k-h+1 …p k-1，(14)成立？若h 存在，则需要比较p h ?= p j． 还分两种情况： 【2.1】找到h (h ≥ 0)，由next[k]的定义可知：next[k] = h，从而(14)式成立，联立(9)式并改写(9)式， p0 p1 … p k-h p k-h+1 …p k-1= p j-k p j-k+1 … p j-h p j-h+1 … p j-1(9)可得， p0 p1 …p h-1= p j-h p j-h+1 …p j-1(15)因此，下一步只需比较p h ?= p j．类似地，若p h = p j，则 next[j+1] = h+1 = next[k]+1= next[next[j]]+1；否则，还需要在p0 p1 …p h-1中寻找更小的next[h]，直到next[t] = -1为止． 【2.2】找不到h，（即h = -1），则next[j+1] = 0 = h + 1 = next[0] + 1． next特征向量的算法和C++代码 next特征向量从0, 1, 2, …, m-1逐项递推计算： [1] 当j == 0时，n0 = -1．设j≥ 0 时n j = k; [2] 当(k == -1) || (p j ==p k)，则n j+1 = k+1 = n j + 1． [3] 当p j≠p k且k ≠ -1，令k = n k，并让[3] 循环直到条件不满 足． [4] 当k == -1，则n j+1 = 0 = k + 1 = n0 + 1． 例如： C++代码： void AString::getNext(int next[ ])const { int j = 0, k = -1, lengthP = curLength; next[0] = -1; while (j < lengthP)// 计算next[j] if ( k == -1 || ch[j] == ch[k]) { j++; k++; next[j] = k; } else k = next[k]; } 完整的例子 #include #include #include using namespace std; const int defaultSize = 128; // 字符串的最大长度 class AString { // 字符串类 private: char *ch;// 存放串的数组首地址 int curLength;// 串的实际长度 int maxSize;// 存放串数组的最大长度 public: AString(int sz = defaultSize);// 构造函数 AString(const char *init );// 构造函数 AString(const AString& ob);// 复制构造函数 ~AString( ) { delete [ ]ch; }// 析构函数 int Length( ) const { return curLength; }// 求长度 AString operator( ) (int pos, int len);// 求子串 bool operator == (AString& ob) const // 判串相等 { return strcmp (ch, ob.ch) == 0; } // 若相等, 返回true bool operator != (AString& ob) const // 判串不等 { return strcmp (ch, ob.ch) != 0; } // 若不等, 返回true bool operator ! ( ) const { return curLength == 0; } AString& operator = (const AString& ob); // 串赋值 AString& operator += (const AString& ob); // 串连接 char operator [ ] (int i);// 取第i 个字符int Find (const AString& pat, int k = 0) const; // 串匹配 int fastFind(const AString& pat, int next[ ], int k = 0) const; void getNext(int next[ ])const; }; AString::AString(int sz) { // 构造函数：创建一个空串maxSize = sz; assert(ch = new char[maxSize+1]); // 创建串数组 curLength = 0; ch[0] = '\0'; // 串的结束符为'\0' } AString::AString(const char *init) { // 构造函数: 从已有字符数组init 复制 int len = strlen(init); maxSize = (len > defaultSize) ? len : defaultSize; assert(ch = new char[maxSize + 1];) // 创建串数组 curLength = len;// 复制串长度 strcpy(ch, init);// 复制串值 } AString :: AString(const AString& ob) { // 复制构造函数：从已有串ob 复制 maxSize = ob.maxSize; // 复制串最大长度 assert(ch = new char[maxSize + 1]); // 创建串数组 curLength = ob.curLength; // 复制串长度 strcpy(ch, ob.ch); // 复制串值 } AString AString::operator ( ) (int pos, int len) { // 从串中第pos 个位置起连续提取len 个字符形成子串返回if (pos < 0 || len <= 0 || pos+len-1 >= curLength) { AString t1; return t1; } // pos 或len不合法，返回空串int n = defaultSize > len ? defaultSize : len; AString temp(n + 1); temp.curLength = len; // 子串长度 for (int i = 0, j = pos; i < len; i++, j++) temp.ch[i] = ch[j]; temp.ch[len] = '\0'; // 子串结束 return temp; } AString& AString::operator = (const AString &ob) {// 串赋值if (&ob != this) {// 若两个串不是自己给自己赋值 delete [ ]ch; maxSize = ob.maxSize; assert(ch = new char[maxSize + 1]); // 重新分配 curLength = ob.curLength; strcpy(ch, ob.ch); } return *this; } char AString::operator [ ] (int i) { // 提取当前串*this 的第i 个字符 if (i < 0 && i >= curLength) { cout << "字符串下标超界!\n"; exit(1); } return ch[i]; } AString& AString::operator+= (const AString &ob) { // 串链接 int n = curLength + ob.curLength;// 串长度累加if (n > maxSize) { maxSize = n; curLength = n; char *temp = ch;// 暂存原串数组 assert(ch = new char[n+1]); strcpy(ch, temp); delete [ ]temp; } strcat(ch, ob.ch);// 连接ob 串数组 return *this; } int AString::Find(const AString& pat, int k) const { // 在当前串中从第k 个字符开始寻找模式pat 在当 // 前串中匹配的位置。若匹配成功, 则函数返回首 // 次匹配的位置, 否则返回-1。 int i, j, n = curLength, m = pat.curLength; if (m <= 0 || k < 0) return -1; while (k <= n - m) { for (i = k, j = 0; j < m; j++, i++) if (ch[i] != pat.ch[j]) { k++; break; } // 本次失配 if (j >= m) return k; // 匹配成功} return -1; // pat为空或在*this中找不到它 } int AString::fastFind(const AString& pat, int next[ ], int k) const { // 从k 开始寻找pat 在this 串中匹配的位置。若找到，函数// 返回pat 在this 串中开始位置，否则函数返回-1。数组 // next[ ] 存放pat 的next[j] 值。 int posP = 0, posT = k;// 两个串的扫描指针 int lengthP = pat.curLength;// 模式串长度 int lengthT = curLength;// 目标串长度 while (posP < lengthP && posT < lengthT) if (posP == -1 || pat.ch[posP] == ch[posT]) { posP++;posT++; }// 对应字符匹配 else posP = next[posP];// 求pat下趟比较位置 if (posP < lengthP)return -1;// 匹配失败 else return posT-lengthP;// 匹配成功 } void AString::getNext(int next[ ])const { int j = 0, k = -1, lengthP = curLength; next[0] = -1; while (j < lengthP) // 计算next[j] if ( k == -1 || ch[j] == ch[k]) { j++; k++; next[j] = k; } else k = next[k]; } int main( ) { AString T("acabaabaabcacaabc"); AString P("abaabcac"); int *next; assert(next = new int[P.Length( )]); P.getNext(next); cout << "B-F: " << T.Find(P) << endl; cout << "KMP: " << T.fastFind(P, next) << endl; delete [ ]next; return 0; } 运行结果如下： 模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。 文献综述 一般使用的计算机的硬件结构主要反映数值计算的需要，而计算机上的非数值处理的对象基本上是字符串数据，因此在处理字符串数据时比处理整数和浮点数要复杂的很多。随着程序语言将程序的发展，字符串的处理也有了越来越多的研究。子串的定位炒作通常称为串的模式匹配，是各种处理系统中最重要的操作之一。串匹配问题是指从给定的字符序列中找出一个或多个具有某种属性的模式序列，而字符串匹配指的便是从给定的字符序列中找出一个或若干个给定的字符串。字符串匹配算法是一个基础算法，它的解决以及在这个过程中产生的方法对计算机的其他问题都产生了巨大的影响。在我们日常使用计算机的过程中，使用字符串匹配技术的例子十分普遍，例如：入侵检测、病毒检测、信息检索、信息过滤、计算生物学等等都包含了字符串匹配技术。 在字符串匹配技术被广泛应用的同时，众多的科技人员也对其进行了深入的研究，字符串匹配问题现在已经发展成为一门相对独立的科学——字符串学（Stingology）[1][2][3]。字符串匹配技术最先被应用于图书文献目录摘要的查询系统和构建数据的全文检索系统。而后，随着网络安全技术和生物技术的日益发展，在网络安全和生物计算等领域中字符串匹配技术又获得了新的发展空间。 随着网络速度和流量的日益增加，基于网络的入侵检测[4][5]系统面临着严峻的挑战，它的处理、分析速度越来越难以跟上网络流量增加速度，从而极易导致数据包的丢失。解决数据包丢失等问题，提高处理速度是关键。另外对于基于误用的入侵检测系统而言，检测过程中最费时的部分便是入侵特征匹配。 目前，信息资源的高速膨胀已经成为一个全球普遍关注的现象。加利福尼亚大学伯克利分校研究人员发现，仅从1999年至2002年全球新产生的信息量就翻了一番。伴随着信息膨胀，信息的良莠不齐现象也是一个严重困扰人们的问题。大量反动、黄色信息以及国家机密在网络上蔓延和传播，给国建安全和社会稳定造成了严重的威胁，如何对这些不良信息进行网络监控是我们面临的一个重要问题。在信息过滤时，特别是在主干网络上进行过滤与检索，对字符串匹配的实时性要求极高，字符串匹配性能的优劣直接影响了过滤与检索系统的性能。 随着生命科学的发展，人们对生命物质的微观结构也有了越来越清晰的认识。目前，人类基因组序列的绘制工作已完成，Prosite等大型蛋白质重要样本数 实验四：KMP算法实验报告 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： 数据结构 实 验 报 告 学院软件学院 年级2009级 班级班 学号 姓名 2010 年 3 月24 日 目录 一、实验内容 (1) 二、实验过程……………………………………….X 三、实验结果……………………………………….X 一、实验内容： 1、实验题目：KMP算法 2、实验要求：实现教材中字串比较kmp算法，比较模式串abaabcac与主串acabaabaabcacaabc。 3、实验目标：了解并掌握串的类型定义和基本操作，并在此基础上实现kmp算法。了解kmp算法的基本原理和next函数的使用。 二、实验过程： 1、任务分配 2、设计思想 （1）KMP算法：在模式匹配中，每当一趟匹配过程出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右滑动尽可能远的一段距离之后，继续进行比较。 （2）next函数：看成一个模式匹配问题，整个模式串既是主串又是模式串，可仿照KMP算法。 3、需求分析 (1) 输入的形式和输入值的范围：输入主串S,模式串T，位置pos (2) 输出的形式：模式串在主串中开始匹配的位置i (3) 程序所能达到的功能：利用kmp算法完成模式串和主串的模式匹 配，并输出模式串在主串中开始匹配的位置 (4) 测试数据： S=acabaabaabcacaabc T=abaabcac Pos=6 4、概要设计 1).抽象数据类型 Class String()定义字符串 Int StrLength()返回串的长度 V oid get_next()求模式串T的next函数值并存入next int kmp()利用模式串T的next函数求出T在主串S中第pos个字符之后的位置的KMP算法 2).算法 a.kmp算法模块：实现主串和模式串的模式匹配 b.next函数模块：实现模式串自身的模式匹配，并存入nxet函数中 c.接收处理命令（初始化数据） 5、详细设计 程序代码（含注释） 对KMP算法的理解 整理者——戴红伟 字符匹配算法的现实意义：随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量。 （请同时参照课本P53～54相关内容） 1.要理解next[j]=k 中，k的含意； （1）BF算法 假设有字符串 S=S1S2......S N P=P1P2......P M 其中（M （2）KMP算法 为了解决上述的问题，KMP算法被发现。 KMP算法的思想如下。匹配过程中，出现不匹配时，S的指针不进行回朔（原地不动），将P尽可能地向后移动一定的距离，再进行匹配。 如图： （该图引用自互联网） 从上图中我们看到，当S移动到i，P到j的时候失配。这时候i不回朔，而只是将P 向前移动尽可能的距离，继续比较。 假设，P向右移动一定距离后，第k个字符P[k]和S[i]进行比较。 此时如上图，当P[j]和S[i]失配后，i不动，将P前移到K，让P[k]和S[i]继续匹配。现在的关键是K的值是多少？ 通过上图，我们发现，因为黄色部分表示已经匹配了的结果（因为是到了S[i]和P[j]的时候才失配，所以S i-j+1S i-j+2…S i-1 = P1P2…P j-1，见黄色的部分）。所以有： 1、S i-k+1S i-k+2…S i-1 = P j-k+1P j-k+2…P j-1。 所以当P前移到K时，有： 2、S i-k+1S i-k+2…S i-1 = P1P2…P k-1。 通过1，2有 P j-k+1P j-k+2…P j-1 = P1P2…P k-1。 呵呵，此时我们的任务就是求这个k值了。。。 参考：https://www.wendangku.net/doc/cb3103869.html,/2008-09/122068902261358.html 2.求出k 值 按照课本的求法就可以处理。 课本是已知前j个元素的“前缀函数值”，如何求的j+1个元素的前缀函数值。这里有一个思路要发生转变的地方，把一个模式串分成两个部分，因为我们要找k使得P j-k+1P j-k+2…P j-1= P1P2…P k-1，而这本身就是一个模式匹配问题，所以把模式串的前边部分的子串当作“新的模式串”，这样就很容易理解为什么当t k!=t j时，t1…t next[k]-1 = t j-（next[k]-1）…t j-1了。因为这时候t k匹配失败，需要进一步移动模式子串，所以移动的位置就是next[k]。 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 入 侵 检 测 试 验 实验名称:_ KMP算法实验专业班级: _ 网络工程13-01 学号:_ 姓名: 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 字符串匹配是计算机的基本任务之一。 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ 许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。 我用自己的语言，试图写一篇比较好懂的KMP算法解释。 1. 首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。 2. 因为B与A不匹配，搜索词再往后移。 3. 就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。 4. 接着比较字符串和搜索词的下一个字符，还是相同。 5. 直到字符串有一个字符，与搜索词对应的字符不相同为止。 6. 这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。 7. 一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。 8. 怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。 9. 已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数： KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos 详解KMP算法中Next数组的求法 例如： 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next值0 1 1 2 2 3 1 2 next数组的求解方法是：第一位的next值为0，第二位的next 值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next 值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。 看起来很令人费解，利用上面的例子具体运算一遍。 1.前两位必定为0和1。 2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。 3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next 值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。 4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。 5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next 值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。 6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。 7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next 值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。 KMP算法小结 Posted on 2011/06/14 by huangchao 主要看了这里，感觉讲的十分的不错，总结一下。 首先声明要搜索的串为S,设长度为n，要匹配的串为M,设长度为m. 先考虑暴力的算法，暴力的算法是遍历S的每一个字符，然后从这个字符开始和M串进行匹配。时间复杂度为O(nm). 怎么在此基础上进行优化？假设现在从某个位置(设为s)开始和M串进行匹配，如果匹配不成功，暴力算法是从这个位置的下一个位置(s+1)进行匹配,直观上来说就是匹配的字符串向后“滑动”了一位。 图1 能不能想办法让M向后移动的距离最大化？考虑最好的情况，如果和M匹配的S中的m个字符和M中的字符没有一个相等，那么能向右移动m位；考虑最坏的情况，比如上图，只能移动一位。 而KMP就是在这里做文章，让M串向后“滑动”的距离最大化。 图2 考虑上面的图，M中灰色部分已经和S的灰色部分匹配上了，而灰色部分后一个字符不匹配，则现在M要向后滑动，假设一直向后滑动，直到如图位置又和S再一次匹配上了，那么从这里我们可以得到如下的结论： ?A段字符串是M的一个前缀。 ?B段字符串是M的一个后缀。 ?A段字符串和B段字符串相等。 这样，如果暂时不考虑S，只看M的话，假设已经匹配的M的字串(即图中M 中灰色部分)为subM，则subM有个【相等】的【前缀】和【后缀】。而且M在遇到不匹配的时候可以直接滑动到使subM的前缀和subM的后缀重合的地方。而M向后滑动的时候，第一次subM的前缀和后缀重合意味着此时这个相等的subM的前缀和后缀的长度是最大的。 我们的任务就是要寻找subM的最长的前缀和后缀相等的串。 知道了这一点，离KMP的真谛也就不远了。现在结合这上面的图模拟一下KMP 算法的整个流程： ?将S串和M串从第一个字符开始匹配； ?如果匹配成功，则subM即灰色部分增加； ?如果不成功，则M向后滑动使滑动后的subM的前缀和滑动前的subM的后缀重合，再进行匹配，如果还不成功，则再次滑动M，直到匹配成功或者M 滑动到X处。如果到了X处，则从M串的起始位置进行匹配。 从上面的步骤可以知道，KMP的关键就是要知道当S串中的字符和M串中的字符不匹配时，S串要和M串中的哪个字符继续进行匹配。这个就是在利用状态机模型来解释KMP算法时的状态转移. KMP是通过一个定义了一个next数组，这个next数组保存了如果S中的字符和M中的字符不匹配时S要和M中的哪个字符重新进行匹配的坐标值。如图2中所示是例子，S中的X位置和M不匹配了，那么S要和M中A段后面的字符进行比较，从图中来看是M向后滑动了。 换句话说，next[i]总是保存了当M[i]不匹配时要从M[next[i]]处进行匹配，这个M[next[i]]可能会匹配，如果还不匹配？那么可能会在M[next[next[i]]]处匹配了。这里同时隐含着一个信息，就是i之前的一段字符和next[i]之前的一段字符是相同的，也就是M[0…i-1]相等的前缀和后缀。 现在考虑next[0],next[1]…next[i]都已经知道了，那么图示如下： #define _CRT_SECURE_NO_DEPRECA TE #include s_i++; p_i++; continue; } else { if (p_i == 0) { s_i++; } else { p_i = next[p_i-1]; //取当前匹配不到之前的字符串的最大相等前缀的最后一个字符 } } for (i = 0; i < s_i - p_i; i++) { putchar(' '); } printf("%s\n",ptr); } return (p_i == plen) ? (s_i - plen) : -1;//返回第一次找到子串的下标位置 } int main() { char str[N] = { 0 }; char ptr[N] = { 0 }; int slen, plen; int next[N]; int ret; printf("请输入主串："); scanf("%s",str); printf("请输入模式串:"); scanf("%s",ptr); slen = strlen(str); plen = strlen(ptr); cal_next(ptr, next, plen); printf("\nnext:"); KMP算法步骤剖析 注：先计算好next值进而推出nextval数值，可在CSND上找到求解方法。 对于上述KMP算法第趟匹配,有一定的难度！接下来，我来分析一下。 先给主串和模式串进行编号： 主串 a b c a a b b a b c a b a a c b a c b a 编号i: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 模式串 a b c a b a a 编号j：1 2 3 4 5 6 7 (1)第一趟排序 主串t: a b c a a b b a b c a b a a c b a c b a 模式串p: a b c a b a a i=5 j=5 时匹配失败 取模式串p第五位的nextval值。nextval=1 故下一趟排序将主串的第i=5位与模式串的第nextval=1位进行比 较。 即得到第二趟排序： (2)第二趟排序 主串t: a b c a a b b a b c a b a a c b a c b a 模式串p: a b c a b a a i=7 j=3 时匹配失败 取模式串p第三位的nextval值。nextval=1 故下一趟排序将主串的第i=7位与模式串的第nextval=1位进行比 较。 即得到第三趟排序： (3)第二趟排序 主串t: a b c a a b b a b c a b a a c b a c b a 模式串p: a b c a b a a i=7 j=1 匹配失败 取模式串p第1位的nextval值。nextval=0 当nextval=0时，主串要向后面移动一位 故下一趟排序将主串的第i=7+1=8位与模式串的第1位进行比较。 (4)第二趟排序 主串t: a b c a a b b a b c a b a a c b a c b a 模式串p: a b c a b a a i=15 j=8 匹配成功！ KMP算法是在最近这两年的软件设计师考试中才出现的。2次都是让求Next函数的序列（其实是）。先看看题吧。 （2011年下半年上午题） （2012年上半年上午题） 其实做这个题很简单，我先说说这个题里的各种概念。 给定的字符串叫做模式串T。j表示next函数的参数，其值是从1到n。而k则表示一种情况下的next函数值。p表示其中的某个字符，下标从1开始。看等式左右对应的字符是否相等。 好了，开始做题了。 首先，要把字符串填入到一个表格中：（拿第一个题为例） 将j导入next函数，即可求得， j=1时，next[0]=0； j=2时，k的取值为(1,j)的开区间，所以整数k是不存在的，那就是第三种情况，next[2]=1； j=3时，k的取值为（1，3）的开区间，k从最大的开始取值，然后带入含p的式子中验证等式是否成立，不成立k取第二大的值。现在是k=2，将k导入p的式子中得，p1=p2，即“a”=“b”，显然不成立， 舍去。k再取值就超出范围了，所以next[3]不属于第二种情况，那就是第三种了，即next[3]=1； j=4时，k的取值为（1，4）的开区间，先取k=3，将k导入p的式子中得，p1p2=p2p3，不成立。再取k=2，得p1=p3，成立。所以next[4]=2； j=5时，k的取值为（1，5）的开区间，先取k=4，将k导入p的式子中得，p1p2p3=p2p3p4，不成立。再取k=2，得p1p2=p3p4，不成立。再取k=2，得p1=p4，成立。所以next[4]=2； j=6时，k的取值为（1，6）的开区间，先取k=5，将k导入p的式子中得，p1p2p3p4=p2p3p4p5，不成立。取k=4，得p1p2p3=p3p4p5，不成立。再取k=3，将k导入p的式子中得，p1p2=p4p5，成立。所以next[4]=3； j=7时，k的取值为（1，7）的开区间，先取k=6，将k导入p的式子中得，p1p2p3p4p5=p2p3p4p5p6，不成立。再取k=5，得 p1p2p3p4=p3p4p5p6 ，不成立。再取k=4，得p1p2p3=p4p5p6 ，成立。所以next[4]=4； KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足,明确next数组需要改进之外。其中,理解算法是核心,会求数组是得分点。不用我多说,这一节内容是本章的重中之重。可能进行的考查方式是:求next和nextval 数组值,根据求得的。 KMP算法即Knuth-Morris-Pratt算法，是模式匹配的一种改进算法，因为是名字中三人同时发现的，所以称为KMP算法。因为偶然接触到有关KMP的问题，所以上网查了一下next数组和nextval数组的求法，却没有找到，只有在CSDN 的资料文件里找到了next数组的简单求法（根据书上提供的程序也可以求到，但一般在课堂讲解的时候，学生难以理解，所以希望以更容易理解的形式来讲解），那位高人说时间关系，先讲到这里，于是讲完了next数组就功成身退了。BS的同时，自己研究了下nextwal数组，发现了其中的简易规律，并写了出来，希望能对需要快速理解KMP中nextval的求法的朋友有所帮助。 int get_nextval(SString T,int &nextval[ ]){ //求模式串T的next函数修正值并存入数组nextval。 i=1; nextval[1]=0; j=0; while(i 改进的模式匹配算法的理论分析 设 T = t0 t1 … t s-1 t s t s+1 t s+2 … t s+j-1 t s+j t s+j+1 … t n-1 P = p0 p1 p2 … p j-1 p m-1． 若在匹配过程中出现了如下情况： t s t s+1t s+2… t s+j-1= p0p1p2… p j-1，(1)但t s+j ≠ p j．也就是说，在匹配过程出现了： T t0 t1 … t s-1t s t s+1t s+2… t s+j-1t s+j t s+j+1… t s+m-1 … t n-1 ‖ ‖ ‖ … ‖ ? P p0p1p2 … p j-1p j p j-1… p m-1 则本次匹配失败． 由朴素的模式匹配算法，我们需要下一趟匹配，即需要验证下式是否成立： t s+1t s+2… t s+j-1 t s+j … t s+m?= p0p1 … p j-2p j-1… p m-1(2)如果（2）式成立，则匹配成功，返回s+1；否则需要再下一趟的匹配：t s+2t s+3… t s+j-1t s+j… t s+m+1?= p0p1… p j-3p j-2 …p m-1 (2')以此类推． 下面给出两个互逆的条件 p0p1… p j-2 = p1p2 …p j-1 (3) p0p1… p j-2 ≠p1p2 …p j-1 (3')显然，这两个条件能且只能满足一个．下面并分情况讨论：【1】如果(3) 式成立，则由(1) (2) (3) 式，可以断定p0 p1 …p j-2 = t s+1 t s+2 … t s+j-1成立，即在（3）式条件下，对(2) 式的验证只需要从p j- 引记 此前一天，一位MS的朋友邀我一起去与他讨论快速排序，红黑树，字典树，B树、后缀树，包括KMP算法，唯独在讲解KMP算法的时候，言语磕磕碰碰，我想，原因有二：1、博客内的东西不常回顾，忘了不少；2、便是我对KMP算法的理解还不够彻底，自不用说讲解自如，运用自如了。所以，特再写本篇文章。由于此前，个人已经写过关于KMP算法的两篇文章，所以，本文名为：KMP算法之总结篇。 本文分为如下六个部分： 1. 第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度，并两相对照各 自的匹配原理； 2. 第二部分、通过我此前第二篇文章的引用，用图从头到尾详细阐述KMP算法中的 next数组求法，并运用求得的next数组写出KMP算法的源码； 3. 第三部分、KMP算法的两种实现，代码实现一是根据本人关于KMP算法的第二篇文 章所写，代码实现二是根据本人的关于KMP算法的第一篇文章所写； 4. 第四部分、测试，分别对第三部分的两种实现中next数组的求法进行测试，挖掘其 区别之所在； 5. 第五部分、KMP完整准确源码，给出KMP算法的准确的完整源码； 6. 第六步份、一眼看出字符串的next数组各值，通过几个例子，让读者能根据字符串 本身一眼判断出其next数组各值。 力求让此文彻底让读者洞穿此KMP算法，所有原理，来龙去脉，让读者搞个通通透透（注意，本文中第二部分及第三部分的代码实现一的字符串下标i 从0开始计算，其它部分如第三部分的代码实现二，第五部分，和第六部分的字符串下标i 皆是从1开始的）。 在看本文之前，你心中如若对前缀和后缀这个两个概念有自己的理解，便最好了。有些东西比如此KMP算法需要我们反复思考，反复求解才行。个人写的关于KMP算法的第二篇文章为：六（续）、从KMP算法一步一步谈到BM算法；第一篇为：六、教你初步了解KMP算法、updated（文末链接）。ok，若有任何问题，恳请不吝指正。多谢。 第一部分、KMP算法初解 1、普通字符串匹配BF算法与KMP算法的时间复杂度比较 这里有两种KMP算法的详解~大家可以参考 KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一．简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos j=0 起比较S[i+j] 与T[j]，若相等，则在主串S 中存在以i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即i 增1，而j 退回至0，重新开始新一轮的匹配。 例如：在串S=”abcabcabdabba”中查找T=” abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1] 和T[1]是否相等…我们发现一直比较到S[5] 和T[5]才不等。如图： 当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S 下标增1,然后再次比较。如图： 这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图： 这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图： 模式匹配的KMP算法研究 学生姓名：黄飞指导老师：罗心 摘要在计算机科学领域，串的模式匹配<以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病 毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中 查找模式串的一个或所有出现。在本文中主串表示为S=s1s2s3…sn，模式串表示为 T=t1t2…tm。串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配 算法有BF算法、KMP算法、BM算法及一些改进算法。本文主要在精确匹配方面对KMP 算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。 关键字：模式匹配；主串；模式串；KMP算法 Research and Analysis of KMP Pattern Matching Algorithm Student:Huangfei Teacher:Luoxin Abstract In computer science,String pattern matching(Hereinafter referred to as the string matching>algorithmis always the focus of the study.In the spell check, language translation, data compression, search engine, the network intrusion detection system, a computer virus signature matching DNA模式匹配的KMP算法详解
KMP算法文献综述
模式匹配KMP算法实验报告
kmp算法实验报告
KMP算法-如何理解
模式匹配KMP算法实验步骤
KMP算法实验
字符串匹配的KMP算法
(完整word版)KMP算法详解
详解KMP算法中Next数组的求法
经典KMP算法(易理解)
KMP算法源码
KMP算法步骤分析
KMP算法考题
KMP算法演算过程(讲述内容)
KMP算法的理论推导
kmp算法详解
大学课件-KMP算法
模式匹配KMP算法研究报告