题解 | 实现字通配符*

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String p=in.nextLine();
            String s=in.nextLine();
            //*可以匹配空串的话会出现重复答案，所以用set去重
            Set<String> set=new LinkedHashSet<>();
            //从s的不同起点进行匹配
            for(int i=0;i<s.length();i++){
                dfs(p,s,0,i,i,set);
            }
            if(set.size()==0){
                System.out.println(-1+" "+0);
            }else{
                for(String res:set){
                    System.out.println(res);
                }
            }

            
        }
    }
    public static void dfs(String p,String s,int p1,int p2,int start,Set<String> set){
        //目标串用完时检查模式串是不是只剩下*
        while(p1<p.length()&&p2==s.length()&&p.charAt(p1)=='*'){
            p1++;
        }
        //模式串用完时就匹配出一个答案
        if(p1==p.length()){
            if(p2==start)return;
            set.add(start+" "+(p2-start));
            return;
        }
        //目标串用完结束递归
        if(p2==s.length())return;
        // System.out.println(p.charAt(p1)+"=="+s.charAt(p2));
        //消去*或常规匹配
        if(p.charAt(p1)==s.charAt(p2)||p.charAt(p1)=='*'){
            dfs(p,s,p1+1,p2+1,start,set);
        }
        //*匹配空串
        if(p.charAt(p1)=='*')dfs(p,s,p1+1,p2,start,set);
        //不消去*
        if(p.charAt(p1)=='*')dfs(p,s,p1,p2+1,start,set);
        
    }
}