String matching where one string contains wildcard characters

Columbo

Ist das hier korrekt? Macht mal jemand ein wenig stress testing?

template <typename BidirectionalIterator, typename InputIterator>
bool match_iter( BidirectionalIterator pat_first, BidirectionalIterator pat_last,
                 InputIterator match_first, InputIterator match_last )
{
	using namespace std;
	// Ein paar triviale Fälle:
	if (pat_first == pat_last)
		return match_first == match_last;
	if (match_first == match_last)
		return find_if(pat_first, pat_last, [] (char c) {return c != '*';}) == pat_last;

	auto pattern_slice = make_pair(pat_first, find(pat_first, pat_last, '*'));

	auto find_match = [&]
	{
		return search( match_first, match_last, pattern_slice.first, pattern_slice.second,
		               [] (char lhs, char rhs) {return lhs == '?' || rhs == '?' ?: lhs == rhs;} );
	};

	auto slice_pos = find_match();
	if (slice_pos != match_first)
		return false;

	while(pattern_slice.second != pat_last)
	{
		match_first = match_first + (pattern_slice.second - pattern_slice.first);
		if (match_first == match_last)
			break;

		pattern_slice = {pattern_slice.second+1, find(pattern_slice.second+1, pat_last, '*')};

		slice_pos = find_match();
		if (slice_pos == match_last)
			return false;
	};

	return *std::prev(pat_last) == '*' || slice_pos == match_last - (pattern_slice.second - pattern_slice.first);
}

bool match( char const* str1, char const* str2 )
{
	return match_iter(str1, str1 + std::strlen(str1), str2, str2 + std::strlen(str2));
}

assert(match("", "a"));
  assert(match("ac", "aab"));

Warum triviale Fälle separat behandeln? Das macht den Code nur komplizierter und langsamer.

Columbo

O(n) schrieb:

assert(match("", "a"));
  assert(match("ac", "aab"));

Schlägt beides wie erwartet fehl.

Warum triviale Fälle separat behandeln?

Was meinst du?

Arcoth schrieb:

O(n) schrieb:
assert(match("", "a"));
  assert(match("ac", "aab"));
Schlägt beides wie erwartet fehl.

Sorry, sollte assert(match("ab", "aab")); heissen. Keines sollte fehlschlagen. Der Leerstring ist in jedem string enthalten.

volkard

O(n) schrieb:

Arcoth schrieb:
O(n) schrieb:
assert(match("", "a"));
  assert(match("ac", "aab"));
Schlägt beides wie erwartet fehl.
Sorry, sollte assert(match("ab", "aab")); heissen. Keines sollte fehlschlagen. Der Leerstring ist in jedem string enthalten.

match interpretiere ich hier abe rnicht als enthaltensein, sondern als von vorn bis hinten draufpassen.
enthaltensein kannste dann mit

assert(match("**", "a"));
assert(match("*ab*", "aab"));

testen.

@volkard: wie ist folgende wildcard zu verstehen: **

volkard

Algoman1 schrieb:

@volkard: wie ist folgende wildcard zu verstehen: **

Wenn ich schauen will, ob maske1 irgendwo in string1 enthalten ist, egal wo, dann kann ich ganz stur schauen, ob ""+maske1+"" und string1 matchen.

So entstand aus der Maske "" die Maske "**".

wie ist folgende wildcard generell zu verstehen: **

Columbo

volkard schrieb:

match interpretiere ich hier abe rnicht als enthaltensein, sondern als von vorn bis hinten draufpassen.
enthaltensein kannste dann mit
assert(match("**", "a"));
assert(match("*ab*", "aab"));
testen.

Danke, genauso habe ich es mir gedacht.

Algoman1 schrieb:

wie ist folgende wildcard generell zu verstehen: **

Es ist äquivalent zu *.

Ich hab mir da nochmal ein bisschen Gedanken gemacht. Eine Menge Aufwand scheint zu entfallen, wenn man die Wildcard-Ausdrücke vorher in eine leichter zu verarbeitende Form bringt -- alle Sequenzen von * und ? am Stück lassen sich ja zusammendampfen; zum Beispiel ist ????* äquivalent zu ????*. Wenn man einen Wildcard-Ausdruck auf diese Weise "normalisiert" hat und sich darauf verlassen kann, dass nach einem * ein Buchstabe oder das Ende kommt, flutscht die Behandlung gleich deutlich besser. Ich denke mir das etwa so:

