SearchMethod.cpp
上传用户:czfddz
上传日期:2013-03-20
资源大小:1517k
文件大小:12k
源码类别:

酒店行业

开发平台:

C/C++

  1. // SearchMethod.cpp: implementation of the CSearchMethod class.
  2. //采用通配符匹配字符窜的方法类接口
  3. //语法说明:本类实现的通配符号有两个"?"and"*"
  4. //   '?'----------可以代替一个字符
  5. //   '*'----------可以代替任意长度的字符窜
  6. //example: "3*6?8"与"345678"两个字符窜是可以匹配的
  7. //////////////////////////////////////////////////////////////////////
  8. #include "stdafx.h"
  9. #include "qq.h"
  10. #include "SearchMethod.h"
  11. #ifdef _DEBUG
  12. #undef THIS_FILE
  13. static char THIS_FILE[]=__FILE__;
  14. #define new DEBUG_NEW
  15. #endif
  16. //////////////////////////////////////////////////////////////////////
  17. // Construction/Destruction
  18. //////////////////////////////////////////////////////////////////////
  19. static LPCTSTR STRINGS[]=
  20. {
  21. "!","@","#","$","%","^","&",
  22. "-","+","~",":","<", ">"," ","(",")","=","==",
  23. "\","//","|","||","&&","/*","*/",
  24. "{","}","{}","[","]","[]",";","'",".",
  25. "`","$$","!=",
  26. NULL
  27. };
  28. CSearchMethod::CSearchMethod()
  29. {
  30. for(int i=0;i<50;i++)
  31. {
  32. serial[i]=0;//赋初值
  33. serialchar[i]=' ';
  34. }
  35. }
  36. CSearchMethod::~CSearchMethod()
  37. {
  38. }
  39. //////////////////////////////////////////////////////////////////////////
  40. /*             检查输入的字符是否合乎语法规则               */
  41. //////////////////////////////////////////////////////////////////////////
  42. bool CSearchMethod::CheckString(CString str)
  43. {
  44. CString strText=str;
  45. int i=0;
  46. while (i<strText.GetLength()&&strText[i]!=NULL)
  47. {
  48. int j=0;
  49. while(STRINGS[j]!=NULL)
  50. {
  51. CString str1=strText[i];
  52. if(str1==STRINGS[j])
  53. {
  54. return false;
  55. }
  56. j++;
  57. }
  58. i++;
  59. }
  60. //因为通配符*可以代替任何长度,所以不能有连续两个**符号
  61. int k=0;
  62.     while(k+1<strText.GetLength()&&strText[k]!=NULL&&strText[k+1]!=NULL)
  63. {
  64. if(strText[k]=='*'&&strText[k+1]=='*')
  65. {
  66. return false;
  67. }
  68. k++;
  69. }
  70.     return true;
  71. }
  72. /*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  73.                    str1:需要匹配的字符窜
  74.                    str2:源字符窜
  75.          说明:若str1中的部分或者全部字符与str2相同则称为匹配
  76. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
  77. bool CSearchMethod::IsMatchString(CString str1, CString str2)
  78. {
  79.        //先清空
  80. for(int m=0;m<50;m++)
  81. {
  82. serial[m]=0;
  83. serialchar[m]=' ';
  84. }
  85.     //循环str1查找非特殊字符
  86. int i=0,j=0;
  87. while (i<str1.GetLength()&&str1[i]!=NULL)
  88. {//search the serial and serialchar
  89. if(str1[i]!='?'&&str1[i]!='*')
  90. {
  91.             serial[j]=i;//保存序号
  92. serialchar[j]=str1[i];//保存字符
  93. j++;
  94. }
  95. i++;
  96. }
  97. bool bAllZero=true;//判断得出的结果是否全为0
  98. for(i=0;i<50;i++)
  99. {
  100. if(serial[i]==0)
  101. {
  102. bAllZero=bAllZero&true;
  103. }
  104. else
  105. {
  106. bAllZero=bAllZero&false;
  107. }
  108. }
  109. bool bEnableMates=true;
  110. if(bAllZero)
  111. {//若输入的字符全为0
  112. if(str1.GetLength()==1)
  113. {
  114.             if(str1[0]=='*')
  115. {
  116. bEnableMates=true;
  117. }
  118. else if(str1[0]=='?')
  119. {
  120. if(str2.GetLength()>1)
  121. {
  122. bEnableMates=false;
  123. }
  124. else
  125. {
  126. bEnableMates=true;
  127. }
  128. }
  129. else
  130. {
  131. if(str2.GetLength()==1&&str1[0]==str2[0])
  132. {
  133. bEnableMates=true;
  134. }
  135. else
  136. {
  137. bEnableMates=false;
  138. }
  139. }
  140. }
  141. else
  142. {//不是只有一位,有多位的特殊符号
  143. BOOL bAllSame=true;//是否全为?
  144. for(int i=0;i<str1.GetLength();i++)
  145. {
  146.                 if(str1[i]=='?')
  147. {
  148. bAllSame=bAllSame&true;
  149. }
  150. else{bAllSame=bAllSame&false;}
  151. }
  152. if(bAllSame)
  153. {//全为?
  154. if(str1.GetLength()==str2.GetLength())
  155. {
  156. bEnableMates=true;
  157. }
  158. else{bEnableMates=false;}
  159. }
  160. else
  161. {
  162. if(str1[0]!=str2[0])
  163. {
  164. bEnableMates=false;
  165. }
  166. else
  167. {bEnableMates=true;}
  168. }
  169. }
  170. }
  171. else
  172. {
  173. i=0;
  174. while(serial[i+1]!=0)
  175. {
  176. //得到分段的字符窜
  177. CString s1=str1.Mid(serial[i],serial[i+1]-serial[i]+1);
  178. int k=0,pre=0,next=0;
  179. while(k<str2.GetLength()&&str2[k]!=NULL)
  180. {
  181. if(str2[k]==serialchar[i])
  182. {
  183. pre=k;//前一个字符
  184. }
  185. if(str2[k]==serialchar[i+1])
  186. {
  187. next=k;//后一个字符
  188. break;
  189. }
  190. k++;
  191. }
  192. CString s2=str2.Mid(pre,next-pre+1);
  193. bEnableMates=bEnableMates&EnableMatches(s1,s2);
  194. i++;
  195. }
  196. //分析字符的前面一部分
  197. bool bsuceess=false;
  198. if(serial[0]!=0)
  199. {
  200. BOOL bAllSame=true;//是否全为'?'
  201. for(int i=0;i<serial[0];i++)
  202. {
  203. if(str1[i]=='?')
  204. {
  205. bAllSame=bAllSame&true;
  206. }
  207. else
  208. {
  209. bAllSame=bAllSame&false;
  210. }
  211. }
  212. if(bAllSame)
  213. {//若全为'?'
  214.                 int nCount=0;
  215. for(int i=0;i<str2.GetLength();i++)
  216. {
  217. if(str2[i]==serialchar[0])
  218. {
  219. nCount=i;
  220. break;
  221. }
  222. }
  223. if(nCount==serial[0])
  224. {//若两个字符窜的前面一部分的字符个数相同
  225.                     bEnableMates=bEnableMates&true;
  226. }
  227. else{bEnableMates=bEnableMates&false;}
  228. }
  229. else
  230. {
  231. bEnableMates=bEnableMates&true;
  232. }
  233. }
  234. else
  235. {
  236. if(str1[0]==str2[0])
  237. {
  238. bsuceess=true;
  239. }
  240. else{bsuceess=false;}
  241.             bEnableMates=bEnableMates&bsuceess;
  242. }
  243. //分析后面一部分
  244. bsuceess=false;
  245. int nFirstZero=0;
  246. for(i=0;i<50;i++)
  247. {
  248. if(serial[i]==0&&serial[i+1]==0)
  249. {
  250. nFirstZero=i;
  251. break;
  252. }
  253. }
  254.             if(serial[nFirstZero-1]==str1.GetLength()-1)
  255. {//不存在通配符号
  256.                  if(serialchar[nFirstZero-1]==str2[str2.GetLength()-1])
  257.  {
  258.  bsuceess=true;
  259.  }
  260.  else{bsuceess=false;}
  261.  bEnableMates=bEnableMates&bsuceess;//将后部分的结果并入总结果中
  262. }
  263. else
  264. {
  265. if(serialchar[nFirstZero-1]==str2[str2.GetLength()-1])
  266. {
  267. bEnableMates=bEnableMates&false;
  268. }
  269. else
  270. {
  271. BOOL bAllSame=true;
  272. for(int i=serial[nFirstZero-1]+1;i<str1.GetLength();i++)
  273. {
  274. if(str1[i]=='?')
  275. {
  276. bAllSame=bAllSame&true;
  277. }
  278. else{bAllSame=bAllSame&false;}
  279. }
  280. if(bAllSame)
  281. {
  282.                         int nCount=0;
  283. for(int i=0;i<str2.GetLength();i++)
  284. {
  285. if(str2[i]==serialchar[nFirstZero-1])
  286. {
  287. nCount=i;
  288. break;
  289. }
  290. }
  291. int nLong1=str1.GetLength()-serial[nFirstZero-1]-1;
  292. int nLong2=str2.GetLength()-nCount-1;
  293. if(nLong1==nLong2)
  294. {
  295. bEnableMates=bEnableMates&true;
  296. }
  297. else{bEnableMates=bEnableMates&false;}
  298. }
  299. else{bEnableMates=bEnableMates&true;}
  300. }
  301. }
  302. }
  303. return bEnableMates;
  304. }
  305. bool CSearchMethod::EnableMatches(CString str1, CString str2)
  306. {//判断两个首尾字符相同的字符窜是否匹配 str1="a*b",str2="acdfeb"
  307.     if(str1.GetLength()>str2.GetLength())
  308. {
  309. return false;
  310. }
  311. else
  312. {
  313. if(str1.GetLength()<=2&&str2.GetLength()>2)
  314. {
  315. return false;
  316. }
  317. else 
  318. {
  319. BOOL bAllSame=true;
  320. for (int i=1;i<str1.GetLength()-1;i++)
  321. {
  322. if(str1[i]=='?')
  323. {
  324. bAllSame=bAllSame&true;
  325. }
  326. else{bAllSame=bAllSame&false;}
  327. }
  328. if(bAllSame)
  329. {
  330. if(str1.GetLength()==str2.GetLength())
  331. {
  332. return true;
  333. }
  334. else{return false;}
  335. }
  336.             else{return true;}
  337. }
  338. }
  339. }
  340. int CSearchMethod::FindingString(const char *lpszSour, const char *lpszFind, int nStart)
  341. {
  342.     if(lpszSour == NULL || lpszFind == NULL || nStart < 0)
  343. return -1;
  344. int m = strlen(lpszSour);
  345. int n = strlen(lpszFind);
  346. if( nStart+n > m )
  347. return -1;
  348. if(n == 0)
  349. return nStart;
  350. //KMP算法
  351. int* next = new int[n];
  352. //得到查找字符串的next数组
  353. { n--;
  354. int j, k;
  355. j = 0;
  356. k = -1;
  357. next[0] = -1;
  358. while(j < n)
  359. { if(k == -1 || lpszFind[k] == '?' || lpszFind[j] == lpszFind[k])
  360. { j++;
  361. k++;
  362. next[j] = k;
  363. }
  364. else
  365. k = next[k];
  366. }
  367. n++;
  368. }
  369. int i = nStart, j = 0;
  370. while(i < m && j < n)
  371. {
  372. if(j == -1 || lpszFind[j] == '?' || lpszSour[i] == lpszFind[j])
  373. { i++;
  374. j++;
  375. }
  376. else
  377. j = next[j];
  378. }
  379. delete []next;
  380. if(j >= n)
  381. return i-n;
  382. else
  383. return -1;
  384. }
  385. //功   能:带通配符的字符串匹配
  386. //参   数:lpszSour是一个普通字符串;
  387. //   lpszMatch是一可以包含通配符的字符串;
  388. //   bMatchCase为0,不区分大小写,否则区分大小写。
  389. //返  回  值:匹配,返回1;否则返回0。
  390. //通配符意义:
  391. // ‘*’ 代表任意字符串,包括空字符串;
  392. // ‘?’ 代表任意一个字符,不能为空;
  393. bool CSearchMethod::MatchingString(const char *lpszSour, const char *lpszMatch, bool bMatchCase)
  394. {
  395.     if(lpszSour == NULL || lpszMatch == NULL)
  396. return false;
  397. if(lpszMatch[0] == 0)//Is a empty string
  398. {
  399. if(lpszSour[0] == 0)
  400. return true;
  401. else
  402. return false;
  403. }
  404. int i = 0, j = 0;
  405. //生成比较用临时源字符串'szSource'
  406. char* szSource =
  407. new char[ (j = strlen(lpszSour)+1) ];
  408. if( bMatchCase )
  409. { //memcpy(szSource, lpszSour, j);
  410. while( *(szSource+i) = *(lpszSour+i++) );
  411. }
  412. else
  413. { //Lowercase 'lpszSour' to 'szSource'
  414. i = 0;
  415. while(lpszSour[i])
  416. { if(lpszSour[i] >= 'A' && lpszSour[i] <= 'Z')
  417. szSource[i] = lpszSour[i] - 'A' + 'a';
  418. else
  419. szSource[i] = lpszSour[i];
  420. i++;
  421. }
  422. szSource[i] = 0;
  423. }
  424. //生成比较用临时匹配字符串'szMatcher'
  425. char* szMatcher = new char[strlen(lpszMatch)+1];
  426. //把lpszMatch里面连续的“*”并成一个“*”后复制到szMatcher中
  427. i = j = 0;
  428. while(lpszMatch[i])
  429. {
  430. szMatcher[j++] = (!bMatchCase) ?
  431. ( (lpszMatch[i] >= 'A' && lpszMatch[i] <= 'Z') ?//Lowercase lpszMatch[i] to szMatcher[j]
  432. lpszMatch[i] - 'A' + 'a' :
  433. lpszMatch[i]
  434. ) :
  435. lpszMatch[i];  //Copy lpszMatch[i] to szMatcher[j]
  436. //Merge '*'
  437. if(lpszMatch[i] == '*')
  438. while(lpszMatch[++i] == '*');
  439. else
  440. i++;
  441. }
  442. szMatcher[j] = 0;
  443. //开始进行匹配检查
  444. int nMatchOffset, nSourOffset;
  445. bool bIsMatched = true;
  446. nMatchOffset = nSourOffset = 0;
  447. while(szMatcher[nMatchOffset])
  448. {
  449. if(szMatcher[nMatchOffset] == '*')
  450. {
  451. if(szMatcher[nMatchOffset+1] == 0)
  452. { //szMatcher[nMatchOffset]是最后一个字符
  453. bIsMatched = true;
  454. break;
  455. }
  456. else
  457. { //szMatcher[nMatchOffset+1]只能是'?'或普通字符
  458. int nSubOffset = nMatchOffset+1;
  459. while(szMatcher[nSubOffset])
  460. { if(szMatcher[nSubOffset] == '*')
  461. break;
  462. nSubOffset++;
  463. }
  464. if( strlen(szSource+nSourOffset) <
  465. size_t(nSubOffset-nMatchOffset-1) )
  466. { //源字符串剩下的长度小于匹配串剩下要求长度
  467. bIsMatched = false; //判定不匹配
  468. break; //退出
  469. }
  470. if(!szMatcher[nSubOffset])//nSubOffset is point to ender of 'szMatcher'
  471. { //检查剩下部分字符是否一一匹配
  472. nSubOffset--;
  473. int nTempSourOffset = strlen(szSource)-1;
  474. //从后向前进行匹配
  475. while(szMatcher[nSubOffset] != '*')
  476. {
  477. if(szMatcher[nSubOffset] == '?')
  478. ;
  479. else
  480. { if(szMatcher[nSubOffset] != szSource[nTempSourOffset])
  481. { bIsMatched = false;
  482. break;
  483. }
  484. }
  485. nSubOffset--;
  486. nTempSourOffset--;
  487. }
  488. break;
  489. }
  490. else//szMatcher[nSubOffset] == '*'
  491. { nSubOffset -= nMatchOffset;
  492. char* szTempFinder = new char[nSubOffset];
  493. nSubOffset--;
  494. memcpy(szTempFinder, szMatcher+nMatchOffset+1, nSubOffset);
  495. szTempFinder[nSubOffset] = 0;
  496. int nPos = FindingString(szSource+nSourOffset, szTempFinder, 0);
  497. delete []szTempFinder;
  498. if(nPos != -1)//在'szSource+nSourOffset'中找到szTempFinder
  499. { nMatchOffset += nSubOffset;
  500. nSourOffset += (nPos+nSubOffset-1);
  501. }
  502. else
  503. { bIsMatched = false;
  504. break;
  505. }
  506. }
  507. }
  508. } //end of "if(szMatcher[nMatchOffset] == '*')"
  509. else if(szMatcher[nMatchOffset] == '?')
  510. {
  511. if(!szSource[nSourOffset])
  512. { bIsMatched = false;
  513. break;
  514. }
  515. if(!szMatcher[nMatchOffset+1] && szSource[nSourOffset+1])
  516. { //如果szMatcher[nMatchOffset]是最后一个字符,
  517. //且szSource[nSourOffset]不是最后一个字符
  518. bIsMatched = false;
  519. break;
  520. }
  521. nMatchOffset++;
  522. nSourOffset++;
  523. }
  524. else//szMatcher[nMatchOffset]为常规字符
  525. {
  526. if(szSource[nSourOffset] != szMatcher[nMatchOffset])
  527. { bIsMatched = false;
  528. break;
  529. }
  530. if(!szMatcher[nMatchOffset+1] && szSource[nSourOffset+1])
  531. { bIsMatched = false;
  532. break;
  533. }
  534. bool b=bIsMatched;
  535. nMatchOffset++;
  536. nSourOffset++;
  537. }
  538. }
  539. delete []szSource;
  540. delete []szMatcher;
  541. return bIsMatched;
  542. }