C++编程练习(7)----“KMP模式匹配算法“字符串匹配

/* Index_KMP.h头文件 */
#include<string>
#include<sstream>void get_next(std::string T,int *next)
{
unsigned int i,j;
i=1;
j=0;
next[1]=0;
while(i<(T.size()-1))/* 此处T的首个字符T[0]表示串T的长度，不参与计算 */
{
if(j==0||T[i]==T[j])/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
{
++i;
++j;
next[i]=j;
}
else
j=next[j];/* 若字符不相同，则j值回溯 */
}
}int Index_KMP(std::string S, std::string T, unsigned int pos)
{
std::string s,t;/*在字符串S,T的最前插入一个字符来保存串的长度值，*/
std::ostringstream s1,s2;/*用来保证字符串的有用元素是从下标1开始*/
s1<<S.size()<<S;/*将新的数组保存为s，t*/
s2<<T.size()<<T;
s=s1.str();
t=s2.str();
unsigned int i=pos;/* i用于主串s当前位置下标值，若pos不为1，则从pos位置开始匹配 */
unsigned int j=1;/* j用于字串t中当前位置下标值 */
int next[255];/* 定义一next数组 */
get_next(t,next);/* 对串t作分析，得到next数组 */
while (i<=(s.size()-1) && j<=(t.size()-1))/* 若i小于S的长度且j小于T的长度时，循环继续 */
{
if ( j==0 || s[i]==t[j])/* 两字母相等则继续，相对于朴素算法增加了j=0判断 */
{
++i;
++j;
}
else/* 指针后退重新开始匹配 */
{
j=next[j];/* j退回合适的位置，i值不变 */
}
}
if ( j>(t.size()-1) )
return i-(t.size()-1);
else
return 0;
}

KMP模式匹配算法的改进：

/* Index_KMP.h头文件 */
#include<string>
#include<sstream>void get_nextval(std::string T,int *nextval)
{
unsigned int i,j;
i=1;
j=0;
nextval[1]=0;
while(i<(T.size()-1))/* 此处T的首个字符T[0]表示串T的长度，不参与计算 */
{
if(j==0||T[i]==T[j])/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
{
++i;
++j;
if (T[i]!=T[j])/*若当前字符与前缀字符不同*/
nextval[i]=j;/*则当前的j为nextval在i位置的值*/
else
nextval[i]=nextval[j];/*如果与前缀字符相同，则将前缀字符的nextval值赋值给nextval在i位置的值*/}
else
j=nextval[j];/* 若字符不相同，则j值回溯 */
}
}int Index_KMP(std::string S, std::string T, unsigned int pos)
{
std::string s,t;/*在字符串S,T的最前插入一个字符来保存串的长度值，*/
std::ostringstream s1,s2;/*用来保证字符串的有用元素是从下标1开始*/
s1<<S.size()<<S;/*将新的数组保存为s，t*/
s2<<T.size()<<T;
s=s1.str();
t=s2.str();
unsigned int i=pos;/* i用于主串s当前位置下标值，若pos不为1，则从pos位置开始匹配 */
unsigned int j=1;/* j用于字串t中当前位置下标值 */
int next[255];/* 定义一next数组 */
get_nextval(t,next);
while (i<=(s.size()-1) && j<=(t.size()-1))/* 若i小于S的长度且j小于T的长度时，循环继续 */
{
if ( j==0 || s[i]==t[j])/* 两字母相等则继续，相对于朴素算法增加了j=0判断 */
{
++i;
++j;
}
else/* 指针后退重新开始匹配 */
{
j=next[j];/* j退回合适的位置，i值不变 */
}
}
if ( j>(t.size()-1) )
return i-(t.size()-1);
else
return 0;
}

匹配算法不做变化，只需要将"get_next(T,next)"改为“get_nextval (T,next)”即可。



总结：改进过的KMP算法，它是在计算出 next 值的同时，如果a位字符与它 next 值指向的 b 位字符相等，则该 a 位的nextval 就指向 b 位的 nextval 值，如果不等，则该 a 位的 nextval 值就是它自己 a 位的 nextval 的值。