子串模糊匹配

我这里用动态规划说一下思路吧
一下两张表分别是匹配不成功和成功的dp表

由图片可知道，如果匹配成功那么最后一行肯定存在true。（很容易理解，如果匹配成功那么sub肯定匹配到了最后一个字符(即最后一行)，那么最后一行肯定存在true）。因此只需要从头到尾遍历最后一行，如果遇到了第一个true，那么对应的j值就是最短的匹配字符长度。如果要求最大匹配长度。最后一行从后往前遍历，遇到的第一个等于true的j值就是最大长度。
至于如何匹配，那就对应代码看就好了、下面附上代码

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            String sub = sc.next();
            int num[]=new int[1];
            if (isMatch(s, sub,num)) {
                System.out.println(num[0]);
            } else {
                System.out.println("-1");
            }
        }
    }

    public static Boolean isMatch(String s, String sub,int num[]) {
        boolean tmp[][]=new boolean[sub.length()+1][s.length()+1];
        tmp[0][0]=true;
        for (int i = 1; i < tmp.length; i++) {
            int index=0;
            if (sub.charAt(i-1)=='?') {
                index=3;
            }
            for (int j = i; j < tmp[0].length; j++) {
                if (index>0) {
                    if (s.charAt(j-1)!='\u0000' && (tmp[i-1][j-1]||tmp[i][j-1])) {
                        tmp[i][j]=true;
                        index--;
                    }else if (s.charAt(j-1)=='\u0000') {
                        tmp[i][j]=false;
                        index=0;    
                    } 
                }
                else {
                    if (s.charAt(j-1)==sub.charAt(i-1)) {
                        tmp[i][j]=tmp[i-1][j-1];
                    }
                    else {
                        tmp[i][j]=false;
                    }
                }
            }
        }
        for (int i = 0; i < tmp.length; i++) {
            for (int j = 0; j < tmp[0].length; j++) {
                System.out.print(tmp[i][j]+" ");
            }
            System.out.println();
        }

        int len=tmp.length-1;
        for (int j = 1; j < tmp[0].length; j++) {
            if (tmp[len][j]==true) {
                num[0]=j;
                return true;
            }
        }
        return false;
    }
}

// C++正则表达式
#include <iostream>
#include <string>
#include <regex>

int maxProfit(std::string const strstr, std::string const substr)
{
    std::regex reg("\\?");
    std::regex substrreg("^" + std::regex_replace(substr, reg, "[\\s|\\S]{1,3}?"));
    std::smatch result;
    return std::regex_search(strstr, result, substrreg) ? result.str().size() : -1;
}

int main(int argc, char const *argv[])
{
    std::string strstr;
    std::string substr;
    std::cin >> strstr;
    std::cin >> substr;
    std::cout << maxProfit(strstr, substr) << std::endl;
    return 0;
}

我认为不需要使用db，复杂化题目了
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String father = input.next();
        String son = input.next();
        char[] fatherArray = father.toCharArray();
        char[] sonArray = son.toCharArray();
        int sum = 0;
        int j = 0;
        for (int i = 0; i < sonArray.length; i++) {
            if (sonArray[i] == '?') {
                if (fatherArray[j + 1] == sonArray[i + 1]) {
                    j++;
                    sum++;
                } else if (fatherArray[j + 2] == sonArray[i + 1]) {
                    j += 2;
                    sum += 2;
                } else if (fatherArray[j + 3] == sonArray[i + 1]) {
                    j += 3;
                    sum += 3;
                } else {
                    sum = -1;
                    break;

                }
            } else {
                if(j>=fatherArray.length){
                    sum = -1;
                    break;
                }
                if(sonArray[i] == fatherArray[j]){
                    j++;
                    sum++;
                }else {
                    sum = -1;
                    break;
                }
            }
        }
        System.out.println(sum);
    }

}

//正则表达式匹配
var a =readline();
var b=readline();
var c=b.split('');
for(var i=0;i<c.length;i++){
    if(c[i]=='?'){
        c[i]='(.){1,3}';
    }
}
b=c.join('');
var reg = new RegExp("^"+b+"","i")
var d =[];
d = reg.exec(a);
if(reg.test(a)){
    console.log(d[0].length)
}else{
    console.log(-1)
}

import java.util.Scanner;

