FireEmissary

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  14 随笔 :: 0 文章 :: 20 评论 :: 0 Trackbacks
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input 
string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch(
"aa","a") → false
isMatch(
"aa","aa") → true
isMatch(
"aaa","aa") → false
isMatch(
"aa""*") → true
isMatch(
"aa""a*") → true
isMatch(
"ab""?*") → true
isMatch(
"aab""c*a*b") → false
贪心算法就是遇到*开始记录位置并不断尝试匹配,开始*匹配0字符失败后*匹配1字符再试,匹配到下一个*就终止了又开始记录位置后尝试匹配...
bool isMatch(string s, string p) {
        
return isMatchB(s.c_str(),p.c_str());
    }
    
 
bool isMatchB(const char *s, const char *p) {
           
const char* star=nullptr;  
            
const char* ss=nullptr;   
            
while (*s){  
                
if ((*p=='?')||(*p==*s)){++s;++p;continue;}  
                
if (*p=='*'){star=++p; ss=s;continue;}  
                
if (star){ p = star; s=++ss;}  
                
else return false;  
            }  
            
while (*p=='*'){++p;}  
            
return !*p;  

    }
递归版本却是碰到*后从0开始递增s然后调用自己直到成功或s到了尾部:  
             while(*p=='*')++p;             do              {                   if(isMatchC(s, p))                 {  return true;                 }               
            }  
while(*++s);             return isMatchC(s, p); 
算法很易懂;但没找到证明感觉如芒在背.想了很久没发现怎么证明贪心法是"最优"的办法.
但后来想想证明最优干嘛?其实只要证明比递归版本效率并和它一样正确就行了....
证明如下:
base
1.模式p里没有*,平凡的匹配,递归版本和贪心版本一样效率.
2.模式p里一个*,递归版递归后的匹配和贪心版本(毕竟贪心版本不会碰到*了)算法一样.
3.模式p有两个*
   p: same*abc*xxxxxx. (x代表任意字符和?)
  s: same....abcxxxxxxx (.代表任意不含abc的字符x代表任意字符)
贪心版本匹配到第二个*后s剩下abc后面部分,第二个*可以任意扩展使得后段的x匹配为止
递归版本碰到第一个*后递归求abc*xxxxxxx与....abcxxxxxxx匹配
看起来和贪心版本一样效率,不效率的地方就在于:匹配失败后贪心版本就失败了而递归版本屁颠颠的又挪动s到下一个试图匹配,
递归版本不会成功的,因为第二个*失败就说明了后段的xxxxx之间子串不匹配

现在假设模式p有k个*且贪心版本更效率且一样正确.
4.p有k+1个*.
   p: xxxx*abc*...... (.代表任意字符和*)
   s: xxxx....abcdef..... (.代表任意不含abc的字符)
在第二个*之前使用贪心算法,匹配完毕碰到第二个*转调用递归版本的话,开头匹配情况落入base 1和base 2.递归版本则处理:
p: *.....
s: def.....
即落入假设模式里k个*里换用贪心版本更优秀且正确的情况里了

这样的话就归纳证明了贪心版本在正确匹配时不比递归版本差;在失败时比递归版本效率.


  
 


posted on 2016-03-17 12:48 FireEmissary 阅读(1230) 评论(0)  编辑 收藏 引用

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