文档介绍：串的模式匹配算法
*
第1页，共21页，编辑于2022年，星期一
算法目的：确定主串中所含子串第一次出现的位置（定位）
串的模式匹配算法
BF算法（又称古典的、经典的、朴素的、穷举的）
KMP算法
算且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ }
1 其他情况
讨论：
（1） next[ j ]的物理意义是什么？
（2） next[ j ]具体怎么求？—即KMP算法的实现
令k = next[ j ]（k 与j 显然具有函数关系），则
取T首与Tj处最大的相同子串
新起点 k怎么求？
*
第8页，共21页，编辑于2022年，星期一
（1） next[ j ]有何物理意义？
next[j]函数表征着模式T中最大相同前缀子串和后缀子串（真子串）的长度。
可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。
即：next[j]越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。
next[ j ]＝max { k |1<k<j 且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ }
模式串从第1位往右直到K-1位
模式串从j的前一位往左经过K-1位
想一想：如果主串和模式均为二进制码流，用KMP算法效果如何？
T=‘a b a a b c a c’
再想一想：如果主串是外存中一个大文件，用KMP算法效果又如何？
（2） next[ j ]具体怎么求？—即KMP算法的实现
*
第9页，共21页，编辑于2022年，星期一
计算Next[j]的方法：
当j=1时，Next[j]=0；
//Next[j]=0表示根本不进行字符比较
当j>1时，Next[j]的值为：模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度加1。
无首尾相同的子串时Next[j]的值为1。
// Next[j]=1表示从模式串头部开始进行字符比较
（2） next[ j ]怎么计算？
怎样计算模式T所有可能的失配点 j 所对应的 next[j]？
*
第10页，共21页，编辑于2022年，星期一
从两头往中间比较
模式串 T： a b a a b c a c
可能失配位 j： 1 2 3 4 5 6 7 8
新匹配位k=next[j] :
next[ j ]＝
0 当j＝1时
max { k |1<k<j 且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ }
1 其他情况
0
1
1
2
2
3
1
2
讨论：
j=1时, next[ j ]≡ 0；//属于“j=1”情况;
j=2时, next[ j ]≡ 1；// 找不到1<k<j的k，属于“其他情况”；
刚才已归纳：
j=3时, k={2}，只需查看‘T1’=‘T2’成立否，No则属于其他情况
j=4时, k={2，3}，要查看‘T1’=‘T3’ 及‘T1T2’=‘T2 T3’ 是否成立
j=5时, k={2，3，4}，要查看‘T1’=‘T4’ ，‘T1T2’=‘T3T4’ 和
‘T1T2T3’=‘T2T3T4’
以此类推，可得后续next[j]值。
可用演示程序验证
next[j]与s无关，可以预先计算
例：
*
第11页，共21页，编辑于2022年，星期一
下一个要讨论的问题是：如何用递推方式来求出最大相同子串的长度呢？换言之，如何让电脑替我们求出最大相同子串呢？这个问题一旦解决，整个KMP算法就可以掌握得很透彻了。
void get_next(SString T, int &next[ ] ){ //
//求模式串T的next函数值并存入数组next[ ]。
i=1; next[1]=0; j=0;
while(i<T[0] ){
if(j= = 0||T[i]= =T[j]){++i; ++j; next[i]=j;}
else j=next[j];
}
}// get_next
递推法编程，参见教材P83程序
*
第12页，共21页，编辑于2022年，星期一
求解next[j]流程图（递推）
i=1; j=0
next[1]=0
i<T[0]
j==0 || T[i]==T[j]
++i; ++j;
next[i]=j;
j=next[