#include <cassert>
#include <cstring>
#include <iostream>
#include <string>

std::string normalize_wildcard(std::string const &wildcard) {
  std::string result;
  bool pending_star = false;

  for(char c : wildcard) {
    switch(c) {
    case '?':
      result += '?';
      break;
    case '*':
      pending_star = true;
      break;
    default:
      if(pending_star) {
        result += '*';
        pending_star = false;
      }
      result += c;
    }
  }

  if(pending_star) {
    result += '*';
  }

  return result;
}

namespace impl {
  bool compare_aux(char const *glob, std::string const &str, std::size_t pos_str) {
    if(*glob == '*') {
      ++glob;
      // Erwarte normalisierten Wildcard-Ausdruck
      assert(*glob != '*' && *glob != '?');

      if(*glob == '\0') {
        return true;
      }

      char const *pattern_begin  = glob;
      std::size_t pattern_length = std::strcspn(glob, "*?");

      // Von hinten suchen für mehr average-case-Performanz.
      std::size_t pos_search     = std::string::npos;

      do {
        std::size_t pos_pattern = str.rfind(pattern_begin, pos_search, pattern_length);

        if(pos_pattern == std::string::npos || pos_pattern < pos_str) {
          return false;
        }

        if(compare_aux(glob + pattern_length, str, pos_pattern + pattern_length)) {
          return true;
        }

        pos_search = pos_pattern;
      } while(pos_search > pos_str);

      return false;
    } else if(*glob == '?') {
      return pos_str < str.size() && compare_aux(glob + 1, str, pos_str + 1);
    } else if(str.c_str()[pos_str] != *glob) {
      return false;
    } else if(pos_str < str.size()) {
      return compare_aux(glob + 1, str, pos_str + 1);
    }

    return true;
  }
}

bool compare(std::string const &wildcard, std::string const &filename) {
  return impl::compare_aux(normalize_wildcard(wildcard).c_str(), filename, 0);
}

int main() {
  assert(compare("g*ks", "geeks")); // Yes
  assert(compare("ge?ks*", "geeksforgeeks")); // Yes
  assert(!compare("g*k", "gee"));  // No because 'k' is not in second
  assert(!compare("*pqrs", "pqrst")); // No because 't' is not in first
  assert(compare("abc*bcd", "abcdhghgbcd")); // Yes
  assert(!compare("abc*c?d", "abcd")); // No because second must have 2 instances of 'c'
  assert(compare("*c*d", "abcd")); // Yes
  assert(compare("*?c*d", "abcd")); // Yes
}

Für Performance verlasse ich mich dann darauf, dass std::string::rfind vernünftig implementiert ist. Geprüft habe ich das nicht, aber wenn man deswegen in Performanceprobleme läuft, gibt es drölf Milliarden Bibliotheken, die man da draufwerfen könnte. Politur bleibt dem interessierten Leser als Übungsaufgabe überlassen.

Auf Dateinamen könnte man das in der Form wahrscheinlich schon loslassen. Es lassen sich immer noch Fälle konstruieren, die ewig dauern (f*o*o*b*a*r*b*a*z*q*u*x* mit passenden Eingabedaten), aber das ist letztlich ein Problem, das man nicht vollständig los wird. Man könnte hier noch Dinge tun, aber langsam ist der Punkt erreicht, an dem ich dazu rate, bestehende Lösungen zu verwenden, anstatt eigene Dinge zusammenzuhacken. Die laufen dann meistens darauf hinaus, die Pattern vorher aufwändig in eine Form zu bringen, die hinterher Matching in bis zu linearer Zeit erlaubt (Backrefs sind ja hier nicht notwendig). Ich lass mal einen Link hier.

Mir fällt grad auf, dass ich mich da bei einigen Dingen verdacht habe (zu sehr an Regexes gedacht). Es ist ja bei diesem speziellen Subset egal, welchen Substring ein bestimmter Ausdruck matcht, und dann kann man sich die ganze Backtrackerei auch sparen. Asche, Haupt und so.

volkard