Search routine loops through characters of wildcard string.
1) search string position 1: "*" -> wildcard symbol for any char so move on to next
2) search string position 2: "×" -> loop through text string from position 1 till character "×" found, store the position of the character after this character (pointer).
3) search string position 3: "*" -> wildcard symbol for any char so move on to next
4) search string position 4: "×" -> loop through text from previous position onwards till character "×" found, update the pointer to the position after this character.
Seach result 'false' (discarding moment) happens when the current no-wildcard symbol * being character is not found in the text string on the position of the pointer.
The key idea you're missing here is backtracking; when a particular way of matching each * with a substring fails, a different combination is tried, and the number of such combinations is exponential to the number of *'s.
The first takes 5436 ms, the second 2 ms.
The only difference is that in the first alias, the last token is NOT matched, while it is matched in the second alias, the fast (or should I say 'normal'?) one - which is also remarkable, because you only know if there is a match after checking ALL characters, while a check for a non-match may be able to discard at an earlier position, so less characters compared.
Doesn't that blow up the entire theory of alot wildcard symbols as reason?
Not at all, the problem mostly occurs when the pattern does
not match the string in
any way, so that the routine has to try all possible "assignments" of *'s.
You should probably Google these issues, as I suspect there's not much I could say to convince you. The problem is central to regular expressions implementations too (
pcre.txt, section "ATOMIC GROUPING AND POSSESSIVE QUANTIFIERS" describes a similar case). An analogous situation in regex is this:
//echo -ag $regex($str(a,39),/^.*.*.*.*.*.*\d$/)
\d matches a digit (0 to 9), so this pattern will never match a string of a's. Even a single call to the above takes a noticeably long time to complete. Removing a ".*" makes it much faster; adding a ".*" makes it return -8, which is the error code meaning "too many attempts to match". Regular expressions in mirc are supported through a 3rd-party library, PCRE (my point being, different author). PCRE contains an optimisation, ie if you change \d to a literal, say b, $regex fails very quickly. This is the sort of 'early termination' checks I mentioned in my previous post. Khaled could do something like that in his wildcard matching routine, but of course that would only cover a subset of problem cases.
In my opinion, it is the user who should come up with a 'better' pattern (or an entirely different method altogether), not the programmer who should come up with a better algorithm.
