实现字通配符*

#include <bits/stdc++.h>
using namespace std;

string s, t;
set<int> S;

void DFS(int i, int j){
    if(j==t.length())
        S.insert(i);
    if(i==s.length())
        return;
    if(s[i]==t[j])
        DFS(i+1, j+1);
    else if(t[j]=='*'){
        DFS(i, j+1);
        DFS(i+1, j);
        DFS(i+1, j+1);
    }
    return;
}

int main(){
    cin>>t>>s;
    bool flag = false;
    for(int i=0;i<s.length();i++){
        if(s[i]==t[0] || t[0]=='*'){
            DFS(i, 0);
            if(!S.empty()){
                flag = true;
                for(set<int>::iterator it=S.begin();it!=S.end();it++)
                    if(*it>i)
                        cout<<i<<" "<<*it-i<<endl;
            }
            S.clear();
        }
    }
    if(!flag)
        cout<<-1<<" "<<0<<endl;
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int Core(string &str1, string &str2, int left, int right,int start, int len)
{
    int res = false;
    if(str1[left] == '\0')
    {
        cout << start << " " << len << endl; 
        return true;
    }
    if(str1[left] != '\0' && str2[right] == '\0') return false;
    //当通配字符不是*时候，判断两个个字符是否相等
    if(str1[left] != '*')
    {
        if(str1[left] != str2[right]) return false;
        else 
        {
           res = Core(str1, str2, left+1, right+1, start, len+1);
        }
    }
    //当通配字符是*时候，通配字符向后移动或者查找字符向后移动
    else
    {
        //这里要注意不能用||因为一旦第一个条件成立第二个条件不会被执行
        bool tem1 = Core(str1, str2, left+1, right, start, len) ;
        bool tem2 = Core(str1, str2, left, right+1,start, len+1);
        res = tem1||tem2;
            
    }
    return res;
}
int main()
{
    
    string str1;
    string str2;
    cin >> str1 >> str2;
    if(str1 == "*")
    {
        for(int i = 0; i < str2.size();i++)
        {
            for(int j = 1; j + i <= str2.size();j++)
            {
                cout << i << " " << j << endl;
            }
        }
        return 0;
    }
    bool res = false;
    for(int i = 0; i < str2.size();i++) 
    {
        if(Core(str1, str2, 0,i,i,0)) res = true;
    }
    if(!res) cout << -1 << " " << 0 << endl;
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    private static boolean match(String matchStr, String str, int matchIdx, int idx) {
        if (matchIdx == matchStr.length() && idx == str.length()) {
            return true;
        }
        if (idx >= str.length() && matchIdx < matchStr.length() && matchStr.charAt(matchIdx) == '*') {
            return match(matchStr, str, matchIdx + 1, idx);
        }
        if (matchIdx >= matchStr.length() || idx >= str.length()) {
            return false;
        }
        if (matchStr.charAt(matchIdx) != '*' && matchStr.charAt(matchIdx) != str.charAt(idx)) {
            return false;
        }
        boolean flag = false;
        if (matchStr.charAt(matchIdx) == '*') {
            flag = match(matchStr, str, matchIdx + 1, idx) || match(matchStr, str, matchIdx, idx + 1);
        }
        if (matchStr.charAt(matchIdx) == str.charAt(idx)) {
            flag |= match(matchStr, str, matchIdx + 1, idx + 1);
        }
        return flag;
    }
 
    private static List<Integer[]> getMatchPosAndLen(String matchStr, String str) {
        List<Integer[]> ans = new ArrayList<>();
        for (int i = 0; i < str.length(); ++i) {
            if (matchStr.charAt(0) != '*' && matchStr.charAt(0) != str.charAt(i)) {
                continue;
            }
            for (int j = i; j < str.length(); ++j) {
                if (matchStr.charAt(matchStr.length() - 1) != '*' && matchStr.charAt(matchStr.length() - 1) != str.charAt(j)) {
                    continue;
                }
                if (match(matchStr, str.substring(i, j + 1), 0, 0)) {
                    ans.add(new Integer[]{i, j - i + 1});
                }
            }
        }
        if (ans.size() == 0) {
            ans.add(new Integer[]{-1, 0});
        }
        return ans;
    }
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        List<Integer[]> list = getMatchPosAndLen(matchStr, str);
        for (Integer[] arr : list) {
            System.out.println(arr[0] + " " + arr[1]);
        }
 
    }
}

