Two Way算法是一种子字符串搜索算法(primary paper, 1.4 MB PDF)。
它将搜索模式x分成两部分:x = xl xr，首先它尝试匹配xr与文本，如果成功，算法规定匹配xl反向(即从右到左的顺序)。
- 为什么xl从右到左匹配?
- 我可以用从左到右的比较来代替它吗?
这个问题的原因很简单:一个顺序未指定的比较已经可用，并且可能更性能，想想像优化的memcmp或展开的循环。
从效率的角度来看，这显然无关紧要。我能想到的唯一另一个原因是:在不匹配的情况下，从右到左的尝试可能会让算法留下更多关于部分匹配的信息。按照RTL，如果我们在xl中匹配两个字符，然后失败，我们知道我们有一个部分的，连续的匹配，2个字符+ xr。如果我们匹配xl LTR而失败，我们只知道xr匹配。