题解 | 实现字通配符*

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var pStr, sStr string
var endPositions map[int]bool

// dfs: 从 sIdx 和 pIdx 开始尝试匹配
func dfs(sIdx, pIdx int) {
	if pIdx == len(pStr) {
		endPositions[sIdx] = true
		return
	}
	if sIdx == len(sStr) {
		return
	}

	if pStr[pIdx] == sStr[sIdx] {
		dfs(sIdx+1, pIdx+1)
	} else if pStr[pIdx] == '*' {
		// 三种情况：
		// 1. '*' 匹配空（跳过 '*'）
		dfs(sIdx, pIdx+1)
		// 2. '*' 匹配当前字符，并继续用 '*' 匹配后续
		dfs(sIdx+1, pIdx)
		// 3. '*' 仅匹配当前字符
		dfs(sIdx+1, pIdx+1)
	}
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	pStr = scanner.Text()
	scanner.Scan()
	sStr = scanner.Text()

	foundMatch := false

	// 存储结果：起始位置 → 长度列表
	type Result struct {
		Start, Length int
	}
	var results []Result

	for i := 0; i < len(sStr); i++ {
		// 只有首字符匹配，或模式首字符是 '*' 才尝试匹配
		if pStr[0] == '*' ||
			pStr[0] == sStr[i] {

			endPositions = make(map[int]bool) // 清空上次结果
			dfs(i, 0)

			if len(endPositions) > 0 {
				foundMatch = true
				// 收集所有有效的匹配（长度 > 0）
				for endPos := range endPositions {
					if endPos > i {
						results = append(results, Result{Start: i, Length: endPos - i})
					}
				}
			}
		}
	}

	// 去重并排序：按起始位置，再按长度
	uniqueResults := make(map[string]bool)
	var finalResults []Result
	for _, r := range results {
		key := strconv.Itoa(r.Start) + "," + strconv.Itoa(r.Length)
		if !uniqueResults[key] {
			uniqueResults[key] = true
			finalResults = append(finalResults, r)
		}
	}

	// 排序输出
	sort.Slice(finalResults, func(i, j int) bool {
		if finalResults[i].Start == finalResults[j].Start {
			return finalResults[i].Length < finalResults[j].Length
		}
		return finalResults[i].Start < finalResults[j].Start
	})

	// 输出结果
	if foundMatch && len(finalResults) > 0 {
		for _, r := range finalResults {
			fmt.Printf("%d %d\n", r.Start, r.Length)
		}
	} else {
		fmt.Println("-1 0")
	}
}