字符串匹配

import java.util.*;
 
public class Main{
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String A = sc.nextLine();
        String B = sc.nextLine();
        StringBuilder sb = new StringBuilder();
        //将sb装换成模式匹配
        for(int i=0; i<B.length(); i++)
            if(B.charAt(i) == '?')
                sb.append("[01]{1}");
            else
                sb.append(B.charAt(i));
        Set<String> res = new HashSet<>();
 
        for(int i=0; i<=A.length()-B.length(); i++){
            String sub = A.substring(i, i+B.length());
            if(sub.matches(sb.toString()))
                res.add(sub);
        }
        System.out.println(res.size());
    }
}

用一个map来存字符串，暴力匹配时间复杂度n的平方。

当找到第一个字符串后进入循环，这里注意匹配条件，相等或者b[i]为0

#include<bits/stdc++.h>
using namespace std;
int main()
{
    unordered_set<string> strMap;
    string a, b;
    while(cin >> a >> b){
        int sizeA = a.size();
        int sizeB = b.size();
        for(int i = 0;i < sizeA - sizeB + 1;i++)
        {
            if(a[i] == b[0] || b[0] == '?'){
                int cnt = 0;
                for(int j = 0;j < sizeB;j++){
                    if(a[i + j] == b[j] || b[j] == '?')
                        cnt++;
                    else
                        break;
                }
                if(cnt == sizeB){
                    strMap.insert(a.substr(i, sizeB));
                }
            }
        }
        cout << strMap.size() << endl;
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] a = br.readLine().toCharArray();
        char[] b = br.readLine().toCharArray();

        HashSet<String> set = new HashSet<>();
        for (int i = 0; i <= a.length - b.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < b.length; j++) {
                if (b[j] == '?' || b[j] == a[i + j]) {
                    sb.append(a[i + j]);
                }
            }
            if (sb.toString().length() == b.length) set.add(sb.toString());
        }
        System.out.println(set.size());
    }
}

def solution(A,B):
    if len(B)>len(A):
        return 0
    s=len(B)
    count=0
    res=[]
    for i in range(len(A)-s+1):
        t=0
        for j in range(s):
            if B[j]=='?' or B[j]==A[i:i+s][j]:
                t+=1
                if t==s:
                    res.append(A[i:i+s])
            else:
                break
    return len(set(res))
A=raw_input().strip()
B=raw_input().strip()
print solution(A,B)

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

int main(){
    string A, B;
    cin>>A>>B;
    int n=A.length(), m=B.length(), s=0;
    if(n<m){
        puts("0");
        return 0;
    }
    vector<string> v;
    for(int i=0;i<n-m+1;i++){
        bool flag = true;
        for(int j=0;j<m;j++)
            if(A[i+j]!=B[j] && B[j]!='?')
                flag = false;
        if(flag){
            string t = A.substr(i, m);
            if(find(v.begin(), v.end(), t) == v.end())
                v.push_back(t);
        }
    }
    printf("%ld\n", v.size());
    return 0;
}

const readline = require("readline");

const r1 = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout,
});

let inArr = [];
let temp = [];
r1.on("line", (line) => {
    inArr.push(line.trim());
    let a = inArr[0];
    let b = inArr[1];
    a += "";
    b += "";
    if (inArr.length > 1) {
        let index = stringMatch(a, b, 0);
        while (index < a.length - b.length) {
            stringMatch(a, b, ++index);
        }
        temp = temp.filter((item, index) => temp.indexOf(item) == index);
        console.log(temp.length);
    }
});

var stringMatch = function (T, P, t) {
    let p = 0;
    if (T.length < P.length) return 0;
    while (t < T.length && p < P.length) {
        if (T[t] == P[p] || P[p] == "?") {
            t++;
            p++;
        } else {
            t = t - p + 1;
            p = 0;
        }
    }

    if (p >= P.length) {
        temp.push(T.slice(t - p, t - p + P.length));
        return t - p;
    }

    return 0;
};

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        // 输入数据
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();
        
        // 算法核心
        // 采用HashSet记录匹配成功的字符串，实现去重的目的
        HashSet<String> set = new HashSet<>();
        int al = a.length();
        int bl = b.length();
        for (int aStart = 0; aStart < al - bl + 1; aStart++) {
            // aStart表示新一轮匹配在a上的起点下标，要与b的0位置对齐
            boolean yes = true;
            for (int ai = aStart, bi = 0; bi < bl; ai++, bi++) {
                // 构造字符匹配成功的条件
                boolean match = b.charAt(bi) == '?' || b.charAt(bi) == a.charAt(ai);
                if (!match) {
                    // 若匹配失败
                    yes = false;
                    break;
                }
            }
            if (yes) {
                // 匹配成功时，对应在a上就是aStart ~ aStart + bl - 1上，
                // 将其记录进set中
                set.add(a.substring(aStart, aStart + bl));
            }
        }

        // 结果输出
        System.out.println(set.size());
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    cin>>a>>b;
    set<vector<char>> se;
    for(int i=0;i<=a.length()-b.length();i++)
    {
        vector<char> v;
        int flag=1;
        for(int j=0;j<b.length();j++)
        {
            if(b[j]==a[i+j])    continue;
            else if(b[j]=='?') v.push_back(a[i+j]);
            else    {flag=0;break;}
        }
        if(flag)    se.insert(v);
    }
    cout<<se.size()<<endl;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();
        HashSet<String> s = new HashSet<>();
        for (int i = 0; i < a.length() - b.length() + 1; i++) {
            int c = 0;
            for (int j = 0, k = i; j < b.length(); j++, k++) {
                if (b.charAt(j) == '?' || b.charAt(j) == a.charAt(k)) {
                    //匹配到b串中的字符个数+1
                    c++;
                }
            }
            //匹配的字符数等于b串长度，说明从第i项开始在a串中完成匹配，将匹配出的存入set
            if (c == b.length()) {
                s.add(a.substring(i, i + b.length()));
            }
        }
        System.out.print(s.size());
    }
}

var count = 0
func main() {
	var A,B string
	fmt.Scanf("%s",&A)
	fmt.Scanf("%s",&B)
	dfs([]byte(A),[]byte(B),0)
	fmt.Println(count)
}
//深度优先超时
func dfs (a,b []byte,i int){
	if i == len(b){
		if strings.Contains(string(a),string(b)){
			count++
		}
		return
	}
	if strings.Contains(string(a), string(b[:i+1])){
		dfs(a,b,i+1)
	}else{
		if b[i] == '?'{
			b[i] = '0'
			dfs(a,b,i+1)
			b[i] = '1'
			dfs(a,b,i+1)
			b[i] = '?'
		}
	}
}