暴力加略微剪枝，过了!

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> // 宏定义：限制各模块的最大长度，防止内存溢出 #define MAX_PART_NUM 20 // 模式串被*拆分后的最大固定段数量 #define MAX_MATCH_NUM 10000 // 最大匹配结果存储数量，避免数组越界 #define MAX_PATTERN_LEN 21 // 模式串最大长度（含结束符） #define MAX_STRING_LEN 1001 // 目标串最大长度（含结束符） // 定义匹配结果的结构体：存储子串的起始位置和长度 typedef struct { int start; // 匹配子串在目标串中的起始下标（从0开始） int len; // 匹配子串的长度 } MatchResult; /** * @brief 排序函数：用于qsort的比较规则，按要求排序匹配结果 * @param a 待比较的第一个匹配结果指针 * @param b 待比较的第二个匹配结果指针 * @return 排序差值：起始位置升序，同位置按长度升序 */ int compareMatches(const void *a, const void *b) { // 强制类型转换为MatchResult指针，方便访问成员 MatchResult *ma = (MatchResult *)a; MatchResult *mb = (MatchResult *)b; // 优先按起始位置升序排列 if (ma->start != mb->start) { return ma->start - mb->start; } // 起始位置相同时，按子串长度升序排列 return ma->len - mb->len; } /** * @brief 去重函数：移除排序后结果中重复的匹配项 * @param matches 已排序的匹配结果数组 * @param count 原始匹配结果的数量 * @return 去重后的有效结果数量 */ int deduplicateMatches(MatchResult *matches, int count) { // 边界条件：无结果或只有1个结果时，无需去重 if (count <= 1) return count; int unique = 1; // 记录去重后的结果数量，初始为1（第一个结果默认唯一） // 从第二个结果开始遍历，与前一个唯一结果比较 for (int i = 1; i < count; i++) { // 起始位置或长度不同，视为不同结果 if (matches[i].start != matches[unique-1].start || matches[i].len != matches[unique-1].len) { matches[unique++] = matches[i]; // 存入唯一结果数组 } } return unique; // 返回去重后的数量 } /** * @brief 拆分模式串：将带*的模式串拆分为若干非*的固定段 * @param p 输入的模式串 * @param parts 输出的固定段数组，存储拆分后的每个子串 * @param partLens 输出的固定段长度数组，存储每个子串的长度 * @return 拆分后的固定段数量 */ int splitPattern(const char *p, char parts[][MAX_PATTERN_LEN], int *partLens) { int partNum = 0; // 记录拆分出的固定段数量 int currentLen = 0; // 记录当前正在拼接的固定段长度 int pLen = strlen(p); // 计算模式串的总长度 // 遍历模式串的每个字符 for (int i = 0; i < pLen; i++) { if (p[i] == '*') { // 遇到*分隔符 // 若当前已有拼接的字符（避免连续*导致空段） if (currentLen > 0) { parts[partNum][currentLen] = '\0'; // 给当前段加结束符 partLens[partNum] = currentLen; // 记录当前段长度 partNum++; // 段数加1 currentLen = 0; // 重置当前段长度，准备下一段 } } else { // 遇到普通字符，拼接到当前段 parts[partNum][currentLen++] = p[i]; } } // 处理模式串末尾的非*段（最后一个字符不是*的情况） if (currentLen > 0) { parts[partNum][currentLen] = '\0'; partLens[partNum] = currentLen; partNum++; } return partNum; // 返回最终拆分的段数 } /** * @brief 单段匹配检查：判断目标串从pos开始是否匹配指定固定段 * @param s 目标串 * @param sLen 目标串总长度 * @param pos 目标串的起始检查位置 * @param part 待匹配的固定段 * @param partLen 固定段的长度 * @return 匹配返回true，不匹配返回false */ bool matchSinglePart(const char *s, int sLen, int pos, const char *part, int partLen) { // 边界检查：起始位置+段长度超过目标串长度，直接不匹配 if (pos + partLen > sLen) return false; // 逐字符比较，判断是否完全匹配 for (int i = 0; i < partLen; i++) { if (s[pos + i] != part[i]) { return false; // 有一个字符不匹配则返回false } } return true; // 所有字符匹配，返回true } /** * @brief 核心匹配函数：查找目标串中所有符合模式串规则的子串 * @param p 模式串 * @param s 目标串 * @param matches 输出的匹配结果数组 * @return 匹配结果的总数量 */ int findAllMatches(const char *p, const char *s, MatchResult *matches) { int pLen = strlen(p); // 模式串长度 int sLen = strlen(s); // 目标串长度 char parts[MAX_PART_NUM][MAX_PATTERN_LEN]; // 存储拆分后的固定段 int partLens[MAX_PART_NUM]; // 存储每个固定段的长度 // 拆分模式串，得到固定段数量 int partNum = splitPattern(p, parts, partLens); int matchCount = 0; // 记录匹配结果的数量 // 情况1：模式串全是*（拆分后无固定段），匹配所有可能的子串 if (partNum == 0) { // 枚举所有起始位置（0到sLen，包含空串的情况） for (int start = 0; start <= sLen; start++) { // 枚举所有可能的长度（0到sLen-start，包含空串） for (int len = 0; start + len <= sLen; len++) { matches[matchCount].start = start; matches[matchCount].len = len; matchCount++; // 结果数量加1 } } return matchCount; // 直接返回所有可能的子串数量 } // 情况2：模式串含固定段，需要按顺序匹配所有固定段 int firstPartLen = partLens[0]; // 第一个固定段的长度 // 枚举第一个固定段在目标串中的所有可能起始位置 for (int i0 = 0; i0 <= sLen - firstPartLen; i0++) { // 检查目标串i0位置是否匹配第一个固定段 if (!matchSinglePart(s, sLen, i0, parts[0], firstPartLen)) { continue; // 不匹配则跳过当前i0，尝试下一个位置 } int currentPos = i0 + firstPartLen; // 记录第一个段匹配后的结束位置 bool isValid = true; // 标记是否所有段都匹配成功 // 依次匹配后续的每个固定段 for (int j = 1; j < partNum; j++) { int currPartLen = partLens[j]; // 当前待匹配段的长度 bool found = false; // 标记当前段是否找到匹配位置 // 从currentPos开始，枚举当前段的所有可能起始位置 for (int k = currentPos; k <= sLen - currPartLen; k++) { // 检查k位置是否匹配当前段 if (matchSinglePart(s, sLen, k, parts[j], currPartLen)) { currentPos = k + currPartLen; // 更新当前结束位置 found = true; // 标记找到匹配 break; // 找到后跳出循环，匹配下一段 } } // 当前段未找到匹配位置，整个模式匹配失败 if (!found) { isValid = false; break; } } // 所有固定段都匹配成功，记录结果 if (isValid) { matches[matchCount].start = i0; // 匹配子串的起始位置（第一个段的起始） matches[matchCount].len = currentPos - i0; // 匹配子串的总长度（结束位置-起始位置） matchCount++; // 结果数量加1 } } return matchCount; // 返回最终匹配结果数量 } int main() { char p[MAX_PATTERN_LEN], s[MAX_STRING_LEN]; // 定义模式串和目标串的存储数组 MatchResult matches[MAX_MATCH_NUM]; // 定义匹配结果数组 int matchCount; // 记录匹配结果数量 // 读取模式串：fgets读取含换行符，用strcspn去除换行符 fgets(p, MAX_PATTERN_LEN, stdin); p[strcspn(p, "\n")] = '\0'; // 读取目标串：同理去除换行符 fgets(s, MAX_STRING_LEN, stdin); s[strcspn(s, "\n")] = '\0'; // 调用核心函数，查找所有匹配结果 matchCount = findAllMatches(p, s, matches); // 对匹配结果排序+去重：保证结果有序且唯一 if (matchCount > 0) { // 使用qsort排序，比较规则为compareMatches函数 qsort(matches, matchCount, sizeof(MatchResult), compareMatches); // 去重处理 matchCount = deduplicateMatches(matches, matchCount); } // 输出结果：有匹配则逐行输出，无匹配则输出-1 0 if (matchCount > 0) { for (int i = 0; i < matchCount; i++) { printf("%d %d\n", matches[i].start, matches[i].len); } } else { printf("-1 0\n"); } return 0; } </stdbool.h></string.h></stdlib.h></stdio.h>

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")
	}
}

