题解 | 实现字通配符*

import re

# Process input
p = input()
s = input()

# Algo
chips = re.split(r"\*+", p)
# - Special cases
if len(chips) == 2 and chips[0] == '' and chips[1] == '':
    for i in range(len(s)):
        for j in range(i, len(s)):
            print(i, j-i+1)
    exit()
# - Build anchors
lst_anchors = []
nextStart = 0
for i in range(len(chips)):
    chip = chips[i]
    if chip == '':
        if i == 0:
            lst_anchors.append(list(range(0, len(s))))
        else:  # i == len(chips) - 1
            lst_anchors.append(list(range(max(0, nextStart-1), len(s))))
    else:
        anchors = []
        j = nextStart
        while j < len(s):
            try:
                j = s.index(chip, j)
                anchors.append(j)
                j += 1
            except ValueError:
                break
        if not anchors:
            print("-1 0")
            exit()
        nextStart = anchors[0] + len(chip)
        lst_anchors.append(anchors)
# - Implement DFS func
def dfs(i, minAnchor, start, zeroWidthEnd):
    if i == len(lst_anchors):
        nLen = minAnchor-start+zeroWidthEnd
        if nLen > 0:
            print(start, nLen)
        return
    anchors = lst_anchors[i]
    chip = chips[i]
    b_layer0 = i == 0
    zeroWidthEnd = 1 if chip == '' and i > 0 else 0
    for anchor in anchors:
        if anchor < minAnchor and not zeroWidthEnd:
            continue
        dfs(i+1, anchor+len(chip), anchor if b_layer0 else start, zeroWidthEnd)
# - Invoke
dfs(0, 0, 0, 0)