实现字通配符*

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

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

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