文档介绍：基于MATLAB 《数据结构与算法》
延边大学 信息管理专业(13级)
崔基哲
KMP模式匹配算法
MATLAB编程之基础算法
*
串的模式匹配算法
一、基本概念
1、模式匹配（定位）
设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。
2、算法目的
确定主串中所含子串第一次出现的位置（定位）
3、算法种类
KMP算法
KMP模式匹配算法
它是：在一个长字符串中匹配一个短子串的无回溯算法。
定义
s: 模式串 , m: 模式串的长度
text: 要匹配的字符串, n:text的长度
设text: x1,x2,…xn , s: a1,a2,…am, 则当存在i使 xi+k=ak(k=1,2,…m)时，认为text与模式串匹配，当然text也可能与模式串有多处匹配
例如：text: abcabca, s:abc 则text与s匹配的位置有3和6
KMP算法
作为一种无回溯的算法，它是高效的，待会儿你将看到它的时间复杂度为O(m+n)，空间复杂度也为O(m+n)
而且，它很容易理解，代码也很短
定义
next: 为对应模式串的数组
设字符串为 s1s2s3...sm ,其中s1，s2，s3，... si，... sm均是字符，则next[i]=m，当且仅当满足如下条件：字符串s1s2...sm equals 字符串s(i-m+1)...si-1 si 并且s1s2...sm s(m+1) unequals s(i-m) s(i-m+1)...si-1 si。
通俗地讲，next[i]保存了以s[i]为结尾的后缀与模式串前缀的最长匹配数。
KMP算法的运行过程
我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。
如果a[i+1]==b[j+1],i和j各加1，什么时候j==m，就说B是A的子串（B串已经整完了）
KMP算法的运行过程
如果a[i+1]!=b[j+1],这时候怎么办？
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
j=5时，a[i+1]!=b[j+1],我们要把j改成比它小的值j‘。改成多少合适呢？
KMP算法的运行过程
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
记住，我们要保持A[i-j+ 1..i]与B[1..j]完全相等，因而j’是最大的数使a[i-j’+1..i]与B[1..j’]完全相等.