Сравнить строку WildCard (пустой или весь символ)

По сути, вы перебираете строку с подстановочными знаками (с этого момента я буду называть эту строку pattern):

Если первый символ шаблона является символом, но не ?, то попробуйте использовать именно этот символ из входной строки (другая строка без подстановочных знаков).

Если первым символом шаблона является ?, то у вас есть два случая:

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 вызовов, оставив только одно необходимое использование рекурсии).