4.3 串的算法

串的模式匹配算法：
算法目的：确定主串中所含子串（模式串）第一次出现的位置（定位）
算法种类：
（1）BE算法（Bruce-Force，又称古典的、经典的、朴素的、穷举的）
（2）KMP算法（特点：速度快）
BF算法：亦称简单匹配算法，采用穷举法的思路
Index(S,T,pos)
将主串的第pos个字符和模式串的第一个字符比较
（1）若相等，继续逐个比较后续字符；
（2）若不等，从主串的下一个字符起，重新与模式串的第一个字符比较
（3）直到主串的一个连续子串字符序列与模式串相等，返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功
（4）否则，匹配失败，返回值0
算法描述：
int Index BF(SString S,SString T){
int i=1,j=1;
while(i<=S.length && j<=T.length){
if(s.ch[i]==t.ch[j]){++i;++j;}//主串和子串依次匹配下一个字符
else{i=i-j+2;j=1;}//主串。子串指针回溯重新开始下一次匹配
}
if (j>=T.length) return i-T.length;//返回匹配的第一个字符的下标
else return 0;//模式匹配不成功
}
算法时间复杂度：若n为主串长度，m为子串长度，若m<KMP(Knuth Morris Pratt)算法（三个科学家名字的首字母命名）
算法设计思想：利用已经部分匹配的结果而加快模式串的滑动速度，且主串S的指针i不必回溯，可提速到O(n+m)，为此，定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置
算法描述：
int Index_KMP(SString S,SString T, int pos){
i=pos,j=1;
while(i<=S.length && j<=T.length){
if(j=0 || S.ch[i]==T.ch[j]){++i;++j;}//主串和子串依次匹配下一个字符
else
j=next[j];// i不变，j后退
}
if (j>=T.length) return i-T.length;//匹配成功
else return 0;//模式不匹配标志
}
void get_next(SString T,int &next[]){
i=1;next[1] =0; j=0;
while(iif(j==0 || T.ch[i]==T.ch[j]){
++i;++j;
next[i]=j;
}
else
j=next[j];
}
}
void get_nextval(SString T,int &nextval[]){
i=1;nextval[1] =0; j=0;
while(iif(j==0 || T.ch[i]==T.ch[j]){
++i;++j;
if(T.ch[i] != T.ch[j]) nextval[i] = j;
else nextval[i] =nextval[j];
}
else j=nextval[j];
}
}