NO IMAGE

今天看到這樣一個題,實現字串的模式匹配,具體題目如下:

請實現一個函式來匹配包括’.’和’*’的正規表示式,其中匹配是指字串的所有字元匹配整個模式串。具體匹配規則如下:模式串中的字元’.’表示任意一個字元,而’*’表示它前面的字元可以出現任意次(包含0次。例如,字串”aaa”與模式”a.a”和”ab*ac*a”匹配,但是與”aa.a”和”ab*a”均不匹配。

經過簡單的分析,我們可以很容易想到利用遞迴求解,先匹配字串中的當前字元,如果匹配成功,則遞迴匹配下一個字元,否則返回 false。下面看看字串匹配的具體過程:

為了方便說明,str 表示字串,pattern 表示模式串

   bool match_core (char *str, char *pattern);

1、首先考慮遞迴出口:

      當 *str == ‘\0’ && *pattern == ‘\0’ 時,即 str 和 pattern 都是空串時,我們說它們是匹配的,返回 true;

      當 *str != ‘\0’ && *pattern == ‘\0’,str 無法完成匹配,返回 false.

      【注意】當 *str ==’\0′ && *pattern != ‘\0’ 時,是有可能匹配成功的,比如:pattern 為 a*,而 str 為空串時,是可以匹配成功的。因為 ‘*’ 前面的字元 a 可以出現0次。

2、我們可以將匹配過程分為兩類:一類是*(pattern 1) != ‘*’;另一類是*(pattern 1) == ‘*’,下面基於這兩種情況討論該問題的具體實現:

      *(pattern 1) != ‘*’ 時,只要 *str 與 *pattern 匹配,兩個字串分別向前移動一步。即:

             若  *str == *pattern, 則 match_core (str 1, pattern 1);

             若   *str != ‘\0’ && *pattern == ‘.’,則 match_core (str 1, pattern 1);

             若 *str 和 *pattern 不滿足上述兩個條件,說明 *str 和 *pattern 不匹配,直接返回 false。

     *(pattern 1) == ‘*’ ,根據 *pattern 與 *str 匹配的個數,可以分為下面幾種情況:

             若匹配個數為0,即 *pattern 與 *str 不匹配,則match_core (str, patten 2);

            若匹配個數為 1 個或多個,我們只需要每次將 str 向前移一步,pattern 保持原來的位置,繼續做下一輪匹配,即match_core (str 1, pattern)。

我們考慮這種情況:str = “aaaaa”, pattern = “aa*a”,按照題目敘述的匹配原則,str 與 pattern 應該是匹配的,但是按照我們剛才分析的思路走下來,match_core返回的是false,分析明顯是由漏洞的,我們再來看看*(pattern 1) == ‘*’中匹配個數是多個的情況,我們不僅要考慮 str 1 與 pattern 的匹配, 還要考慮到 str 與 pattern 2 的匹配情況,只要這兩種情況中的任何一種匹配成功, str 和 pattern 都算是匹配成功。

基於上述分析,給出 C 程式碼如下:

//正規表示式匹配核心部分
bool match_core (char *str, char *pattern)
{
//*pattern == '\0'的兩種情況已經分析完,下面的情況肯定是*pattern != '\0'
if (*str == '\0' && *pattern == '\0')
{
return true;
}
if (*str != '\0' && *pattern == '\0')
{
return false;
}
//下面來分析pattern沒有走完的情況
//分為兩種情況:一個是模式串的下一個字元為*;另一種是模式串的下啊一個字元不為*
if (*(pattern   1) != '*')   
{
if (*str == *pattern || (*str != '\0' && *pattern == '.'))
{
return match_core(str   1, pattern   1);
}
else
{
return false;
}
}
else
{
if (*str == *pattern || (*str != '\0' && *pattern == '.'))
{
return match_core (str, pattern   2) || match_core (str   1, pattern);
}
else
{
return match_core (str, pattern   2);
}
}
}
bool match (char *str, char *pattern)
{
if (str == NULL && pattern == NULL)
{
return true;
}
if (str == NULL || pattern == NULL)
{
return false;
}
return match_core (str, pattern);
}