元字符*字符匹配问题--转

t中含有*，s中没有，t和s是否匹配的问题.

(1)当*t不是*的时候, 就像普通的串匹配一样, 移动s和t
(2)当*t是*的时候,  假设*t后面第一个不是*的字符是x,  若x是null, 直接匹配成功, 
否则在s中找到当前位置后所有字符x的位置, 这时候问题转化成了t中x后的串和s中当前位置以后所有以x为开始的串的匹配问题,递归调用即可, 其中任意一个匹配成功, 则原串匹配成功, 若都没有匹配成功则匹配失败.

//当*s和*t其中一个是null时 跳出循环, 若此时 *t  == '*', 则++t 直到 t != '*',  这时若 *t == 0 则代表匹配成功, 否则匹配失败

#include
#include
#include

using namespace std;

bool is_match(const char * s, const char * t)
{
 while (*s && *t)
 {
  if (*t != '*' && *s == *t) //普通匹配
    ++s, ++t;
  else if (*t != '*' && *s != *t)
    return false;
  else if (*t == '*')
  {
   do ++t; while (*t == '*'); //找到t中*以后的字符
   if (*t == 0) return true; //*以后没有字符，匹配成功
   for (; *s; ++s) //在s中找到以字符*t为开头的所有的字符串
   {
    if (*s == *t && is_match(s+1, t+1)) //比较两个子串
     return true;
   }
   return false;
  }
 }
 while (*t == '*') ++t;
 if (*s == *t) return true;
 else return false;
}

int main(int argc, char * argv[])
{
 string str1 ,str2;
 str1 = "hello", str2 = "he*lo";
 if (is_match(str1.c_str(), str2.c_str()))
  cout << "match" << endl;
 else cout << "not match" << endl;
 getchar();
 return 0;
}