首页 > 试题广场 >

子串模糊匹配

[编程题]子串模糊匹配
  • 热度指数:3512 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
从字符串string开始完整匹配子串sub,返回匹配到的字符个数。

sub中如果出现'?'表示可以匹配一到三个除'\0'以外的任意字符。
如果sub还有找不到匹配的字符,则说明不能完整匹配。

如果能完整匹配,返回匹配到的字符个数,如果有多种匹配方式,返回匹配字符数最少的那个,如果不能完整匹配,返回-1


输入描述:
第一行输入字符串string,长度小于10000

第二行输入子串sub,长度小于100


输出描述:
从string开头位置完整匹配sub,匹配到的字符个数。
示例1

输入

abcdefg
a?c

输出

3
示例2

输入

aabcddefg
a?c

输出

4
示例3

输入

aabcddefg
b?e

输出

-1
示例4

输入

aabcddefg
a?d

输出

5
import re

class Solution():
    def return_re_length(self, first_str, second_str):
        second_str_re = second_str.replace("?","(.*?)")
        number_wenhao = len(second_str) - len(second_str.replace("?",""))

        try:
            pattern = re.compile(r'{}'.format(second_str_re))
            res = pattern.match(first_str)
            #print(number_wenhao)

            for i in range(1,number_wenhao+1):
                if len(res.group(i)) == 0 or len(res.group(i)) > 3:
                    return -1

            return len(res.group(0))

        except:
            return -1


s1 = input()
s2 = input()
test = Solution()
print(test.return_re_length(s1, s2))
发表于 2019-07-30 19:50:07 回复(3)
// 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;
}

编辑于 2020-02-26 14:04:38 回复(2)
好像没有人用递归做...
import sys
 
def backtrace(p, s, cnt):
    if not p:
        return cnt
    if not s:
        return 0
    if p[0] == '?':
        res = sorted([backtrace(p[1:], s[1:], cnt+1), backtrace(p[1:], s[2:], cnt+2), backtrace(p[1:], s[3:], cnt+3)])
        return res[0] or res[1] or res[2]
    elif p[0] == s[0]:
        return backtrace(p[1:], s[1:], cnt+1)
    else:
        return 0
if __name__ == '__main__':
    string = sys.stdin.readline().strip()
    partten = sys.stdin.readline().strip()
    res = backtrace(partten, string, 0)
    if not res:
        print(-1)
    else:
        print(res)


发表于 2019-09-02 18:16:32 回复(5)

我这里用动态规划说一下思路吧
一下两张表分别是匹配不成功和成功的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;
    }
}
发表于 2019-08-09 18:06:14 回复(6)
#include<iostream>
using namespace std;


string s1,s2;
int len1,len2;
int fun(int index1,int index2)
{
    while(index1<len1&&index2<len2)
    {
        if(s2[index2]!='?'&&s1[index1]!=s2[index2])
            return -1;

        if(index1-index2>3)
            return -1;
        if(s1[index1]==s2[index2])
        {
            index1++;
            index2++;
            continue;
        }
        if(s2[index2]=='?'&&s1[index1]!='\0')
        {
            if(s1[index1+1]==s2[index2+1])
            {
                int temp=0;
                
                if((temp=fun(index1+1,index2+1))!=-1)
                {
                    return temp;
                }
                else
                {
                    index1++;
                }
            }
            else
                index1++;
        }
    }
    if(index2!=len2)
    {
        return -1;
    }
    else
    {
        return index1;
    }


    
    
}
int main()
{
    cin>>s1>>s2;
    len1=s1.length();
    len2=s2.length();
    if(len1==0||len2==0)
    {
        cout<<0<<endl;
        return 0;
    }
    cout<<fun(0,0)<<endl;
    //getchar();
    return 0;
}

发表于 2019-07-30 13:53:25 回复(8)
#include<iostream>
#include<cstring>
using namespace std;

int func(char*str , char* sub)
{
    int i=0,j=0;//i j 分别用来表示str、sub比较时的下标 
    int x = 0; //x用来表示?已经代替的字符个数 
    int count = 0;//count表示满足的字符个数
    
    while(i<strlen(str) && j<strlen(sub))
    {
        if(str[i] == sub[j])
        {
            i++;
            j++;
            count++;
            x = 0;
        }
        
        else if(sub[j] != '?')
            break;
            
        else    //sub[j] = '?'
        {
            while(str[i] != sub[j] && x<3)  
            {
                i++;
                if(!x) j++; //第一次x=0时,sub的下标也向后移动一个 
                x++;
                count++;
            }
            x=0;
        }
    }
    
    if(j == strlen(sub))
        return count;
    else 
        return -1;
}