Scanner scanner=new Scanner(System.in); String str1=scanner.nextLine(); String str2=scanner.nextLine(); String[] list = str1.split("\\*"); String s1=list[0]; String s2=list[1]; int begin=str2.indexOf(s1); while(begin!=-1){ int end=str2.indexOf(s2,begin);  while(end!=-1){
        System.out.println(begin+" "+(end+s2.length()-begin));  end=str2.indexOf(s2,end+1);  }
    begin=str2.indexOf(s1,begin+1); }

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * 实现字通配符*
 *
 * @author WU Jiahui
 * @date 2020/07/28 11:24
 */


public class Main {
    static boolean found = false;

    public static void search(char[] target, char[] text, int begin, int targetCur, int textCur, Set<Integer> set) {
        if (targetCur == target.length
                || (textCur == text.length && targetCur == (target.length - 1) && target[targetCur] == '*')) {
            found = true;
            if (!set.contains(textCur - begin) && textCur != begin) {
                set.add(textCur - begin);
                System.out.printf("%d %d\n", begin, textCur - begin);
            }
            return;
        }

        if (textCur == text.length) {
            return;
        }

        if (target[targetCur] == '*') {
            search(target, text, begin, targetCur + 1, textCur, set);
            search(target, text, begin, targetCur + 1, textCur + 1, set);
            search(target, text, begin, targetCur, textCur + 1, set);
        } else if (target[targetCur] == text[textCur]) {
            search(target, text, begin, targetCur + 1, textCur + 1, set);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String targetStr = scanner.nextLine();
        String textStr = scanner.nextLine();
        char[] target = targetStr.toCharArray();
        char[] text = textStr.toCharArray();
        for (int i = 0; i < text.length; i++) {
            search(target, text, i, 0, i, new HashSet<>());
        }
        if (!found) {
            System.out.printf("%d %d\n", -1, 0);
        }
    }
}

import sys

class Solution:
    def match(i, j):
        # Terminator:当t每个元素都匹配到
        if j == len(t):
            ans.add(i)
            # 千万不能忘记return
            return
        # 当前索引相等(小心越界)
        if i < len(s) and s[i] == t[j]:
            Solution.match(i + 1, j + 1)
        elif i < len(s) and t[j] == '*':
            # 1. 让*代表nothing
            Solution.match(i, j + 1)
            # 2. 让x代表s[i]
            Solution.match(i + 1, j + 1)
            # 2. 让*代表多个字符
            Solution.match(i + 1, j)
        return

if __name__ == "__main__":
    while True:
        # 读取第一行
        t = sys.stdin.readline().strip()
        if t == '':
            break
        s = input()
        # 存储答案
        ans = set()
        # 初始化没找到
        if_find = False
        # 定字符的开始坐标i
        for i in range(len(s)):
            if s[i] == t[0]&nbs***bsp;t[0] == '*':
                Solution.match(i, 0)
            if len(ans):
                if_find = True
                for last_index in sorted(ans):
                    if last_index > i:
                        print(i, last_index - i)
            ans.clear()
        if not if_find:
            print(-1, 0)

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] pat = sc.next().toCharArray();
		char[] str = sc.next().toCharArray();
        int count=0;

		for (int i = 0; i < str.length; i++) {
			for (int j = i; j < str.length; j++) {
				// 匹配str[i..j]
				if (match(pat, str, 0, i, j)) {
					System.out.println( String.valueOf(i) + " " + String.valueOf(j - i + 1));
                    count++;
				}
			}
		}
        if(count==0){
            System.out.println("-1 0");
        }
	}

	public static boolean match(char[] pat, char[] str, int pIndex, int left, int right) {

		if (pIndex == pat.length && left > right) {
            //恰好匹配完
			return true;
        }
		if (left > right && pIndex != pat.length && pat[pIndex] != '*') {
			//pat过长
            return false;
		}
        if (pIndex == pat.length && right >= left) {
			// str过长
			return false;
		}
		// pIndex!=length
		else if (pat[pIndex] == '*') {
			if (left > right) {
				return match(pat, str, pIndex + 1, left, right);
			} else {
				return match(pat, str, pIndex, left + 1, right) || match(pat, str, pIndex + 1, left, right);
			}
		} else if (left <= right && pat[pIndex] == str[left]) {
			return match(pat, str, pIndex + 1, left + 1, right);
		} else if (left <= right && pat[pIndex] != str[left]) {
			return false;
		} else {
			return false;
		}
	}
}

