本文主要对字串匹配Like的算法实现，在SQL Server中Like的匹配中主要有表现为对两个通配符的处理，分别为“_”代表一个字符，“%”代表任意个字符。由于“%”在匹配过程中的位置任意性，所以完全匹配、通配符“_”匹配与此不应该一起参与匹配运算，所以我们决定在匹配前先将子串按“%”分段，进行逐段匹配，显然降低了匹配算法的难度，下面讲解一下算法的实现过程：（后附实现源码）
１. 确定第一个“%”的位置，
目的：确定模式匹配的方式
a> 是以“%”开头则不需要左匹配（左匹配即要求子串的第一个字符必须与原串的第一个字符相一致）
b> 不是以“%”开头则需要进行左匹配
２. 进行ＫＭＰ*算法进行模式匹配
ＫＭＰ算法不能完全地实现本文提到的匹配算法，我们必须对此加以修正，主要是模式因子不适合，在这里必须认为“_”的因子值为与前一个任意字符一致，所以“_”越多，匹配时的回退的可能性将越少，当然其匹配速度比教课书上的模式查找要快。
３. 继续下一个子串段的匹配工作。
下面提供算法的源码，分为两个函数，
１. _strat
为ＫＭＰ*模式串查找函数，函数前有其使用说明。
２. _strlike
为Like的实现过程，内部用到_strat模式串匹配函数，实现的关键是对模式串的分段，来降低匹配的难度。
////////////////////////////////////////////////////////////////////////////////
// 函数名称：int _strat(
// char * chText,
// char * chPattern,
// int nbegpos,
// int nlen
// bool bleft )
// 实现功能：模式串搜索
// 对全局变量的影响：无
// 参数说明：
// chText 原串
// chPattern 模式串
// nbegpos 起始位置
// nlen 原串相对长度
// bleft 是否左对齐(即第一个字符必须一致)
// 返回结果说明：实际位置
// 待优化一：回退数不得大于nlen - len(chPattern)，即回退后无法导致完全匹配
// 待优化二：计算模式串与字串搜索代码合并，减少计算量
////////////////////////////////////////////////////////////////////////////////
int _strat(char * chText , char * chPattern , int nbegpos /* = 0 */ , int nlen /* = -1 */ , bool bleft /* = false */)
{
int nPatternLen = _tcslen(chPattern);
int nTextLen = _tcslen(chText);
if(nlen >= 0)
{
if(nbegpos + nlen < nTextLen)
nTextLen = nbegpos + nlen;
}
if(nbegpos + nPatternLen > nTextLen || nPatternLen > MAXLEN_PATTERN)
return -1;
if(nPatternLen == 0)
return nbegpos;
else
{
int nGeneralLen = 0;
short chNext[MAXLEN_PATTERN] = { -1 };
int nPattPos = 0 , nNext = -1;
if(!bleft)
{
//生成模式回退值
while(nPattPos < nPatternLen)
{
if( nNext == -1 || chPattern[nPattPos] == '_' || chPattern[nPattPos] == chPattern[nNext])
{
nPattPos ++;
nNext ++;
chNext[nPattPos] = nNext;
}
else
nNext = chNext[nNext];
}
}
int nTextPos = nbegpos;
nPattPos = 0;
//进行模式匹配
while(nPattPos < nPatternLen && nTextPos < nTextLen)
{
if(nPattPos == -1 || chPattern[nPattPos] == '_' || chPattern[nPattPos] == chText[nTextPos])
{
nPattPos ++;
nTextPos ++;
}
else
{
//要求左对齐时，不允许回退（回退时肯定不是左对齐的）
if(bleft)
return -1;
else
nPattPos = chNext[nPattPos];
}
}
//判断模式串是否已经完全被匹配，否则返回-1
&
| 