?? searchmethod.cpp
字號:
// SearchMethod.cpp: implementation of the CSearchMethod class.
//采用通配符匹配字符竄的方法類接口
//語法說明:本類實現(xiàn)的通配符號有兩個"?"and"*"
// '?'----------可以代替一個字符
// '*'----------可以代替任意長度的字符竄
//example: "3*6?8"與"345678"兩個字符竄是可以匹配的
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "qq.h"
#include "SearchMethod.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
static LPCTSTR STRINGS[]=
{
"!","@","#","$","%","^","&",
"-","+","~",":","<", ">"," ","(",")","=","==",
"\\","//","|","||","&&","/*","*/",
"{","}","{}","[","]","[]",";","'",".",
"`","$$","!=",
NULL
};
CSearchMethod::CSearchMethod()
{
for(int i=0;i<50;i++)
{
serial[i]=0;//賦初值
serialchar[i]=' ';
}
}
CSearchMethod::~CSearchMethod()
{
}
//////////////////////////////////////////////////////////////////////////
/* 檢查輸入的字符是否合乎語法規(guī)則 */
//////////////////////////////////////////////////////////////////////////
bool CSearchMethod::CheckString(CString str)
{
CString strText=str;
int i=0;
while (i<strText.GetLength()&&strText[i]!=NULL)
{
int j=0;
while(STRINGS[j]!=NULL)
{
CString str1=strText[i];
if(str1==STRINGS[j])
{
return false;
}
j++;
}
i++;
}
//因為通配符*可以代替任何長度，所以不能有連續(xù)兩個**符號
int k=0;
while(k+1<strText.GetLength()&&strText[k]!=NULL&&strText[k+1]!=NULL)
{
if(strText[k]=='*'&&strText[k+1]=='*')
{
return false;
}
k++;
}
return true;
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
str1:需要匹配的字符竄
str2:源字符竄
說明：若str1中的部分或者全部字符與str2相同則稱為匹配
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
bool CSearchMethod::IsMatchString(CString str1, CString str2)
{
//先清空
for(int m=0;m<50;m++)
{
serial[m]=0;
serialchar[m]=' ';
}
//循環(huán)str1查找非特殊字符
int i=0,j=0;
while (i<str1.GetLength()&&str1[i]!=NULL)
{//search the serial and serialchar
if(str1[i]!='?'&&str1[i]!='*')
{
serial[j]=i;//保存序號
serialchar[j]=str1[i];//保存字符
j++;
}
i++;
}
bool bAllZero=true;//判斷得出的結(jié)果是否全為0
for(i=0;i<50;i++)
{
if(serial[i]==0)
{
bAllZero=bAllZero&true;
}
else
{
bAllZero=bAllZero&false;
}
}
bool bEnableMates=true;
if(bAllZero)
{//若輸入的字符全為0
if(str1.GetLength()==1)
{
if(str1[0]=='*')
{
bEnableMates=true;
}
else if(str1[0]=='?')
{
if(str2.GetLength()>1)
{
bEnableMates=false;
}
else
{
bEnableMates=true;
}
}
else
{
if(str2.GetLength()==1&&str1[0]==str2[0])
{
bEnableMates=true;
}
else
{
bEnableMates=false;
}
}
}
else
{//不是只有一位，有多位的特殊符號
BOOL bAllSame=true;//是否全為?
for(int i=0;i<str1.GetLength();i++)
{
if(str1[i]=='?')
{
bAllSame=bAllSame&true;
}
else{bAllSame=bAllSame&false;}
}
if(bAllSame)
{//全為?
if(str1.GetLength()==str2.GetLength())
{
bEnableMates=true;
}
else{bEnableMates=false;}
}
else
{
if(str1[0]!=str2[0])
{
bEnableMates=false;
}
else
{bEnableMates=true;}
}
}
}
else
{
i=0;
while(serial[i+1]!=0)
{
//得到分段的字符竄
CString s1=str1.Mid(serial[i],serial[i+1]-serial[i]+1);
int k=0,pre=0,next=0;
while(k<str2.GetLength()&&str2[k]!=NULL)
{
if(str2[k]==serialchar[i])
{
pre=k;//前一個字符
}
if(str2[k]==serialchar[i+1])
{
next=k;//后一個字符
break;
}
k++;
}
CString s2=str2.Mid(pre,next-pre+1);
bEnableMates=bEnableMates&EnableMatches(s1,s2);
i++;
}
//分析字符的前面一部分
bool bsuceess=false;
if(serial[0]!=0)
{
BOOL bAllSame=true;//是否全為'?'
for(int i=0;i<serial[0];i++)
{
if(str1[i]=='?')
{
bAllSame=bAllSame&true;
}
else
{
bAllSame=bAllSame&false;
}
}
if(bAllSame)
{//若全為'?'
int nCount=0;
for(int i=0;i<str2.GetLength();i++)
{
if(str2[i]==serialchar[0])
{
nCount=i;
break;
}
}
if(nCount==serial[0])
{//若兩個字符竄的前面一部分的字符個數(shù)相同
bEnableMates=bEnableMates&true;
}
else{bEnableMates=bEnableMates&false;}
}
else
{
bEnableMates=bEnableMates&true;
}
}
else
{
if(str1[0]==str2[0])
{
bsuceess=true;
}
else{bsuceess=false;}
bEnableMates=bEnableMates&bsuceess;
}
//分析后面一部分
bsuceess=false;
int nFirstZero=0;
for(i=0;i<50;i++)
{
if(serial[i]==0&&serial[i+1]==0)
{
nFirstZero=i;
break;
}
}
if(serial[nFirstZero-1]==str1.GetLength()-1)
{//不存在通配符號
if(serialchar[nFirstZero-1]==str2[str2.GetLength()-1])
{
bsuceess=true;
}
else{bsuceess=false;}
bEnableMates=bEnableMates&bsuceess;//將后部分的結(jié)果并入總結(jié)果中
}
else
{
if(serialchar[nFirstZero-1]==str2[str2.GetLength()-1])
{
bEnableMates=bEnableMates&false;
}
else
{
BOOL bAllSame=true;
for(int i=serial[nFirstZero-1]+1;i<str1.GetLength();i++)
{
if(str1[i]=='?')
{
bAllSame=bAllSame&true;
}
else{bAllSame=bAllSame&false;}
}
if(bAllSame)
{
int nCount=0;
for(int i=0;i<str2.GetLength();i++)
{
if(str2[i]==serialchar[nFirstZero-1])
{
nCount=i;
break;
}
}
int nLong1=str1.GetLength()-serial[nFirstZero-1]-1;
int nLong2=str2.GetLength()-nCount-1;
if(nLong1==nLong2)
{
bEnableMates=bEnableMates&true;
}
else{bEnableMates=bEnableMates&false;}
}
else{bEnableMates=bEnableMates&true;}
}
}
}
return bEnableMates;
}
bool CSearchMethod::EnableMatches(CString str1, CString str2)
{//判斷兩個首尾字符相同的字符竄是否匹配 str1="a*b",str2="acdfeb"
if(str1.GetLength()>str2.GetLength())
{
return false;
}
else
{
if(str1.GetLength()<=2&&str2.GetLength()>2)
{
return false;
}
else
{
BOOL bAllSame=true;
for (int i=1;i<str1.GetLength()-1;i++)
{
if(str1[i]=='?')
{
bAllSame=bAllSame&true;
}
else{bAllSame=bAllSame&false;}
}
if(bAllSame)
{
if(str1.GetLength()==str2.GetLength())
{
return true;
}
else{return false;}
}
else{return true;}
}
}
}
int CSearchMethod::FindingString(const char *lpszSour, const char *lpszFind, int nStart)
{
if(lpszSour == NULL || lpszFind == NULL || nStart < 0)
return -1;
int m = strlen(lpszSour);
int n = strlen(lpszFind);
if( nStart+n > m )
return -1;
if(n == 0)
return nStart;
//KMP算法
int* next = new int[n];
//得到查找字符串的next數(shù)組
{ n--;
int j, k;
j = 0;
k = -1;
next[0] = -1;
while(j < n)
{ if(k == -1 || lpszFind[k] == '?' || lpszFind[j] == lpszFind[k])
{ j++;
k++;
next[j] = k;
}
else
k = next[k];
}
n++;
}
int i = nStart, j = 0;
while(i < m && j < n)
{
if(j == -1 || lpszFind[j] == '?' || lpszSour[i] == lpszFind[j])
{ i++;
j++;
}
else
j = next[j];
}
delete []next;
if(j >= n)
return i-n;
else
return -1;
}
//功 能：帶通配符的字符串匹配
//參 數(shù)：lpszSour是一個普通字符串；
// lpszMatch是一可以包含通配符的字符串；
// bMatchCase為0，不區(qū)分大小寫，否則區(qū)分大小寫。
//返 回 值：匹配，返回1；否則返回0。
//通配符意義：
// ‘*’ 代表任意字符串，包括空字符串；
// ‘?’ 代表任意一個字符，不能為空；
bool CSearchMethod::MatchingString(const char *lpszSour, const char *lpszMatch, bool bMatchCase)
{
if(lpszSour == NULL || lpszMatch == NULL)
return false;
if(lpszMatch[0] == 0)//Is a empty string
{
if(lpszSour[0] == 0)
return true;
else
return false;
}
int i = 0, j = 0;
//生成比較用臨時源字符串'szSource'
char* szSource =
new char[ (j = strlen(lpszSour)+1) ];
if( bMatchCase )
{ //memcpy(szSource, lpszSour, j);
while( *(szSource+i) = *(lpszSour+i++) );
}
else
{ //Lowercase 'lpszSour' to 'szSource'
i = 0;
while(lpszSour[i])
{ if(lpszSour[i] >= 'A' && lpszSour[i] <= 'Z')
szSource[i] = lpszSour[i] - 'A' + 'a';
else
szSource[i] = lpszSour[i];
i++;
}
szSource[i] = 0;
}
//生成比較用臨時匹配字符串'szMatcher'
char* szMatcher = new char[strlen(lpszMatch)+1];
//把lpszMatch里面連續(xù)的“*”并成一個“*”后復(fù)制到szMatcher中
i = j = 0;
while(lpszMatch[i])
{
szMatcher[j++] = (!bMatchCase) ?
( (lpszMatch[i] >= 'A' && lpszMatch[i] <= 'Z') ?//Lowercase lpszMatch[i] to szMatcher[j]
lpszMatch[i] - 'A' + 'a' :
lpszMatch[i]
) :
lpszMatch[i]; //Copy lpszMatch[i] to szMatcher[j]
//Merge '*'
if(lpszMatch[i] == '*')
while(lpszMatch[++i] == '*');
else
i++;
}
szMatcher[j] = 0;
//開始進行匹配檢查
int nMatchOffset, nSourOffset;
bool bIsMatched = true;
nMatchOffset = nSourOffset = 0;
while(szMatcher[nMatchOffset])
{
if(szMatcher[nMatchOffset] == '*')
{
if(szMatcher[nMatchOffset+1] == 0)
{ //szMatcher[nMatchOffset]是最后一個字符
bIsMatched = true;
break;
}
else
{ //szMatcher[nMatchOffset+1]只能是'?'或普通字符
int nSubOffset = nMatchOffset+1;
while(szMatcher[nSubOffset])
{ if(szMatcher[nSubOffset] == '*')
break;
nSubOffset++;
}
if( strlen(szSource+nSourOffset) <
size_t(nSubOffset-nMatchOffset-1) )
{ //源字符串剩下的長度小于匹配串剩下要求長度
bIsMatched = false; //判定不匹配
break; //退出
}
if(!szMatcher[nSubOffset])//nSubOffset is point to ender of 'szMatcher'
{ //檢查剩下部分字符是否一一匹配
nSubOffset--;
int nTempSourOffset = strlen(szSource)-1;
//從后向前進行匹配
while(szMatcher[nSubOffset] != '*')
{
if(szMatcher[nSubOffset] == '?')
;
else
{ if(szMatcher[nSubOffset] != szSource[nTempSourOffset])
{ bIsMatched = false;
break;
}
}
nSubOffset--;
nTempSourOffset--;
}
break;
}
else//szMatcher[nSubOffset] == '*'
{ nSubOffset -= nMatchOffset;
char* szTempFinder = new char[nSubOffset];
nSubOffset--;
memcpy(szTempFinder, szMatcher+nMatchOffset+1, nSubOffset);
szTempFinder[nSubOffset] = 0;
int nPos = FindingString(szSource+nSourOffset, szTempFinder, 0);
delete []szTempFinder;
if(nPos != -1)//在'szSource+nSourOffset'中找到szTempFinder
{ nMatchOffset += nSubOffset;
nSourOffset += (nPos+nSubOffset-1);
}
else
{ bIsMatched = false;
break;
}
}
}
} //end of "if(szMatcher[nMatchOffset] == '*')"
else if(szMatcher[nMatchOffset] == '?')
{
if(!szSource[nSourOffset])
{ bIsMatched = false;
break;
}
if(!szMatcher[nMatchOffset+1] && szSource[nSourOffset+1])
{ //如果szMatcher[nMatchOffset]是最后一個字符，
//且szSource[nSourOffset]不是最后一個字符
bIsMatched = false;
break;
}
nMatchOffset++;
nSourOffset++;
}
else//szMatcher[nMatchOffset]為常規(guī)字符
{
if(szSource[nSourOffset] != szMatcher[nMatchOffset])
{ bIsMatched = false;
break;
}
if(!szMatcher[nMatchOffset+1] && szSource[nSourOffset+1])
{ bIsMatched = false;
break;
}
bool b=bIsMatched;
nMatchOffset++;
nSourOffset++;
}
}
delete []szSource;
delete []szMatcher;
return bIsMatched;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -