目录
一、概念
本节重点讨论串定位操作——模式匹配的实现算法。对串的同一种运算，在不同的存储结构上实现时其算法是不同的。由于采用链式存储时其操作与线性链表类似，并且占用的存储空间多，在大多数情况下，串值的存储采用顺序存储方式。
串的模式匹配index(s,t,start)即子串定位是一种重要的串运算。设s和t是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置；否则，匹配失败，返回0。子串t称为模式串。
二、模式匹配的基本算法（BF 算法）
实现模式匹配的最简单、直观的方法是基于蛮力法技术设计的算法，即BF算法。该算法的基本思想是，按照自左至右的顺序，从主串的第start个字符起和模式串的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的第start+1个字符起重新和模式串的字符比较。以此类推，直到模式串t中的每个字符依次和主串s中的一个连续的字符序列相等，则匹配成功；否则，匹配不成功 。对应的BF算法代码如下：
int indexBF(SqString *s,SqString *t,int start){
int i=start-1,j=0;
while(i<s->length&&j<t->length){
if(s->data[i]==t->data[j]){
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
if(j>=t->length)
return i-t->length+1;
else
return 0;
}三、KMP 算法
采用KMP算法的模式匹配过程可分为两个部分，首先对模式串t的每个字符计算其对应的k值，并保存在一个数组next中；然后利用next数组进行模式匹配。
3.1 next 数组
next数组具有如下性质：
（1）next[ j ]是一个整数，且0<=next[ j ]<j。
（2）为了使t的右移不丢失任何匹配成功的可能，当存在多个满足式的k值时，应取最大值，这样向右“滑动”的距离最短，“滑动”的字符为j-next[ j ]个。
next数组的计算 :
void getNext(SqString *t,int next[]){
int i=0,j=-1;
next[0]=-1;
while(i<t->length){
if((j==-1)||(t->data[i]==t->data[j])){
i++;
j++;
next[i]=j;
}
else{
j=next[j];
}
}
}3.2 KMP 算法
在求得模式的next数组之后，模式匹配过程为，假设以指针i和j分别指示主串和模式中的字符比较位置，令i从start开始，j的初值为1.在匹配过程中，若 si = tj ，则 i 和 j 分别增加1，继续下一个对应位置字符的比较；若 si != tj ，则 i 不变，j 退到next[ j ]位置进行下一趟比较，以此类推。直至下列两种情况：一是 j 退到某个next值时字符比较相等，则i和j分别增加1继续本趟匹配；二是 j 退到值为零（即模式的第一个字符失配），则此时 i 和 j 也要分别增1，表明从主串的下一个字符起和模式重新开始下一趟匹配。直到主串中存在一个连续的字符序列与模式串相同，则匹配成功；否则，匹配失败。
KMP算法：
int indexKmp(SqString *s,SqString *t,int start,int next[]){
int i=start-1,j=0;
while(i<s->length&&j<t->length){
if(j==-1||s->data[i]==t->data[j]); //s和t对应字符相等，比较下一个字符
i++;
j++;
}
else j=next[j]; //开始下一次匹配，子串指针j移动到下一个比较位置
if(j>=t->length+1)
return(i-t->length+1);
else
return 0;
}四、Horspool 算法
4.1 概念
Horspool算法进行模式匹配的每一趟，总是从模式串的最后一个字符开始与主串中的对应位置的字符进行比较，如果发生字符失配，则需要将模式串整体右移。在不错过匹配机会的前提下，总希望移动的幅度尽可能大。
假设对齐模式串最后一个字符的主串字符是c，Horspool算法根据c的不同情况来确定模式的移动距离。一般可能出现以下4种情况：
（1）如果模式串中不存在字符c，则模式串安全移动的距离就是模式串的长度。
（2）如果模式串中存在字符c，但它不是模式串的最后一个字符，则应将模式串中最右边的c与主串中的c对其。
（3）如果c正好是模式串的最后一个字符，但模式串的其他字符中不包含c，模式串的移动方法类似于情况（1），移动的距离就是模式串的长度。
（4）如果c正好是模式串的最后一个字符，且模式串的其他字符中也包含c，模式串的移动方法类似于情况（2），应将模式串中最右边的c与主串中的c对齐。
因此，类似于KMP算法，可以预先计算每次移动的距离并保存在一个字符移动表中，就可以在模式匹配时利用它确定下一趟匹配的模式串移动距离。
4.2 Horspool 算法
Horspool 算法：
int horspoolMathing(SqString *pat,SqString *txt,int table[]){
int i=pat->length-1,k;
while(i<=txt->length-1){
k=0;
while((k<=pat->length-1)&&(pat->data[pat->length-1-k]==txt->data[i-k])){
k++;
}
if(k==pat->length) return i-pat->length+1;
else i=i+table[txt->data[i]];
}
return -1;
}字符移动表的计算：
int shift_table(SqString *pat,int table[]){
int i,j;
for(i=0;i<N;i++){
table[i]=pat->length;
}
for(j=0;j<pat->length-1;j++){
table[pat->data[j]]=pat->length-1-j;
}
return 0;
}