3 ms·
That 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 q
by JdeBP 10y ago
That 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 10y 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 10y agoYes it does.
- E6300 10y 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.