饭中淹的避难所~~~~~

偶尔来避难的地方~

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  94 随笔 :: 0 文章 :: 257 评论 :: 0 Trackbacks
  1 ///@brief 使用空白字符匹配
  2 #define    USE_WHITE_SPACE_MATCH
  3 
  4 /*!
  5 *    @brief 匹配一个字符串模版
  6 *    @param pszText 需要匹配的字符串
  7 *    @param uTextLen 需要匹配的字符串长度
  8 *    @param pszTemplateText 需要匹配的模版字符串
  9 *    @param uTemplateTextLen 需要匹配的模版字符串的长度
 10 *    @param pMatchedLen 返回的完成匹配的字符串长度
 11 *    @return 返回是否匹配成功
 12 *    @retval true on 匹配成功
 13 *    @retval false on 匹配失败
 14 */
 15 bool _MatchTemplate( const wchar_t * pszText, size_t uTextLen, const wchar_t * pszTemplateText, size_t uTemplateTextLen, size_t * pMatchedLen )
 16 {
 17 
 18     size_t uTextPos = 0u, uTemplateTextPos = 0u;
 19     size_t uLastStarPos = ~(size_t)0u;
 20 
 21     //    没有匹配的模版,直接匹配成功
 22     if( uTemplateTextLen == 0 )
 23     {
 24         if( pMatchedLen != NULL )
 25             *pMatchedLen = uTextPos;
 26         return true;
 27     }
 28     whiletrue )
 29     {
 30         wchar_t cTemplate = pszTemplateText[uTemplateTextPos];
 31         switch( cTemplate )
 32         {
 33 #ifdef    USE_WHITE_SPACE_MATCH
 34         case L'.':
 35             {
 36                 if( pszText[uTextPos] != 0x20 &&
 37                     pszText[uTextPos] != 0x3000 )
 38                 {
 39                     if( pMatchedLen != NULL )
 40                         *pMatchedLen = uTextPos;
 41                     return false;
 42                 }
 43                 ++uTemplateTextPos;
 44                 ++uTextPos;
 45             }
 46             break;
 47 #endif
 48         case L'?':
 49             {
 50                 ++uTemplateTextPos;
 51                 ++uTextPos;
 52             }
 53             break;
 54         case L'*':
 55             {
 56                 if( uTemplateTextPos >= uTemplateTextLen-1 )
 57                 {
 58                     //    结尾的*,直接认为是匹配所有字符(包括空)
 59                     if( pMatchedLen != NULL )
 60                         *pMatchedLen = uTextLen;
 61                     return true;
 62                 }
 63 
 64                 wchar_t cNextTemplate = pszTemplateText[uTemplateTextPos+1];
 65                 //    跳过重复的*
 66                 if( cNextTemplate == '*' )
 67                 {
 68                     ++uTemplateTextPos;
 69                     break;
 70                 }
 71                 //    记录最后一个*的出现位置
 72                 if( uLastStarPos != uTemplateTextPos )
 73                     uLastStarPos = uTemplateTextPos;
 74                 //    检查下一个模版字符是否匹配
 75 
 76                 //    ?匹配直接跳过
 77                 if( cNextTemplate == '?' )
 78                 {
 79                     uTemplateTextPos+= 2;
 80                 }
 81 #ifdef    USE_WHITE_SPACE_MATCH
 82                 //    空格匹配
 83                 else if( cNextTemplate == '.' )
 84                 {
 85                     if( pszText[uTextPos] == 0x20 ||
 86                         pszText[uTextPos] == 0x3000 )
 87                     {
 88                         uTemplateTextPos+=2;
 89                     }
 90                 }
 91 #endif
 92                 //    字符匹配
 93                 else if( cNextTemplate == pszText[uTextPos] )
 94                 {
 95                     uTemplateTextPos+=2;
 96                 }
 97                 //    下一个字符
 98                 ++uTextPos;
 99             }
100             break;
101         default:
102             if( cTemplate != pszText[uTextPos] )
103             {
104                 //    如果遇到过*就回退到最后一个*
105                 if( uLastStarPos < uTemplateTextLen )
106                 {
107                     uTemplateTextPos = uLastStarPos;
108                     cTemplate = pszTemplateText[uTemplateTextPos];
109                     ++uTextPos;
110                     break;
111                 }
112                 if( pMatchedLen != NULL )
113                     *pMatchedLen = uTextPos;
114                 return false;
115 
116             }
117             ++uTextPos;
118             ++uTemplateTextPos;
119             break;
120         }
121         //    成功匹配完城所有的
122         if( uTemplateTextPos >= uTemplateTextLen )
123         {
124             break;
125         }
126         //    没有成功匹配完整个模版,文字就没有了
127         if( uTextPos >= uTextLen )
128         {
129             if( pMatchedLen != NULL )
130                 *pMatchedLen = uTextPos;
131             return false;
132         }
133     }
134     if( pMatchedLen != NULL )
135         *pMatchedLen = uTextPos;
136     return true;
137 }
138 

