Wildcard Pattern matching selber schreiben

[kdot]

Hallo Leute!

Ich hab mich entschlossen, für ein Projekt eine funktion zu basteln, die einen String auf ein Suchmuster durchsucht, ähnlich Regulären ausdrücken, jedoch sind nur Sterne (*) als Wildcard zugelassen, sollte also wesentlich einfache realisierbar sein, als eine regex-suche.

nun will mir aber beim besten willen kein praktikabler ansatz einfallen...hab schon iterative und rekursive algos durchdacht, aber komme auf keinen grünen zweig...hat jemand eine Idee, wie man eine solche Funktion schreibt, ohne auf standard-libraries zurück zu kommen?

hier mal der Prototyp:
int SearchWithWildcards(char* Searchstring,char* pattern);
wobei Searchstring z.b. "HelloWorld" lautet und pattern: H*W* . dieses Beispiel sollte zum erfolgsfall führen, also eine 1 als return liefern., folgendes eine 0: HalloWel*

Ich danke schonmal für die tatkräftige unterstützung.
kdot

[Joghurt]

Ich vermute mal, dass der Wildcardoperator nicht greedy sein soll, d.h. bei "H*W" trifft * nur auf alle Buchstaben außer "W" zu.
in dem Falle könntest du es so lösen:

int Search(const char* haystack, const char* needle)
{
register int haypos = 0;
register int needlepos = 0;
int in_wildcard = 0; //sind wir im Wildcardmodus?
while (needlepos<strlen(needle) &&
haypos<strlen(haystack)) {
if (needle[needlepos] == '*') {
in_wildcard = 1;
needlepos++;
continue;
}
if (haystack[haypos] != needle[needlepos]) {
haypos++;
if (!in_wildcard) needlepos = 0; //Im Wildcardmodus suchen wir nach nichttreffern
continue;
}
in_wildcard = 0; //Passendes Zeichen gefunden, wildcard in jedem Falle aus
needlepos++;
haypos++;
}
//Wenn wir bis zum Ende des Suchstrings gekommen sind, haben wir einen
//treffer gefunden.
return (needlepos == strlen(needle));
}

[kdot]

Danke für die Antwort! das hilft mir schon sehr. funktioniert auch tadellos! Ich hab auch schon mit einer Statemachine gedankengespielt, aber es hat an der realisierung gehapert.

nun fiel der groschen,

Danke nochmals.

[Joghurt]

Denk nur daran, dass beim Suchmuster "H*We" bei "HalloWaWelt" false zurückgegeben wird, da * beim ersten W aufhört.

[kdot]

Danke, das reicht erstmal aus, aber es wäre schon interessant, zu erfahren, wie es sonst noch geht

[panzi]

Danke, das reicht erstmal aus, aber es wäre schon interessant, zu erfahren, wie es sonst noch geht
Ich hab mal eine sehr simple Regulären-Ausdruck-Engine geschrieben. Das ist ja das selbe nur noch ein wenig komplezierter. Da ich python verwendet hatte und da python das absolut geile yield statement hat gings sau einfach. In C/C++ wirds wohl echt mühsam, ohne dem yield.

Siehe:
http://twoday.tuwien.ac.at/pub/stories/22176/main

[Joghurt]

Wenn du * greedy haben willst, kannst du es so machen

int Search(const char* haystack, const char* needle)
{
register int haypos = 0;
register int needlepos = 0;
int in_wildcard = 0; //sind wir im Wildcardmodus?
while (needlepos<strlen(needle) &&
haypos<strlen(haystack)) {
if (needle[needlepos] == '*') {
in_wildcard = 1;
needlepos++;
continue;
}
if (haystack[haypos] != needle[needlepos]) {
haypos++;
if (!in_wildcard) needlepos = 0; //Im Wildcardmodus suchen wir nach nichttreffern
continue;
}
if (in_wildcard) {
// passt der Rest? (rekursiv aufrufen)
if (Search(haystack+haypos, needle+needlepos)) {
return 1; // Passt
} else {
// passt nicht, versuchen wir, mehr Zeichen zu
// verschlingen
haypos++;
continue;
}
} else {
needlepos++;
haypos++;
}
}
//Wenn wir bis zum Ende des Suchstrings gekommen sind, haben wir einen
//treffer gefunden.
return (needlepos == strlen(needle));
}

// H*We: HalloWaWelt = 1, HalloWelt = 1, HalloWaWalt = 0