串的模式匹配(KMP算法)
KMP-1. 问题及简单解决方案
什么是串
- 线性存储的一组数据(默认是字符)
- 特殊操作集
1.求串的长度
2.比较两串是否相等
3.两串相接
4.求子串
5.插入子串
6.匹配子串(有难度)
7.删除子串
什么是串的模式匹配
目标：给定一段文本，从中找出某个指定的关键字
例如从一本Thomas Love Peacock写于十九世纪的小说《Headlong Hall》中找到那个最长的单词：osseocarnisanguineoviscericartilaginonervomedullary
或者从古希腊喜剧《Assemblywomen》中找到一道菜的名字：Lopadotemachoselachogaleokranioleipsanodrimhypotrimmatosilphioparaomelitokatakechymenokichlepikossyphophattoperisteralektryonoptekephalliokigklopeleiolagoiosiraiobaphetraganopterygon
当我们文本是很长的时候，而指定的关键字也是一个很长的字符串的时候，模式匹配就不再是一件简单的事情了
PositionPatterMatch(char*string,char*pattern)//position指位置
//模式匹配就是给定一段文本(string)，给定一个模式(*pattern)，我们要通过PatterMatch函数来返回这个pattern里string第一次出现的位置
简单实现
方法1：C语言的库函数strstr
接口：char*strstr(char*string,char*pattern)
//返回的是char *这个类型的变量(指向某个字符的指针)，变量里面存的是pattern这个字符串第一个字母在string出现的时候那个字母所在的位置
//一个小Demo
#include <stdio.h>
#include <string.h>//库要记得包含进来
typedefchar*Position;//给char*重新起个名字，让不懂的人也可以知道返回的是一个位置
intmain()
{
charstring[] ="This is a simple example.";
charpattern[] ="simple";
Positionp=strstr(string,pattern);
if( p==NotFound ) printf("Mot Found.\n");//能不能找到进行一个判断
elseprintf("%s\n",p);
return0;
}
//输出：simple example.
//如果输入的找不到，就会输出一个空指针(#define NotFound NULL)
strstr的复杂度怎么样？要想知道这个问题我们就得了解一下strstr是怎么运行的
如上图，是两个指针指向两个变量的内容开头进行比对，第一个对上了对下一个，直到全部对上或者中途失败的时候将pattern的a与string下一个字符继续比对，一直循环下去，直到比对完都没成功或者中途成功了就退出循环
若给定文本长度为 n，模式长度为 m，则库函数 strstr 的最坏时间复杂度是：T = O(n*m)
当我们的pattern比较小的时候，我们这个strstr库函数还是很好用的，当两者都不小的时候就得慎重了
简单改进
方法2：从末尾开始比
时间复杂度：T=O(n)//仅仅是根据上方的例子进行的改动，如果pattern = "aab"换成"baa"一样要芭比Q
所以这个改进是没啥作用的
KMP-2. KMP 算法思路
大师改进
方法3：KMP(Knuth、Morris、Pratt)算法
T = O(n+m)
简单的往前错一位的比较是完全没有必要的没有意义的，如下图
网络异常，图片无法展示|KMP算法的想法：
网络异常，图片无法展示|指针指向x不会回退(回溯)了，直接继续从x开始，继续往前比较
网络异常，图片无法展示|
match的具体例子
下标从0到9
第0个字符对应的是一个长度为1的子串，所以他不可能产生匹配，match就永远是-1
从0到1：a跟b是配不上的，match也为-1
0-2：a和c配不上，ab和bc也配不上，所以match还是为-1
0-3：ab和ca是配不上的，abc跟bca也配不上，a对应的j为0，所以match也为0
//此时限制条件是最大i是小于j的，如果i=j的话那就相当于自己等于自己就没有意义了(p0...pj = p0...pj)
//所以我们考虑他的真子串
0-4：a跟b配不上，abc跟cab配不上，ab跟ab能配上，match值为1...
对于 pattern = abcabcacab，最后 3 个字符的 match 值是多少？-1, 0, 1
在早期的教科书上被叫做failure(失败的意思)
match值的含义：
例子：从0到6的子串，首跟尾能配上的小串，从0开始他的尾部下标为3，abca跟abca能配上。这就是match的含义
此代码块内容来自百度百科：
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
KMP算法是三位学者在Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute-Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率
模式匹配类型
(1)精确匹配
如果在目标T中至少一处存在模式P，则称匹配成功，否则即使目标与模式只有一个字符不同也不能称为匹配成功，即匹配失败。给定一个字符或符号组成的字符串目标对象T和一个字符串模式P，模式匹配的目的是在目标T中搜索与模式P完全相同的子串,返回T和P匹配的第一个字符串的首字母位置 。
(2)近似匹配
如果模式P与目标T(或其子串)存在某种程度的相似,则认为匹配成功。常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定。基本操作由字符串的插入、删除和替换来组成
KMP-3. KMP 算法实现
#include<stdio.h>
#include<string.h>
typedefintPosition;//Position对应的是一个整型变量，指的是数组的下标
#define NotFound -1//NotFound就应该定义成一个不可能是数组下标的东西
intmain()
{
charstring[] ="This is a simple example.";//默认指字符串，但这个串可以是任何类型的
charpattern[] ="simple";
Positionp=KMP(string,pattern);//返回的是一个字符指针的话就只能处理字符串，如果返回的是数组下标的话那可以处理任何字符的串
if (p==NotFound ) printf("Not Found.\n");
elseprintf("%s\n",string+p);//因为这里返回的是整数，这个整数就没办法被当作字符串的头指针了。如果我们要打印整个字符串的话，我们这里就只能写成string+p这样的形式
return0;
}
KMP算法实现
一直走到指针不匹配
PositionKMP(char*string,char*pattern )
{
intn=strlen(string);//strlen得到string的长度，下方也是一样 复杂度：O(n)
intm=strlen(pattern);//复杂度：O(m)
ints,p，*match;//声明两个指针
if(n<m) returnNotFound;//找的n不可能比m短
match= (int*)malloc(sizeof(int) *m);
BuildMatch(pattern,match);//Tm = O(?)
s=p=0;
while( s<n&&p<m){ //当这两个指针一起往前飞，任何一个指针先指到自己指的串的末尾的时候结束，复杂度O(n)
if(string[s] ==pattern[p]){ s++;p++; }//p有时候加加有时候回退，但s永远加加
elseif (p>0) p=match[p-1]+1;//为了防止得到段错误，这里加上条件p>0
//如果p = 0的话，意味着pattern从第一个字符就不匹配，这个时候p不动，s向前走一格
elses++;//当string[s] == pattern[p]不匹配，我们s++，继续下一轮匹配
}
//在我们跳出while循环的时候，p指针已经碰到pattern的末尾(p==m)，那就是完全的匹配上了
//反之p还没有到结尾，而string已经到p的结尾了，就意味着我们找不到这个模式
return (p==m) ? (s-m) : NotFound;
}
KMP的整体时间复杂度：T = O(n+m+Tm)
KMP-4. BuildMatch 的实现原理
如果采用这种方法实现的话，时间复杂度将会达到Tm = O(m³)
新想法：如果我们要算j的match值的话先考虑他跟j-1的match值有什么关系
假如我们这是从0到j-1的字段
match[j]>=match[j-1] + 1(是否正确？)
如果 match[j-1]+1 这个位置上的字符与 j 位置上的字符相等，match[j] 会有可能比 match[j-1]+1 更大吗？没可能
match[j]=match[j-1] + 1(最多持平啦，利用反证法证明)
且能得到这个结果的前提是运行很好
网络异常，图片无法展示|
当 pattern[match[j-1]+1] != pattern[j] 时，下一个待与 pattern[j] 比较的元素下标是：match[match[j-1]]+1
KMP-5. BuildMatch的编程实现
voidBuildMatch(char*pattern,int*match)
{
inti,j;
intm=strlen(pattern);//复杂度O(m)
match[0] =-1;
for(j=1;j<m;j++){//复杂度O(m)
i=match[j-1];//把这个值存入i里面，后面就可以直接用i来表示，不至于显得很长很啰嗦，怎么感觉像数学的换元法啊哈哈
while((i>=0) && (pattern[i+1] !=pattern[j]))//每次都考虑最坏情况的话复杂度可能就为O(j)了，每次都退到底的话
i=match[i];//让i做了一个回退，回退到while条件两者有其中之一不发生的时候
if(pattern[i+1]==pattern[j])
match[j] =i+1;//i回退总次数不会超过i增加的总次数
elsematch[j] =-1;
}
}
整个算法复杂度：
