本文主要对字串匹配Like的算法实现,在SQL Server中Like的匹配中主要有表现为对两个通配符的处理,分别为“_”代表一个字符,“%”代表任意个字符。由于“%”在匹配过程中的位置任意性,所以完全匹配、通配符“_”匹配与此不应该一起参与匹配运算,所以我们决定在匹配前先将子串按“%”分段,进行逐段匹配,显然降低了匹配算法的难度,下面讲解一下算法的实现过程:(后附实现源码)
1. 确定第一个“%”的位置,
目的:确定模式匹配的方式
a> 是以“%”开头则不需要左匹配(左匹配即要求子串的第一个字符必须与原串的第一个字符相一致)
b> 不是以“%”开头则需要进行左匹配
2. 进行KMP*算法进行模式匹配
KMP算法不能完全地实现本文提到的匹配算法,我们必须对此加以修正,主要是模式因子不适合,在这里必须认为“_”的因子值为与前一个任意字符一致,所以“_”越多,匹配时的回退的可能性将越少,当然其匹配速度比教课书上的模式查找要快。
3. 继续下一个子串段的匹配工作。
下面提供算法的源码,分为两个函数,
1. _strat
为KMP*模式串查找函数,函数前有其使用说明。
2. _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
if(nPattPos == nPatternLen)
return nTextPos - nPattPos;
else
return -1;
}
}
////////////////////////////////////////////////////////////////////////////////
// 函数名称:bool _strlike(
// char * chText,
// char * chPattern,
// int nbegpos )
// 实现功能:两个字符串的匹配算法,带通配符
// 对全局变量的影响:无
// 参数说明:
// chText 原字符串
// chPattern 模式串
// nbegpos 起始位置
// 返回结果说明:
// =true 表示相似或一致
// =false 表示不相似或不一致
////////////////////////////////////////////////////////////////////////////////
bool _strlike(char * chText , char * chPattern , int nbegpos /* = 0 */)
{
bool bLeftMatch = true , bLast = false;
int nTextLen = _tcslen(chText);
//作最基础的匹配,即存在模式串的情况下再作比较
if(_tcslen(chPattern) == 0)
if(_tcslen(chText) == 0)
return true;
else
return false;
do
{
char * chFirstPattern , * chSecondPattern;
if(chPattern[0] == '%')
{
do
{
chPattern ++;
}while(chPattern[0] == '%');
if(chPattern == NULL || _tcslen(chPattern) == 0)
return true;
bLeftMatch = false;
}
else
bLeftMatch = true;
//初始化模式串
chSecondPattern = _tcschr(chPattern , '%');
int nPatternLen;
if(chSecondPattern == NULL)
{
bLast = true;
nPatternLen = _tcslen(chPattern);
if(!bLeftMatch)
{
//若以%开头,并且没有剩余模式串时,只要考虑右对齐匹配的方式即可(实际上也是左对齐)
if(nbegpos + nPatternLen <= nTextLen)
{
nbegpos = nTextLen - nPatternLen;
bLeftMatch = true;
}
else
return false;
}
else
if(nbegpos + nPatternLen != nTextLen)
return false;
}
else
{
//模式串不得长于原串
nPatternLen = chSecondPattern - chPattern;
if(nbegpos + nPatternLen > nTextLen)
return false;
}
//初始化模式串与修改剩余串
chFirstPattern = new char[nPatternLen + 1];
memcpy(chFirstPattern , chPattern , nPatternLen);
chFirstPattern[nPatternLen] = 0;
chPattern = chSecondPattern;
int npos = _strat(chText , chFirstPattern , nbegpos , bLeftMatch ? nPatternLen : nTextLen - nbegpos , bLeftMatch);
delete chFirstPattern;
if(npos < 0)
{
return false;
}
else
{
//定下一查找位置的起点
if(bLeftMatch)
{
if(npos != nbegpos)
return false;
}
else
nbegpos = npos;
if(bLast)
{
if(nPatternLen + npos == nTextLen)
return true;
else
return false;
}
else
nbegpos += nPatternLen;
}
}while(true);
}