题解 | 实现字通配符* | Python3 通过普通字符串找锚点 （556ms）

import re

p, s = input(), input()

# Algo
m, n = len(p), len(s)
# - Locate anchors
chips = re.split(r"\*+", p)
list_anchors = []
if chips[0] == '': list_anchors.append(list(range(n)))
for chip in chips:
    if chip:
        anchors = []
        i = 0
        while True:
            try:
                i = s.index(chip, i)
                anchors.append(i)
                i += 1
            except:
                break
        if anchors:
            list_anchors.append(anchors)
        else:
            print("-1 0")
            exit()
if chips[-1] == '': list_anchors.append(list(range(1, n+1)))
# - DFS
def dfs(i, prev, stack, res):
    if i == len(list_anchors):
        ss, ee = stack[0], stack[-1]
        cur_len = ee-ss+len(chips[-1])
        if cur_len > 0: res.append((ss, cur_len))
        return
    anchors = list_anchors[i]
    for anchor in reversed(anchors):
        if anchor < prev: break
        stack.append(anchor)
        dfs(i+1, anchor, stack, res)
        stack.pop()

res = []
dfs(0, -1, [], res)
res.sort()
for row in res: print(*row)