串的模式匹配算法理论与思想
串的模式匹配算法
一、基本概念
1、模式匹配（定位）
设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。
2、算法目的
确定主串中所含子串第一次出现的位置（定位）
3、算法种类
BF算法 （又称古典的、经典的、朴素的、穷举的）
KMP算法
1、Brute-Force算法的设计思想：
• 将主串S的第一个字符和模式T的第1个字符比较，
若相等，继续逐个比较后续字符；
若不等，从主串S的下一字符起，重新与T第一个字符比较。
• 直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
否则，匹配失败，返回值 -1。
2、 Brute-Force算法的实现
typedef struct
{ char str[MaxSize];
int length;
}String;
int BFIndex(String S, int start, String T)
{ int i = start, j = 0, v;
while(i < S.length && j < T.length)
{ if(S.str[i] == T.str[j]) {i++; j++; }
else{ i = i-j+1; j = 0; }
}
if (j==T.length) v=i-T.length;
else v=-1;
return v;
}
3、BF算法的时间复杂度
讨论：
若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m＝O(n*m)
最好的情况是：一配就中！ 只比较了m次。
最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还要加上m！所以总次数为：(n-m)*m+m ＝(n-m+1)*m
能否利用已部分匹配过的信息而加快模式串的滑动速度？
能！而且主串S的指针i不必回溯！最坏情况也能达到O(n+m)
请看KMP算法！
三、KMP算法
１、KMP算法设计思想：
尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。
如图：
需要讨论两个问题：
①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？
② 模式应该向右滑多远才是高效率的?
如图：
新起点 k怎么求？
根据模式串T的规律： “T0…Tk-1”=“Tj-k …Tj-1”
由当前失配位置j(已知) ，可以归纳计算新起点 k的表达式。
如图：
（1）k值仅取决于模式串本身而与相匹配的主串无关。
（2）k值为模式串从头向后及从j向前的两部分的最大相同子串的长度。
（3）这里的两部分子串可以有部分重叠的字符，但不可以全部重叠。
next[j]函数表征着模式T中最大相同前缀子串和后缀子串（真子串）的长度。
可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。
即：next[j]越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。
再想一想：如果主串是外存中一个大文件，用KMP算法效果又如何？
如图：
下一个要讨论的问题是：如何用递推方式来求出最大相同子串的长度呢？这个问题一旦解决，整个KMP算法就可以掌握得很透彻了。
求子串next[i]值的算法：
void GetNext(String T, int next[])
{ int j = 0, k = 0;
next[0] = -1;
while(j < T.length){
if(T.str[j]==T.str[k])
{ next[j+1]=k+1; j++; k++; }
else if (k==0){ next[j+1]=0; j++; }
else k=next[k];
}
}
KMP算法的思想
设s为主串，t为模式串，设i为主串s当前比较字符的下标，j为模式串t当前比较字符的下标，令i和j的初值为０。当si = tj时，i和j分别增1再继续比较；否则 i不变，j改变为next[j]值（即模式串右滑）后再继续比较。依次类推，直到出现下列两种情况之一：一是 j退回到某个j=next[j]值时有si = tj ，则 i和j分别增1后再继续比较；二是j退回到j=-1时，令主串和子串的下标各增1，随后比较si+1和t0 。这样的循环过程一直进行到变量大于等于S.length或变量j大于等于T.length时为止。
KMP算法的实现
第一步，先把模式T所有可能的失配点j 所对应的next[j]计算出来；
第二步：执行定位函数Index_kmp （与BF算法模块非常相似）
int KMPIndex(String S, int start,String T, int next[ ])
{int i=start,j=0,v;
while ( i<=S.length && j<T.length ) {
if (j==-1|| S.str[i] = = T.str[j] ) {i++; j++ } //不失配则继续比较后续字符
else j=next[j]; //特点：S第一步，先把模式T所有可能的失配点j 所对应的next[j]
}
if(j==T.length) v=I-T.length;
else v=-1;
return v;
}
主函数
void main(void)
{ String S = {{"cddcdc"}, 6}, T = {{"cdc"}, 3};
int next[8], pos;
GetNext(T, next);
pos = KMPIndex(S, 0, T, next);
printf("pos = %d\n", pos);
}
2、KMP算法的时间复杂度
回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为： (n-m+1)*m＝O(n*m)
而此时KMP的情况是：由于指针i无须回溯，比较次数仅为n,即使加上计算next[j]时所用的比较次数m，比较总次数也仅为n+m=O(n＋m)，大大快于BF算法
注意：由于BF算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍被广泛采用。
KMP算法的用途：
因为主串指针i不必回溯，所以从外存输入文件时可以做到边读入边查找——“流水作业”
如图：
