串定长顺序存储方式

我们显式地在串的索引为0处存储串长。

#define MAXSTRLEN 255   // 用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN＋1]; //0号单元存放串的长度

串的模式匹配

模式匹配：设有主串S和子串T，子串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。
通常也把主串S称为目标串，把子串T称为模式串。
模式匹配成功是指在目标串S中找到一个模式串T是S的子串，返回T在S中的位置。
模式匹配不成功则指目标串S中不存在模式串T不是S的子串，返回-1。

BF算法

又称简单的、朴素的、穷举的模式匹配算法。算法的思路是
将主串的第 i 个字符和模式的第一个字符比较，

1. 若相等，继续逐个比较后续字符；直到主串的一个连续子串字符序列与模式相等。返回值为主串中模式串匹配的子序列第一个字符的序号，即匹配成功。
2. 若不等，从主串的下一字符起，重新与模式的第一个字符比较。

int Index_BF( SString S, SString T )
{// 返回模式串T在主串S中的位置。若不存在，则返回0。T非空int i = 1，j = 1;while ( i <= S[0] && j <= T[0] ) {if ( S[i] == T[j] ) {++i;++j;} // 继续比较后续字符else {i = i - j + 2;j = 1;} // 指针回溯重新开始下一趟匹配}if(j>T[0]) return i-T[0]; //返回匹配成功时主串对应的第一个字符的下标else return 0; //模式匹配不成功
} // Index_BF

时间复杂度：若主串s长度为n，模式串t长度为m
最好情况下的时间复杂度为O(m)。
算法在字符比较不相等，需要回溯（即i=i-j+1）：即退到s中的下一个字符开始进行继续匹配。
最坏情况下每趟比较m次，进行$n－m＋1$趟匹配，总比较次数为$m(n-m+1)$，时间复杂度为$O(n\times m)$。

KMP算法

KMP算法原理

KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表，KMP算法又称克努特-莫里斯-普拉特操作。KMP算法的设计思想：当出现不匹配时，利用已经比较过的已知内容，来避免将主串指针回退到已比较的字符之前。

实现KMP算法需要解决的问题：

1. 为什么主串的“指针”：i可以不回溯？
   若某趟在$S_i$和$T_j$“失配”时，
   $T_1\sim T_{j-1}=S_{i-j+1}\sim S_{i-1}$
   主串的切片$S_{i-j+1}\sim S_{i-1}$的后缀中是否有能成功匹配的前缀，仅和$T_1\sim T_{j-1}$的性质有关，可以在匹配算法之前预计算出来。

2. 若某趟在$S_i$和$T_j$“失配”时，主串中i不回溯，下一步进行$S_i$与$T_k$的比较，那么k如何求出？
   $S_{i-k+1}\sim S_{i-1}$的后缀必须是T的前缀：
   $T_1\sim T_{k-1}=S_{i-k+1}\sim S_{i-1}$
   $S_{i-k+1}\sim S_{i-1}$在上一步已经与T匹配的部分：
   $T_{j-k+1}\sim T_{j-1}=S_{i-k+1}\sim S_{i-1}$
   联立得：
   $T_1\sim T_{k-1}=T_{j-k+1}\sim T_{j-1}$
   k的解集为 K = { k ∣ k = 2 , 3 , . . . , j − 1 且  T 1 ∼ T k − 1 = T j − k + 1 ∼ T j − 1 } K=\{ k \mid k=2,3,...,j-1 \text { 且 }T _{1} \sim T _{ k -1}= T _{ j - k +1} \sim T _{ j -1} \} K={k∣k=2,3,...,j−1 且 T1​∼Tk−1​=Tj−k+1​∼Tj−1​}
   k越大，模式串滑动的距离越小，为了避免遗漏选取k的最大值$k=\max K$

模式中的前k-1个字符（最大真前缀）与模式中$T_j$字符前面的k-1个字符（最大真后缀）相等时，模式T就可以向右"滑动"至使$T_k$和$S_i$对准，继续向右进行比较即可。

