最大的疑惑在于不使用递归, 而又有多个*号出现时的回溯重试问题。
看起来如果第二次遇到*号时覆盖上次遇到*号时记录的重试位置,但是实际上第二个星号之前的匹配已经可以保证成功了,并且更重要的是这时上个星号匹配了多少字符已经无关了, 第二个星号可以吃掉多出来的字符。
比如下面这个例子
aababaababab
a*ab*ab
pattern中第一个*ab是匹配的哪个ab并不重要(只要不是最后一个就行,一般匹配第一个遇见的就好了),因为第二个*会吃掉多余的ab, 并且保证pattern中最后一个ab能够“够”到字符串的结尾。