串的基本操作可以参照考研数据结构-串(串的基本操作)，除去这些基本操作外，还有一个重要的操作就是串的模式匹配算法。模式匹配算法就是，对于一个串中某个子串的定位操作，这里会讲两种模式匹配算法：简单模式匹配算法和KMP算法。
一、简单模式匹配算法
简单模式匹配算法的思路
简单模式匹配算法的思路就是：从主串的第一个位置起和模式串的第一个字符开始比较，如果相等则继续往后逐一比较。如果不相等，则从主串的第二个字符开始，重复上述的操作，直到在主串中找到与模式串相等的子串。如果成功则返回模式串在主串中的位置，否则可以返回NULL、FALSE或区别于主串所有位置的标记。
int Simple_index(Str2 str,Str2 substr)
{
int i=1,j=1,k=i; //串的下标从1位置开始存储，so 值为1
while (i <= str.length && j<substr.length)
{
/* code */
if (str.ch[i] == substr.ch[j])
{
/* code */
++i;
++j;
}else{
j=1;
i=++k; //匹配失败，i从主串的下一个位置开始，k中记录了上一次的起始位置
}
}
if (i > substr.length)
{
/* code */
return k;
}else{
return 0;
}
}
二、KMP算法
由简单模式算法可以看出，在主串中每当碰到一个与模式串中字符不匹配的位置，简单模式匹配都会从主串中的第i-j+2个位置开始重新匹配，这样的过程十分繁琐，所以需要引入一个更加高效的算法来寻找主串中与模式串相匹配的子串位置。
KMP算法的思路
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串（也称文本串）的匹配次数，以达到快速匹配的目的。具体实现是通过一个next()函数（或称为失配函数、部分匹配表），该函数包含了模式串的局部匹配信息。
首先需要对模式串进行预处理，计算模式串的next数组。next数组记录了模式串中每个位置之前的子串的最长相等的前缀和后缀的长度（特殊地，next[1]一般设为0，表示模式串的起始位置没有前缀和后缀）。这个预处理过程的时间复杂度为O(m)，其中m是模式串的长度。
其次进行匹配，使用next数组进行模式匹配。设主串的长度为n，模式串的长度为m。在匹配过程中，当发现不匹配时，不是像暴力匹配那样将主串的指针回溯，而是利用next数组将模式串的指针移动到下一个可能匹配的位置，继续匹配。这个过程的时间复杂度为O(n)。
void getnext(Str2 substr,int next[])
{
int i=1,j=0; // 串从数组下标1位置开始存储
next[1] = 0;
while (i<substr.length)
{
/* code */
if (j==0 || substr.ch[i]==substr.ch[j])
{
/* code */
++i;
++j;
next[i] = j;
}else{
j = next[j];
}
}
}得到next数组后，将简单匹配算法稍微修改就可以得到KMP算法
void KMP(Str2 str,Str2 substr,int next[])
{
int i=1,j=1; //串从下标1开始存储，初始值为1
while (i<=str.length && j<=substr.length)
{
/* code */
if (j==0 || str.ch[i] == substr.ch[j])
{
/* code */
++i;
++j;
}else{
j = next[j];
}
if (j>substr.length)
{
/* code */
return i-substr.length;
}else{
return 0;
}
}
}