应该是暴力过，递归处理*那挺巧妙的

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

string s, t;
set<int> q;

void dfs(int i, int j)
{
    if(j == s.size())  q.insert(i);
    if(i == t.size())  return;
    
    if(t[i] == s[j])  dfs(i+1, j+1);
    else if(s[j] == '*')
    {
        dfs(i, j+1);
        dfs(i+1, j);
        dfs(i+1, j+1);
    }
}

int main()
{
    cin >> s >> t;
    bool flag = false;
    for(int i = 0; i < t.size(); i++)
    {
        if(s[0] == '*' || s[0] == t[i])
            dfs(i, 0);
        if(q.size())
        {
            flag = true;
            for(auto x : q)
                if(x > i)  cout << i << ' ' << x-i << endl;
        }
        q.clear();
    }
    if(!flag)   cout << -1 << ' ' << 0 << endl;
    
    return 0;
}

动态规划+适当剪枝即可AC，新人欢迎指导

def shipei(a,b):
    j=-1
    if a=='*':
        return True
    if '*' not in a:
        if len(a)!=len(b):
            return False
    for i in range(len(a)):
        j+=1
        if a[i]=='*':
            sp=False
            s=a[i+1::]
            for k in range(j,len(b)):
                sp=sp&nbs***bsp;shipei(s,b[k::])
            return sp
        else:
            if j<len(b):
                if a[i]!=b[j]&nbs***bsp;j>len(b):
                    return False
            else:
                return False
    return True
