4 ms·
A pattern like "star a star a star a star" can be handled by the algorithm described in the article: > Consider the pattern "a star bx star cy star d". If we e
by E6300 9y ago
A pattern like "star a star a star a star" can be handled by the algorithm described in the article:
> Consider the pattern "a star bx star cy star d". If we end the first star at the first bx, we have the rest of the name to find the cy and then the d. Using any later bx can only remove choices for cy and d; it cannot lead to a successful match that using the first bx missed. So we should implement a star bx star cy star d without any second-guessing, as “find a leading a, then find the earliest bx after that, then find the earliest cy after that, then find a trailing d, or else give up.”
This algorithm doesn't work if the pattern has question marks.
- rsc 9y agoYes it does.