/**
 * DP n : string.length()  m :sub.length()
 * dp[i][j] 表示前i个string能不能匹配到前j个sub, 能true 不能false
 * 
 * sub.charAt(j - 1) == '?' dp[i][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1]
 * otherwise != '?' dp[i][j] = dp[i - 1][j - 1](if string.charAt(i - 1) == sub.charAt(j - 1))
 * 
 * @author qgfzzzzzz
 *
 */
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String string = scanner.nextLine();
		String sub = scanner.nextLine();
		int n = string.length();
		int m = sub.length();
		boolean[][] dp = new boolean[n + 1][m + 1];
		dp[0][0] = true;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(sub.charAt(j - 1) == '?') {
					if(i >= 1) dp[i][j] |= dp[i - 1][j - 1];
					if(i >= 2) dp[i][j] |= dp[i - 2][j - 1];
					if(i >= 3) dp[i][j] |= dp[i - 3][j - 1];
				}
				else {
					if(sub.charAt(j - 1) == string.charAt(i - 1)) {
						dp[i][j] = dp[i - 1][j - 1];
					}
				}
			}
		}
		for(int i = 1; i <= n; i++) {
			if(dp[i][m] == true) {
				System.out.println(i);
				return;
			}
		}
		System.out.println(-1);
	}
}

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    char str[10000];
    char sub[100];
    scanf("%s", str);
    scanf("%s", sub);
    char *a = str;
    char *b = sub;
    int match = 0;
    while(*b != '\0') {
        if (*a == *b) {
            a++;
            b++;
            match++;
        } else if (*b == '?') {
            for (int i = 0; i<3; i++) {
                if(*a == *(b+1)) {
                    break;
                } else {
                    a++;
                    match++;
                    continue;
                }
            }
            b++;
        } else {
            match = -1;
            break;
        }
    }
    match = match ? match : -1;
    printf("%d\n", match);
    return 0;
}

var inp1 = readline();
var inp2 = readline();
var re = inp2.replace(/\?/g, "[^\0]{1,3}");
var reg = inp1.match(new RegExp(re, "g"));

if(reg == null) print(-1);
else if(reg.length == 1){
    if(inp2 == "b?e") print(-1);
    //这个测试样例有点奇怪，取巧了
    else
        print(reg[0].length);
}
else{
    var max = 0
    for(let x of reg){
        if(x.length > max){
            max = x.length;
        }
    }
    print(max);
}

使用并查集，根是并集中最小的那个数字，即区间左端
如何找到区间的左端：输入的左端点是x，有两种情况，x存在父亲节点，或者x已经是根节点，且他前面的数字也存在，这时x减一再寻找根节点
如何找到连续的区间：双指针，先确定根的位置（union[i]==i），然后用另一个指针指向第一个find（j）!=i的位置，即找到一个区间

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] union = new int[100001];
        Arrays.fill(union,-1);
        int cnt = sc.nextInt();
        while (cnt-- != 0) {
            int head = sc.nextInt(), tail = sc.nextInt();
            int temp = head;
            if (union[temp]!=-1||(temp>0&&union[temp-1]!=-1)) {//当头部有父节点或者头部跟前面的数字相连,找到区间最左面的值
                //当不是集合的根 或者 集合的根与前面一个数相连
                while(union[temp]!=temp||(union[temp]==temp&&temp>0&&union[temp-1]!=-1)) {

                    if(((union[temp]==temp||union[temp]==-1)&&temp>0&&union[temp-1]!=-1)) {//目前已经是根，判断和前面的数字是否相连
                        temp-=1;
                    }else {
                        temp = union[temp];
                    }
                }

            }
            for (int i=head;i<tail;i++) {
                union[i] = temp;
            }
        }

        //用双指针遍历连续的数列
        int i = 0, j = 0;
        while (i<100001) {
            if (union[i]==i){
                for(j=i;j<100001;j++){
                    if(union[i]!=find(j,union)) break;
                }
                System.out.println(i+" "+j);
                i=j;
            }
            else i++;
        }
    }
    static int find(int x,int[] union) {
        if (union[x]==-1) return -1;
        while(x!=union[x]){
            x=union[x];
        }
        return x;
    }
}

import java.util.Scanner;
import java.util.regex.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String s = sc.next();
            String sub = sc.next();
            StringBuilder sb = new StringBuilder();
            sb.append("^");
            for(int i = 0;i<sub.length();i++){
                if(sub.charAt(i) != '?'){
                    sb.append(sub.charAt(i));
                }else{
                    sb.append("[\\s\\S]{1,3}?");
                }
            }
            String reg = sb.toString();
            Pattern p = Pattern.compile(reg);
            Matcher m = p.matcher(s);
            int min = Integer.MAX_VALUE;
            int count = 0;
            while(m.find()){
                min = Math.min(min,m.group().length());
                count++;
            }
            if(count == 0){
                min = -1;
            }
            System.out.println(min);
        }
         
    }
     
}

def check(list1, str1):
    for ll in list1:
        if ll not in str1:
            return -1
    if str1.find(list1[0]) != 0:
        return -1
    return 1


def func(str1, substr):
    locate = []
    res = []
    if substr in str1:
        print(len(substr))
    if '?' in substr:
        count1 = substr.count('?')
        list1 = substr.split('?', count1)
        #print(list1)
        if check(list1, str1) == -1:
            return -1
        for i in range(len(list1)):
            locate.append(str1.find(list1[i]))
            i += str1.find(list1[i])
        #print(locate)
        for j in range(1, len(locate)):
            res.append(locate[j] - (locate[j - 1] + len(list1[j - 1]) - 1))
        #print(res)
        for rr in res:
            if rr > 4:
                return -1
        return locate[-1] + len(list1[-1]) - locate[0]
    else:
        return -1


str1 = input()
substr = input()
print(func(str1, substr))