while True:
    try:
        str1=input()
        str2=input()
        n=0
        ans=[]
        sy=1
        x=str1[0]
        for i in range(len(str2)):
            if x==str2[i]&nbs***bsp;x=='*':
                for j in range(len(str2)):
                    if shipei(str1,str2[i:j+1]) and (j-i+1)>0:
                        sy=0
                        print(str(i)+' '+str(j-i+1))
        if sy==1:
            print('-1 0')
    except:
        break

动态规划过不去，内存不足。建议直接上回溯。

import java.util.*;
public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String pattern = sc.next();
        String str = sc.next();
        String[] pats = pattern.split("\\*");
        if(pattern.endsWith("*")){
            pats = Arrays.copyOf(pats,pats.length+1);
            pats[pats.length-1] = "";
        }
        if(pats.length >= 2){
            List<String> matches = new ArrayList<String>();
            int fromIndex = 0;
            while(true){
                boolean isEmpty = pats[0].equals("");
                int step = pats[0].equals("")?1:pats[0].length();
                int position = str.indexOf(pats[0],fromIndex);
                if(position > -1 && position < str.length()){
                    fromIndex = position + step;
                    matches = findNext(position, position + (isEmpty?0:step),1,pats, str, matches);
                }else{
                    break;
                }
            }
            if(matches.size() > 0){
                for(String s:matches){
                    System.out.println(s);
                }
            }else{
                System.out.println("-1 0");
            }

        }else if(pattern.equals("*")){
            for(int i =0 ; i<str.length(); i++){
                for(int j = i; j<str.length(); j++){
                    System.out.println(i+" "+(j-i+1));
                }
            }
        }else{
            System.out.println("-1 0");
        }

    }

    private static List<String> findNext( int startIndex, int fromIndex, int signIndex, String[] pats, String str, List<String> matches){
        fromIndex -= pats[signIndex].equals("")?1:0;
        while(true){
            int step = pats[signIndex].equals("")?1:pats[signIndex].length();
            int position = str.indexOf(pats[signIndex], fromIndex);
            if(position > -1 && position < str.length()){
                fromIndex = position + step;
            }else{
                break;
            }
            if(signIndex < pats.length -1){
                findNext(startIndex,fromIndex, signIndex+1,pats,str,matches);
            }else{
                matches.add(startIndex+" "+(position+step-startIndex));
            }
        }

        return matches;
    }
}