实现字通配符*

#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]);
        }
 
    }
}

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;
}

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

抄了1楼的答案，有几个很大的坑

#include
#include
using namespace std;
// 这道题和剑指Offer124页题目类似
// 不同的是这个题要在递归的同时输出字符串长度
bool match(const string &str,const string &pattern, int str_pos, int pat_pos, int start, int len){
    if(pattern[pat_pos] == '\0'){
//        printf("%d %d\n", start, len);
        cout << start << " " << len << endl;
        return true;
    }
    if(pattern[pat_pos] != '\0' && str[str_pos] == '\0') return false;
    // 当前指针没有碰到*的情况
    if(pattern[pat_pos] != '*'){
        // 比较两个字符是否相等
        if(pattern[pat_pos] == str[str_pos]){
            // 转移到下一个状态
            return match(str, pattern, str_pos + 1, pat_pos + 1, start, len + 1); 
        } else{
            return false;
        }
    } else{ // 碰到了'*' 
        // 模式串可以镶嵌 
        bool b_status = match(str, pattern, str_pos, pat_pos + 1, start, len);
        bool a_status = match(str, pattern, str_pos + 1, pat_pos, start, len + 1);
        return a_status || b_status; 
    }
    return false;
}
int main(){
    string pattern;
    string str;
    cin >> pattern >> str;
    if(pattern == "*"){
        for(int i = 0; i < str.length(); i++){ // 枚举前面的端点 
            for(int j = 1; i + j <= str.length(); j++){ // 枚举长度 
//                printf("%d %d\n", i, j);
                cout<< i << " " << j << endl;
            }
        }
        return 0;
    } 
    bool succ = false;
    // 从前到后枚举字符串起始点
    for(int i = 0; i < str.length(); i++){
        if(match(str, pattern, i, 0, i, 0)) succ = true;
    } 
    if(!succ){
//        printf("%d %d", -1, 0);        
        cout<< -1 << " " << 0 << endl;
    }
}

1. 递归传参要const string&否则超时
2. b_status和a_status前后的顺序，控制整体打印的顺序，打印顺序不符合要求调整这里即可。

class fun(): def __init__(self): # self.str1 = '*'  # self.str2 = 'shopeemoblie.com'  self.str1 = raw_input() self.str2 = raw_input() self.str1 = self.str1.split('*') self.position = [] self.ans = [] if len(self.str1)>1: self.get_position() # print self.position  self.get_ans() else: self.fun_error() if len(self.ans)>0: for i in self.ans: print i[0], i[1] else: self.fun_error() def get_position(self): for i in self.str1:
            temp = [] if len(i) == 0: for j in range(len(self.str2)):
                    temp.append(j) self.position.append(temp) else:
                tempp = self.str2.find(i, 0, len(self.str2)) while tempp != -1:
                    temp.append(tempp)
                    tempp = self.str2.find(i, tempp + len(i), len(self.str2)) self.position.append(temp) def get_ans(self): for i in self.position[0]:
            longs = [] self.is_ok(i,0,longs) if len(longs)>0: for j in longs: self.ans.append([i,j-i]) # print self.ans  return self.ans def is_ok(self,min,level,longs): for i in self.position[level+1]: if i >= int(min)+len(self.str1[level]): if level == len(self.str1) - 2: if len(self.str1[level+1])== 0:
                        longs.append(i + len(self.str1[level + 1])+1) else:
                        longs.append(i+len(self.str1[level+1])) else: self.is_ok(i,level+1,longs) def fun_error(self): print -1,0  exit(0)
test = fun()