WildCard字符串比較（空或全部字符）

Question

我想在C++中編寫一個函數，它可以比較兩個字符串s1和s2，其中只有s2有'？'字符。 '？'字符表示匹配包括空字符在內的任何字符 的能力。例如，colo？r匹配「顏色」和「顏色」。 這個 查詢應報告每一個匹配的單詞。其它實例：

你好：hello__True

你好：H L -O - 真（既充當通配符？）

hllo：？？？？？H L -O - 真（第一充當？空的，第二充當通配符）

HLO：4 H 10 LO - 真（既充當空）

你好：H LO - 假（字符只能更換一個字符，不是字符串）

hello：h？ p - false（p與任何可能的字符選項都匹配）

我嘗試了很多使用循環的函數，但我只能處理所有'？'的問題。或者是空的或者是通配符。當一個人像通配符那樣空虛而其他時，那麼有很多不同的字符串可以比較，以至於事情失去控制。

我的教授告訴說，遞歸是解決這個問題的關鍵，但我們還沒有討論很多關於遞歸的問題。 請幫助我一些建議/代碼，可以使用回溯技術來解決這個問題。

Answer 1

基本上，你去用通配符字符串（我會打電話給該字符串模式從現在起）：

如果該模式的第一個字符是一個字符，但?，然後嘗試使用從輸入字符串（另一個沒有通配符的字符串）中恰好是該字符。

如果該模式的第一個字符是?，那麼有兩種情況：

1. 的?應該匹配一個字符（爲了匹配完整的圖案），所以只消耗從下一個字符輸入並繼續。
2. ?不應與一個字符匹配，在這種情況下，您將繼續處理該模式中的下一個字符，並保持輸入字符串不變。

當然，你無法知道這些情況之前選擇何時。所以你需要能夠回到那一點，以防你的猜測出錯。

對於這一點，你可以使用遞歸（或者更確切地說：在新的背景下，局部變量和這樣的條件，你從一個遞歸調用得到）：

你只是第一次調用您的匹配功能剩餘模式和輸入字符串，如果失敗，則使用其餘模式和輸入字符串而不是的第一個字符（從而使?使用字符）調用匹配函數。

實施例：

pattern: s?y 
input: say 

圖案的第一個字符是s，這是正常的非通配符匹配，因此在看輸入此匹配的第一個字符，在移動兩個：

pattern: ?y 
input: ay 

現在有一個匹配的通配符，所以假裝它沒有消耗任何字符，讓我們看看我們的位置。調用與匹配功能：

pattern: y 
input: ay 

哎喲，這不符合（a != y），所以在這一點返回false。這讓我們回到我們稱之爲匹配功能（在上面的步驟），留給我們：

pattern: ?y 
input: ay 

我們已經嘗試通配符匹配，因爲沒有文字，現在嘗試匹配它的任何字符，從而消費a：

pattern: y 
input: y 

哇，火柴，兩個字符串就下運行空的，所以我們有一個比賽！

---

這似乎是家庭作業，你可能必須在C++中實現。我不會給你那個代碼。相反，我會給你一個不同語言的實現 - Clojure - 它應該讓你進一步理解上述算法。

(ns wildcards 
    (:refer-clojure)) 

(defn- dpr 
    "Debug printing with poor man's indendation" 
    [pattern & rest] 
    (print (repeat (- 6 (count pattern)) " ")) 
    (apply println rest)) 

(defn wildcard-match [input pattern] 
    (println "wildcard-match " input pattern) 
    (if (or (empty? input) (empty? pattern)) 
    ;; One is empty, return true if both are 
    (and (empty? input) (empty? pattern)) 
    ;; Else 
    (if (= (first pattern) \?) 
     ;; Wildcard, so with short ciruiting or: 
     (or (do 
      (dpr pattern "Try to match no character...") 
      (wildcard-match input (rest pattern))) 
      (do 
      (dpr pattern "Ok, so try to match any character...") 
      (recur (rest input) (rest pattern)))) 
     ;; Non-Wildcard, test for equality, and if equal, go on. 
     (and (= (first pattern) (first input)) 
      (recur (rest input) (rest pattern)))))) 



(defn testcase [input pattern] 
    (println "#####################################") 
    (println "Trying to match" input "with" pattern) 
    (println "=>" (wildcard-match (seq input) (seq pattern))) 
    (println)) 


(doall (map #(testcase (first %) (second %)) 
    [["hello" "hello"] 
    ["hello" "h?l?o"] 
    ["hllo" "h?l?o"] 
    ["hlo" "h??lo"] 
    ["hello" "h?lo"] 
    ["hello" "h???p"]])) 

你可以看到這個正在這裏執行： http://ideone.com/8o4QdR

由於Clojure是遞歸的強大的使用功能性語言，你看到很多遞歸對那裏發生的。將其轉換爲更加緊迫的語言，如C++，應該消除大多數這些遞歸，特別是那些可以被循環替換的遞歸（這些都是recur調用，只留下一個必要的遞歸使用）。