--- a/dynprog.cc	Sat Mar 18 22:51:52 2023 +0100
+++ b/dynprog.cc	Sun Mar 19 18:13:55 2023 +0100
@@ -266,6 +266,43 @@
     fmt::print("memoize count = {}\n", memo.size());
 }
 
+bool wildcard_matches(string::const_iterator pbegin, string::const_iterator pend, string::const_iterator sbegin, string::const_iterator send) {
+    // Pattern finished but string not finished.
+    if (pbegin == pend && sbegin < send) {
+        return false;
+    }
+    // String ended and pattern not definitely ended.
+    if (sbegin == send) {
+        return pbegin == pend;
+    }
+    if (*pbegin == *sbegin || *pbegin == '?') {
+        return wildcard_matches(pbegin+1, pend, sbegin+1, send);
+    }
+    if (*pbegin == '*') {
+        // Keep or consume wildcard.
+        return wildcard_matches(pbegin, pend, sbegin+1, send) || wildcard_matches(pbegin+1, pend, sbegin+1, send);
+    }
+    return false;
+}
+
+bool wildcard_matches(const string& pattern, const string& str) {
+    return wildcard_matches(pattern.begin(), pattern.end(), str.begin(), str.end());
+}
+
+void eval_wildcard_matches() {
+    vector<pair<string,string>> tests{
+        {"xyxzzxy", "x***y"},
+        {"xyxzzxy", "x***x"},
+        {"xyxzzxy", "x***x?"},
+        {"xyxzzxy", "*"},
+    };
+
+    for (const auto& p : tests) {
+        benchmarkit_f([&]() { wildcard_matches(p.second, p.first); }, "wildcard_matches");
+        fmt::print("{} matches {} ? => {}\n", p.first, p.second, wildcard_matches(p.second, p.first));
+    }
+}
+
 int lcss_main(void) {
 
     vector<int> a{1, 6, 2, -1, 3, 55, 2, 4, 23, 5, 6, 7, 8, 9, 10};
@@ -285,9 +322,6 @@
 }
 
 int main(void) {
-    vector<int> a{-1, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
-    // Expect: 0,2,6,9,13 or ,11
-    // or 0,4,6,9,13
-    evaluate_keypad(10);
+    eval_wildcard_matches();
     return 0;
 }

--- a/lib/exec.h	Sat Mar 18 22:51:52 2023 +0100
+++ b/lib/exec.h	Sun Mar 19 18:13:55 2023 +0100
@@ -27,3 +27,31 @@
     fmt::print("{} :: {} s\n", name, static_cast<double>(p.num)/p.den * count); 
     return result;
 }
+
+template<typename F>
+void benchmarkit_f(F f, const string& name, function<void()> setup = []() {}) {
+    int n = 1;
+    const double min_duration = 0.1;
+
+    while (true) {
+        setup();
+     
+        fmt::print("Running {} for {} iterations\n", name, n);
+
+        auto begin = high_resolution_clock::now();
+
+        for (unsigned int i = 0; i < n; i += 1)
+            f();
+
+        auto end = high_resolution_clock::now();
+        decltype(end-begin)::period p;
+        auto seconds = (end-begin).count() * static_cast<double>(p.num)/p.den;
+        if (seconds < min_duration) {
+            n *= 2;
+        } else {
+            fmt::print("{} iterations took {} seconds ({} s/iter)\n", n, seconds, seconds/n);
+            break;
+        }
+    }
+}
+