4.3 串的模式匹配算法
4.3 串的模式匹配算法
所谓串的模式匹配运算，就是判断某串是否为另一已知串的子串，如是其子串，则给出该子串的起始点（即从已知串的第几个字符开始）。所以此运算又称为子串的定位运算。串的模式匹配算法应用非常广泛，例如，在文本编辑程序中，常常需要查找某一特定单词在文本中出现的位置。
设已知串S和串T，要求判断串T是否是串S的子串，如果是其子串则给出起始点。显然串T是串S的子串的一个必要条件是，它的长度len (T)一定要小于或等于串S的长度len (S)，即len (T)≤len (S)。
4.3.1 求子串位置的定位函数Index (S, T, pos)
子串的定位操作通常称做串的模式匹配（其中T被称为模式串），是各种串处理系统中最重要的操作之一。采用串的定长顺序存储结构，可以写出不依赖于其他串操作的匹配算法，算法如下所示：
int Index(HString S,HString T,int pos)
{
/*返回子串T在主串S中第pos个字符之后的位置。如不存在，则返回0*/
int i=pos,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;
}
在上述算法的函数过程中，分别利用计数指针i和j指示主串S和模式串T中当前正待比较的字符位置。算法的基本思想是：从主串S的第pos个字符起和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较。依此类推，直至模式串T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式串T中的第一个字符相等的字符在主串S中的序号；否则称匹配不成功，函数值为零。
例如，假设主串S为“ababcabcacbab”，模式串T为“abcac”，匹配过程如图4-3所示。
图4-3 匹配过程
当开始将串T的第1个字符与串S的第1个字符比较，头两对字符均都匹配，但第3对字符为a与c不匹配；第2轮将T的第1个字符与S的第2个字符比较，可以发现a与b不匹配；第3轮再将T的第1个字符与S的第3个字符比较，前4对字符都匹配，第5对又不匹配；这样继续下去，直至进行到第6轮时才达到完全匹配，故返回子串在S中的起始位置为6。
还存在一种称为首尾匹配的算法，先比较模式串的第1个字符，再比较模式串的最后一个字符，最后比较模式串中从第2个到第n-1个字符。
其算法描述如下：
int Index_FL(SString S, SString T, int pos)
{
/*返回子串T在主串S中第pos个字符之后的位置*/
/*若不存在，则函数值为0*/
/*其中，T非空，1≤pos≤StrLength(S)*/
sLength=S[0];tLength=T[0];
i=pos;
patStartChar=T[1];
patEndChar=T[tLength];
while(i<=sLength–tLength+1)
{
if(S[i]!=patStartChar) ++i; /*重新查找匹配起始点*/
else if(S[i+tLength-1] != patEndChar)
++i;
/*模式串的“尾字符”不匹配*/
else
{ /*检查中间字符的匹配情况*/
k = 1;j = 2;
while(j<tLength && S[i+k]=T[j])
{++k;++j; }
if(j==tLength)
return i;
else
++i; /*重新开始下一次的匹配检测*/
}
}
return 0;
}
4.3.2 模式匹配的一种改进算法
上小节两种算法的时间复杂度为O(m*n)，其比较次数较大，原因在于目标串的检测指针需要回溯。本小节将要讨论的模式匹配的一种改进算法是由D.E.Knuth、V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特—莫里斯—普拉特操作（简称为KMP算法）。此算法可以在O(m+n)的时间数量级上完成串的模式匹配操作，可使目标串的检测指针不必回溯。其改进在于：在发生失配时，主串不需要回溯，而是利用已经得到的“部分匹配”结果将模式串右移尽可能远的距离，继续进行比较。这里要强调的是，模式串不一定向右移动一个字符的位置，右移也不一定必须从模式串起点处重新试匹配，即模式串一次可以右移多个字符的位置，右移后可以从模式串起点后的某处开始试匹配。
即当S[i]<>T[j]时，已经得到的结果：S[i..i+j-2]==T[1..j-1]，若已知T[1..k-1]==T[j-k+ 1..j-1]，则有S[i-k+1] == T[1..k-1]。
可以定义模式串的next 函数，若定义next[j]=k，则next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需要重新和主串中该字符进行比较的字符的位置。模式串的next 函数的定义如下：
0 当j=1
next[j]= Max{k|1<k<j且'p[1]...p[k-1]' = 'p[j-k+1]...p[j-1]' }
1 其他情况
这样在求得了模式的next 函数之后，可按如下的KMP算法进行匹配：
int Index_KMP(SString S, SString T, int pos)
{
/* 利用模式串T的next函数求T在主串S中第pos个位置*/
/* 字符之后的位置的KMP算法。其中，T非空*/
/* 1≤pos≤StrLength(S) */
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;
}
现在的问题就是如何求得模式的next 函数，而求next函数值的过程实际上是一个递推过程，分析如下：
已知：next[1] = 0；
假设：next[j] = k；又T[j] = T[k];
则：next[j+1] = k+1;
若：T[j]！=T[k];
则需往前回溯，检查T[j] == T[？];
这实际上也是一个匹配的过程，只是主串和模式串是同一个串。求模式串T的next函数值的算法如下：
void get_next(SString &T,int &next[ ])
{
/* 求模式串T的next函数值并存入数组next中*/
i=1; next[1]=0;j=0;
while (i < T[0])
{
if(j==0 || T[i]==T[j])
{ ++i; ++j;next[i]=j;}
else j=next[j];
}
}