int main()
{
    char str[1005];
    char sub[105];
    cin>>str>>sub;
    cout<<func(str,sub);
    return 0;
     
}

发表于 2020-02-13 00:48:40 回复(2)
正则
let str = readline();
let key = readline();
let re = key.split("?");
re = "^"+re.join(".{1,3}?");
re = RegExp(re);
const res = re.exec(str);
console.log(res?res[0].length:-1)


发表于 2019-09-15 14:54:35 回复(0)
笔试遇到这种题我都是能正则就正则,赶时间呐
import re

if __name__ == "__main__":
    string = input()
    pattern = "^" + input().replace('?', "\\S{1,3}")
    matches = re.findall(pattern, string)
    if not matches:
        print(-1)
    else:
        print(len(matches[0]))

发表于 2021-12-06 14:30:24 回复(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);
    }

}

发表于 2020-10-15 10:28:08 回复(0)
小白暴力法
string = input()
sub = input()


def solution(sub, string):
    if sub[0] != string[0]:
        return -1
    elif sub[0] == string[0] and sub in string:
        return len(sub)
    elif sub[0] == string[0] and '?' in sub:
        i = 1
        j = 1
        while i < len(sub) and j < len(string):
            if sub[i] == string[j]:
                i += 1
                j += 1
            elif sub[i] != string[j]:
                if sub[i] == '?':
                    for temp in range(3):
                        j += 1
                        if sub[i + 1] == string[j]:
                            i = i + 1
                            break
                        if temp == 2 and sub[i + 1] != string[j]:
                            return -1

                else:
                    return -1
        if i < len(sub):
            return -1

        return j


print(solution(sub, string))


发表于 2020-09-10 09:30:08 回复(0)
#include<iostream>
#
include<cstring>
#include<string>
using namespace std;

#
define MAXSTR 10000
#define MAXSUB 100

int func(char* str, char* sub);

int main()
{
    char str[MAXSTR];
    char sub[MAXSUB];
    while(cin>>str>>sub)
    {
        cout<<func(str,sub)<<endl;
    }
    return 0;
}

int func(char* str, char* sub)
{
    int i=0, j=0;    // i和j用来表示str和sub比较时所指的下标
    int x=0;        // x用来表示?所代替的字符个数
    int count = 0;    //计算字符匹配的个数
    
    while(i<strlen(str) && j<strlen(sub))
    {
        if(str[i] == sub[j])    //如果字符匹配,个数加1
        {
            i++;
            j++;
            count++;
            x=0;
        }
        else if(sub[j] == '?')    //如果sub中出现"?"
        {
            while(str[i] != sub[j] && x<3)
            {
                i++;
                if(!x) j++;        //    str[i]与sub中"?"后面的字符进行匹配是否一样
                count++;
                x++;
            }
            x=0;
        }
        else    //否则,str字符与sub字符没有匹配的了
        {
            break;
        }
    }
    
    if(j == strlen(sub))
    {
    return count;
    }
    else
    {
        return -1;
    }
}
发表于 2020-02-25 23:03:23 回复(4)
import re
 
strR = input()
strT = input()
strT = strT.replace('?', '\w{1,3}?')
rep = re.compile('^'+strT)
res = re.findall(rep, strR)
if res:
    ans = len(res[0])
    for i in res:
        l = len(i)
        if l < ans:
            ans = l
 
    print(ans)
else:
    print(-1)

正则才是真滴牛,这案例-1把我看吐了,也不来个提示还以为案例错了,结果是首字母匹配😒
发表于 2020-02-23 18:08:05 回复(5)
//正则表达式匹配
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)
}

发表于 2019-08-22 14:48:11 回复(0)
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);
	}
}

发表于 2019-08-12 15:33:40 回复(0)
示例2的输出为什么是4啊?不应该是3吗?从第二个a开始匹配
发表于 2022-09-04 20:52:42 回复(0)
#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;
}

发表于 2020-09-17 14:24:38 回复(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);
}

发表于 2020-09-16 03:25:17 回复(0)
使用并查集,根是并集中最小的那个数字,即区间左端
如何找到区间的左端:输入的左端点是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;
    }
}

发表于 2020-09-04 20:47:48 回复(0)


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


编辑于 2020-08-26 16:52:14 回复(0)
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))
用‘?’做分隔符,拆分sub序列,之后算各个拆分序列之间的距离,若都不大于四,返回sub的首尾距离,若有大于四的,返回-1。

发表于 2020-08-25 10:16:41 回复(0)