4 ms·
HN screwed up my comment. It's not supposed to be "question mark, a, question mark, a, ...". I meant to write "question mark, a, star, question mark, a, star, .
by E6300 9y ago
HN screwed up my comment. It's not supposed to be "question mark, a, question mark, a, ...". I meant to write "question mark, a, star, question mark, a, star, ...".
- JdeBP 9y agoThat would be backtracking caused by those stars, not by the question marks. Hacker News didn't screw up the part where you wrote "wouldn't be able to handle question marks".
- E6300 9y agoA 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.
- E6300 9y agoI made a type in my previous response. I wrote "can be handled" instead of "can't be handled". The algorithm described can't handle that case.