模版支持三种匹配符号 '*','?','.'
*匹配任意多个任意字符串
?匹配一个字符串
.匹配一个空格
可以通过注释掉宏来禁止匹配空格
达到的效果和文件系统的文件名匹配差不多


关于递归的方法:
VCZH提供了一个递归的解法,并且“寥寥数行,瞬间搞定”。
不过,递归会带来堆栈的问题。
而且他的方法里存在BUG,我就不贴上来了。
据他称那种方法来自一本 beautiful code的书。此书我没看过,所以不清楚。
从他的方法本身看,他只能提供是否匹配的一个结果,并且匹配模版和待匹配的字符串必须是0结尾,并且不返回结束匹配时的匹配进度。
并且在处理*的时候,有些许小BUG。

虽然他一直在坚持自己是在做学术研究,也有不少人匿名来支持他,不过我觉得他还是有些态度问题。
总是喜欢在别人的贴上表现自己。做的太过了就是显摆了。
从他回帖说的那些话,比如“寥寥数行,瞬间搞定”这些,以及并不完善的代码看来,他根本就没有看过我的代码,只是凭字面意思就开始贴代码。
我实在不清楚他说这些话和贴代码的原因是什么。这些我就不再讨论了,我也删除了他的回复。
不过我想说,如果你一直以这种态度来回别人的帖子,那你会成为一个令人讨厌的人。






posted on 2011-04-27 10:21 饭中淹 阅读(2187) 评论(6)  编辑 收藏 引用 所属分类: 数据算法分析

评论

# re: 【简单的字符串模版匹配】 2011-04-28 15:22 dfdf
支持下!  回复  更多评论
  

# re: 【简单的字符串模版匹配】 2011-04-29 16:26 卧槽
嗯,菜鸟一般都有你这样的自卑心理.  回复  更多评论
  

# re: 【简单的字符串模版匹配】 2011-04-29 17:10 饭中淹
@卧槽
是的,我确实是个菜鸟。
  回复  更多评论
  

# re: 【简单的字符串模版匹配】 2011-04-29 19:51 Kevin Lynx
@饭中淹
不要跟连名字都不敢留的人一般见识。  回复  更多评论
  

# re: 【简单的字符串模版匹配】 2011-07-27 22:21 请输入你的姓名
1. 有没有非UNICODE版本,毕竟多字节比较麻烦
2. 个人感觉没必要删除别人的评论吧,寥寥几行的代码至少也让别人能看到,言论自由吗!!!好坏就由他人评价不行吗??  回复  更多评论
  

# re: 【简单的字符串模版匹配】[未登录] 2011-08-05 14:04 VK
//和文件名匹配相似,只支持*和?,无递归
#define FIX_SIZE 1024
bool _match_fix_size(const wchar_t* src, int srcLen, const wchar_t* rule, int ruleLen)
{
// 声明扫描线并确定新长度
bool old_scan[FIX_SIZE + 1];
bool new_scan[FIX_SIZE + 1];
const int rule_max = ruleLen + 1;
const int src_max = srcLen + 1;

//长度不能超过FIX_SIZE
if (rule_max >= FIX_SIZE || src_max >= FIX_SIZE)
return false;

// 复制平移一个位置
wchar_t src_copy[FIX_SIZE + 1];
wchar_t rule_copy[FIX_SIZE + 1];
memcpy(&src_copy[1], src, (srcLen + 1) * sizeof(wchar_t));
memcpy(&rule_copy[1], rule, (ruleLen + 1) * sizeof(wchar_t));

//初始化扫描线
for(int i = 0; i < src_max + 1; ++i)
{
new_scan[i] = false;
old_scan[i] = false;
}

// 初始化启动标记(new_scan无启动标记)
src_copy[0] = 0;
rule_copy[0] = 0;
old_scan[0] = true; // old_scan 以true开始


//1才是开始
for(int i = 1; i < rule_max + 1; ++i)
{
for(int j = 1; j < src_max + 1; ++j)
{
new_scan[j] = false;
if(rule_copy[i - 1] == src_copy[j - 1] && old_scan[j - 1])
new_scan[j] = true;
if(rule_copy[i - 1] == L'?' && old_scan[j - 1])
new_scan[j] = true;

if(rule_copy[i - 1] == L'*')
{
if(new_scan[j - 1])
new_scan[j] = true;
if(old_scan[j])
new_scan[j] = true;
}
}
for(int j = 0; j < src_max + 1; ++j)
old_scan[j] = new_scan[j];
}
return new_scan[src_max];
}

  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理