滑动位置k仅与模式串T有关。
因此可以预先为模式串设定一个next数组，若令next[j]=k，则next[j]表明当模式串中的第j个字符与主串中相应字符“失配”时，模式串中需要重新和主串中该字符进行比较的字符的位置。
$next[j]=\{\begin{array}{ll}0,& 当j=1时\\ k=\max K,& 当j\ge 2,k\ne \varnothing \\ 1,& 当j\ge 2,k=\varnothing \end{array}$
其中 K = { k ∣ k = 2 , 3 , . . . , j − 1 且  T 1 ∼ T k − 1 = T j − k + 1 ∼ T j − 1 } K=\{ k \mid k=2,3,...,j-1 \text { 且 }T _{1} \sim T _{ k -1}= T _{ j - k +1} \sim T _{ j -1} \} K={k∣k=2,3,...,j−1 且 T1​∼Tk−1​=Tj−k+1​∼Tj−1​}
next[1]=0 表示T[1]与S[i]失配，下一步进行T[1]与S[i+1]的比较。
next[j]=1 表示$S_{i-k+1}\sim S_{i-1}$的后缀都不为T的前缀：下一步进行T[1]与S[i]的比较。

KMP算法实现

int Index_KMP(SString S, SString T, int pos, int next[])
{// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
// 其中，T非空，1≤pos≤StrLength(S)。int i = pos, j = 1;while ( i<=S[0] && j<=T[0] ){  if ( j==0 || S[i]==T[j] ){++i; ++j; } // 继续比较后继字符else j=next[j]; // 模式串向右移动}if(j > T[0]) return i-T[0]; // 匹配成功，返回匹配模式串的首字符下标else return 0; //匹配失败
} // Index_KMP

求模式串T的next值算法

1. 显然，next[1]=0， next[2]=1
2. 如果next[j] =k，表明有$T_1\sim T_{k-1}=T_{j-k+1}\sim T_{j-1}$，此时next[j+1]可能有两种情况：
   (1). $T_k=T_j$，则$T_1\sim T_k=T_{j-k+1}\sim T_j$，因此next[j+1]=next[j]+1=k＋1；
   (2). $T_k\ne T_j$，则相当于在模式串$T_1\sim T_k$与主串$T$的模式匹配问题中k于j失配，设$k^{\prime }=next[k]$，
   若$k^{\prime }\ge 2$，则有$T_1\sim T_{k^{\prime }-1}=T_{j-k^{\prime }+1}\sim T_{j-1}$，将k’赋给k并返回步骤2. ；
   否则说明$T_{j-k+1}\sim T_{j-1}$的真后缀中没有$T_1\sim T_k$的前缀，则next[j+1]=1

void get_next( SString T, int &next[] )
{// 求模式串T的next函数值并存入数组nextint i = 1, k = 0; next[1] = 0; while ( i < T[0] ) {	if ( k == 0 || T[i] == T[k] )    {  ++i;++k;     next[i] = k;     }else k = next[k];}
} // get_next 

时间复杂度分析

BF算法分析

最好情况下的时间复杂度为$O(m)$。
算法在字符比较不相等，需要回溯（即i=i-j+1）：即退到s中的下一个字符开始进行继续匹配。
最坏情况下每趟比较m次，进行n－m＋1趟匹配，总比较次数为m(n-m+1)，时间复杂度为$O(n\times m)$。 平均时间复杂度$O(n\times m)$

KMP算法分析

设串S的长度为n， 串T长度为m，求next数组的时间复杂度为$O(m)$，在后面的匹配中因主串S的下标不减即不回溯，比较次数可记为n，所以KMP算法平均时间复杂度为$O(n+m)$。

KMP算法与BF算法比较

1. 虽然朴素算法最坏时间复杂度为$O(n\times m)$，但一般情况下，其实际执行时间近似于$O(n+m)$，故仍被采用。
2. KMP算法仅当模式与主串存在许多“部分匹配”时才比朴素算法快得多。
3. KMP算法的最大特点是指示主串的指针i不需要回溯，这对处理从外设输入的庞大文件很有效，可以边读入边匹配而无需回头重读。