首页 > 试题广场 >

字符串模式匹配

[编程题]字符串模式匹配
  • 热度指数：2315 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

给出两个字符串，分别是模式串P和目标串T，判断模式串和目标串是否匹配，匹配输出 1，不匹配输出 0。模式串中‘？’可以匹配目标串中的任何字符，模式串中的 ’*’可以匹配目标串中的任何长度的串，模式串的其它字符必须和目标串的字符匹配。例如P=a?b，T=acb，则P 和 T 匹配。


输入描述:
输入第一行包含一个字符串p， (1 ≤ |p| ≤ 20).
输入第二行包含一个字符串t， (1 ≤ |t| ≤ 20).


输出描述:
输出仅包含0和1的整数，0表示p和t不匹配，1表示p和t匹配。
示例1

输入

a?b
ab

输出

0
示例2

输入

a*b
ab

输出

1
示例3

输入

a*b
a(cb

输出

1

备注:
保证T中不包含 ‘*’ 字符和 ‘?’ 字符
算法知识视频讲解
添加回答
Asche头像 Asche 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String p = sc.next();
        String s = sc.next();
        // System.out.println(s + " - " + p);
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int i = 1; i <= n; i++) dp[0][i] = dp[0][i - 1] && p.charAt(i - 1) == '*';
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'){
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if(p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        System.out.println((dp[m][n] ? 1 : 0));
    }
}

发表于 2020-03-10 15:37:07 回复(7)
君亦流水头像 君亦流水 
#include <iostream>
(720)#include <string>
using namespace std;

int compare(string &strS, string &strT, int i, int j) {
    if (i >= strS.size()) {
        if (j >= strT.size())
            return 1;
        return 0;
    } 
    else if (j >= strT.size()){
        for (int k = i; k < strS.size(); k++)
            if (strS[k] != '*')
                return 0;
        return 1;
    }
    if (strS[i] == '*') {
        for (int k = j; k <= strT.size(); k++)
            if (compare(strS, strT, i+1, k))
                return 1;
        return 0;
    }
    if (strS[i] == '?') {
        if (compare(strS, strT, i+1, j+1))
            return 1;
        return 0;
    }
    if (strS[i] == strT[j])
        return compare(strS, strT, i+1, j+1);
    return 0;
}

int main() {
    string strS, strT;
    cin >> strS >> strT;
    cout << compare(strS, strT, 0, 0) << '\n';
    return 0;
}

回溯做的，当然动态规划更好了，但是我水平有限0.0
发表于 2020-04-03 22:33:39 回复(2)
Java
WhyVent头像 WhyVent 
import java.util.regex.Pattern;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String p = scanner.nextLine();
        String t = scanner.nextLine();
        
        if (Pattern.matches(p.replace("*",".*").replace("?","."),t)){
            System.out.println(1);
        }else {
            System.out.println(0);
        }
    }
}


发表于 2020-03-20 10:18:52 回复(3)
史宣豪头像 史宣豪
// java动态规划，高赞解法自己加的注释


import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String p = sc.next();
        String s = sc.next();
        // System.out.println(s + " - " + p);
        int m = s.length(), n = p.length();
        //dp[i][j]的含义：dp[i][j]表示s的前i个字符串和p的前j个字符是否匹配，p是模式串，s是目标串
        boolean[][] dp = new boolean[m + 1][n + 1];
        //初始化dp的第一行第一列
        dp[0][0] = true;
        //s前0个字符与p的i个字符，初始化dp的第一行其他列
        //第一列其他元素为false，不用再次声明
        for(int i = 1; i <= n; i++) dp[0][i] = dp[0][i - 1] && p.charAt(i - 1) == '*';
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果s的第i个元素与p的第j个元素相等（或p的第j元素为问号），那么dp[i][j] = dp[i - 1][j - 1];
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'){
                    dp[i][j] = dp[i - 1][j - 1];
                }
                //如果p的第j位是*，那么分两种情况，一种是s的第i位匹配到p的*之中，另一种是s的第i不匹配到*中，也就是*匹配空字符。两种情况只要有一种为true，那么dp[i][j]为true
                if(p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
                //如果不属于上述两种情况，那么说明最后一位无法匹配，dp[i][j]=false，因为本来就是false，所以不用再次声明
            }
        }
        System.out.println((dp[m][n] ? 1 : 0));
    }
}
发表于 2022-03-16 21:40:27 回复(0)
大可爱(￣^￣)ゞ头像 大可爱(￣^￣)ゞ
c++ 动态规划
#include<iostream>
#include<vector>
#include<string>
using namespace std;

bool match(char a, char b) {
    return a == b || a == '?';
}

int main() {
    string p, t;
    cin >> p >> t;
    int m = t.size();
    int n = p.size();
    vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
    dp[0][0] = true;
    for (int i = 1;i < m + 1;i++) {
        for (int j = 1;j < n + 1;j++) {
            if (p[j-1] == '*') {
                if (j == 1) dp[i][j] = true;
				dp[i][j] = dp[i-1][j] || dp[i][j];
				dp[i][j] = dp[i][j-1] || dp[i][j];
            } else if (match(p[j-1], t[i-1])) {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    int ret = dp[m][n] ? 1 : 0;
    cout << ret << endl;
    return 0;
}

发表于 2021-09-03 22:05:06 回复(0)
StephenDerick头像 StephenDerick
递归做的，用两个指针表示要匹配的下标，遇到*时要遍历所有*可能匹配的长度。 
def dfs(s1, s2, p1, p2):
    # s1或s2结束
    if p1>=len(s1):
        return p2>=len(s2)
    elif p2>=len(s2):
        return s1[p1] == "*" and dfs(s1, s2, p1 + 1, p2)     # s2结束，只有*能匹配空
    # 都未结束
    if s1[p1]!="*":
        if s1[p1]=="?":
            return dfs(s1, s2, p1+1, p2+1)
        else:
            return s1[p1]==s2[p2] and dfs(s1, s2, p1+1, p2+1)
    else:   # 为*可以匹配任意长度
        flag = False
        for i in range(0, len(s2)-p2+1):
            flag = flag&nbs***bsp;dfs(s1, s2, p1+1, p2+i)
        return flag
 
s1 = input()
s2 = input()
 
if dfs(s1, s2, 0, 0):
    print(1)
else:
    print(0)


发表于 2021-05-09 01:13:12 回复(0)
道纪macros头像 道纪macros 
#include <iostream>
#include <string>

using namespace std;

int main() {
    string p, t;
    cin >> p >> t;
    auto iter_t = t.begin();
    for (auto iter_p = p.begin(); iter_p != p.end(); iter_p++) {
        if (iter_t == t.end()) {
            cout << "0" << endl;
            return 0;
        }
        if (*iter_p == '?') {
            iter_t++;
        }
        else if (*iter_p == '*') {
            while (*iter_p == '*') {
                iter_p++;
            }
            if (iter_p == p.end()) {
                cout << "1" << endl;
                return 0;
            }
            else {
                while (iter_t != t.end() && *iter_t != *iter_p) {
                    iter_t++;
                }
                if (iter_t == t.end()) {
                    cout << "0" << endl;
                    return 0;
                }
                else {
                    iter_t++;
                }
            }
        }
        else if (*iter_p == *iter_t) {
            iter_t++;
        }
        else {
            cout << "0" << endl;
            return 0;
        }
    }
    if (iter_t == t.end()) {
        cout << "1" << endl;
    }
    else {
        cout << "0" << endl;
    }
    return 0;
}

发表于 2021-04-13 11:10:05 回复(0)
牛客0X0001号头像 牛客0X0001号 
#include <bits/stdc++.h>
using namespace std;

int main() {
    string p, t;
    cin >> p >> t;
    int n = p.size(), m = t.size();
    int i = 0, j = 0;
    int ii = -1, jj = -1;
    while (j < m) {
        if (p[i] == '*') {
            ii = ++i; jj = j;
        }
        else if (p[i] == t[j] || p[i] == '?') {
            ++i; ++j;
        }
        else if (ii == -1) {
            cout << "0\n";
            return 0;
        }
        else {
            i = ii; j = ++jj;
        }
    }
    while (i < n && p[i] == '*') ++i;
    cout << (i == n ? "1" : "0") << "\n";
}

发表于 2020-12-17 20:32:04 回复(0)
Soccer,soccer,soccer!头像 Soccer,soccer,soccer!

import java.util.Scanner;
 
public class Main{
   public static void main(String[] args)
   {        
       Scanner sc=new Scanner(System.in); 
       String s1_s = sc.nextLine();
       String s2_s = sc.nextLine();
       char[] s1 = s1_s.toCharArray();
       char[] s2 = s2_s.toCharArray();
       int begin = 0;
       int success = 0;
       int question = 0;
       int i = 0;
       int j = 0;
       for (; j < s2.length && i < s1.length; j++) 
       {
        /*
         * a*bcd*ef?
           adebcbcdghefh
         */
           if(s1[i] == '?')
           {
               i++; 
               continue;
           }
         if(s1[i] == '*' && i != s1.length - 1)
        {
            while(s1[i] == '*')
                i++;
             begin = i;
        }
         if(s1[i] != s2[j] && begin == 0 && question == 0)
                break;
         if(s1[i] != s2[j] && begin != 0 && s1[i] != '?'&& i != s1.length - 1)
            {
                i = begin;
            }
         if(s1[i] == '*' && i == s1.length - 1)
            {
                success = 1;
                break;
            }
         if(s1[i] == s2[j])
             {
                 i++;
             }
       }
       if(i == s1.length || success == 1)
           System.out.println(1);
       else
           System.out.println(0);
       
   }
}

发表于 2020-11-06 22:58:46 回复(0)
小贱贱XJJ头像 小贱贱XJJ 
暴力匹配:   private static int match(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int pLength = chars1.length;
        int tLength = chars2.length;
        int i = 0;
        int j = 0;
        boolean flag = false;
        while (true) {
            if (i >= chars1.length && j >= chars2.length) {
                flag = true;
                break;
            }
            if ("?".equals(chars1[i] + "")) {
                i++;
                j++;
            } else if ("*".equals(chars1[i] + "")) {
                if(i < pLength - 1){
                     if("*".equals(chars1[i + 1] + "")){
                         i++;
                         continue;
                     }
                     while (i < pLength - 1 && j < tLength && chars1[i + 1] != chars2[j]){
                         j++;
                     }
                     if(j == tLength){        //没有找到下一位跟chars1[i + 1]相等的存在
                         flag = false;
                         break;
                     }
                     i++;
                 }else{
                    flag = true;
                    break;
                 }
            } else {
                if ( i < pLength && j < tLength && chars1[i] == chars2[j]) {
                    i++;
                    j++;
                } else {
                    break;
                }
            }
        }
        return flag ? 1 : 0;
    }

发表于 2020-10-21 11:15:39 回复(0)
Python
小橙子&amp;头像 小橙子&amp; 
p = input().strip()
t = input().strip()
def DFS(p,t,i,j):
    if i == len(p) and j == len(t):
        return True
    if i == len(p):
        return False
    if j == len(t):
        return False
    if p[i] not in ['*','?']:
        if p[i] != t[j]:
            return False
        else:
            if DFS(p,t,i+1,j+1):
                return True
    else:
        if p[i] == '*':
            if DFS(p,t,i,j+1)&nbs***bsp;DFS(p,t,i+1,j+1)&nbs***bsp;DFS(p,t,i+1,j):
                return True
        else:
            if DFS(p,t,i+1,j+1):
                return True
if DFS(p,t,0,0):
    print(1)
else:
    print(0)

发表于 2020-08-22 16:22:46 回复(0)
牛客595198824号头像 牛客595198824号
请问考试的时候可以debug吗？这些import 之类的都要自己写吗？
发表于 2020-08-15 11:14:45 回复(1)
oskyupup头像 oskyupup 
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String pattern = scanner.nextLine();
        String str = scanner.nextLine();
        Boolean res = match(str, pattern, 0, 0);
        System.out.println(res?"1":"0");
    }
    static Boolean match(String str, String pattern, int i, int j){
        if (i>=str.length() && j>=pattern.length()) return true;
        if (i<str.length() && j>=pattern.length()) return false;
        if (pattern.charAt(j)=='*') {
            return (i<str.length() && match(str, pattern, i+1, j))
                    || match(str, pattern, i, j+1);
        }
        if ((i<str.length() && str.charAt(i)==pattern.charAt(j))
                || (pattern.charAt(j)=='?' && i<=str.length())) {
            return match(str, pattern, i+1, j+1);
        }
        return false;
    }

}

发表于 2020-08-15 09:31:53 回复(0)
冉兮兮头像 冉兮兮 
 
import java.util.Scanner;
 
public class Main {
     public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String T = scanner.nextLine();
        String P = scanner.nextLine();
        char []strP = P.toCharArray();
        char []strT = T.toCharArray();
        int lenP = strP.length;
        int lenT = strT.length;
        int [][]dp = new int[lenT+1][lenP+1];
        dp[0][0]=1;
        if(strT[0]=='*') dp[1][0]=1;
        for (int i = 1; i < lenT+1; i++) {
            int ii=i-1; 
            if (strT[ii]!='*' ){
                for (int j = 1; j < lenP+1; j++) {
                    if( strT[ii]==strP[j-1]||strT[ii]=='?' ){
                        dp[i][j]=dp[i-1][j-1];
                    }
                }
            }
            else if(strT[ii]=='*'){
                for (int j = 1; j < lenP+1; j++) {
                    if(dp[i-1][j]==1||dp[i][j-1]==1){
                        dp[i][j]=1;
                    }
                }
            }
        }
        System.out.println(dp[lenT][lenP]);
    }
}

发表于 2020-08-08 11:12:29 回复(0)
Java
只手遮星辰头像 只手遮星辰 
import java.util.Scanner;  public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String p = sc.nextLine(); String t = sc.nextLine();
    p = p.replace("?",".");
    p = p.replace("*",".{0,}"); if(t.matches("^"+p+"$")){  System.out.print(1);
        }  else {  System.out.print(0);
        }
    }
}

发表于 2020-06-24 09:09:44 回复(0)
大冲冲啊冲头像 大冲冲啊冲 
import java.util.*;
public class Main
{
    public static void main(String[] args){
        System.out.print(result());
    }
    public static int result(){
        Scanner sc = new Scanner(System.in);
        String str=sc.nextLine();
        String str2=sc.nextLine();
        char[] strArray=str.toCharArray();
        char[] strArray2=str2.toCharArray();
        int arrayseq=0;
        for(int i=0;i<strArray.length;i++){
            if(strArray[i]=='?'){
                arrayseq++;
                continue;
            }
            else if(strArray[i]=='*'){
                while (true){
                    if (i<strArray.length-1&& strArray[i+1]=='*') {
                        i++;
                    }
                    else {
                        break;
                    }
                }
                if(i==strArray.length-1){
                    return 1;
                }
                else{
 
                    for(int j=arrayseq;j<strArray2.length;j++){
                        if(strArray[i+1]==strArray2[j]){
                            arrayseq=j-1;
                            break;
                        }
                    }
                }
 
            }
            else{
                if(strArray[i]!=strArray2[arrayseq]){
                    return 0;
                }
            }
            arrayseq++;
            if ((i+1)==strArray.length-1&&arrayseq<strArray2.length-1){
                return 0;
            }
            else if (arrayseq==strArray2.length-1&&(i+1)<strArray.length-1){
                return 0;
            }
        }
        return 1;
 
    }
}


发表于 2020-04-27 22:20:25 回复(0)
福宇乔头像 福宇乔 
import re
str1 = input()
str2 = input() print(1 if(re.match(str1.replace('?', '.').replace("*", '.*'), str2) != None) else 0 )
发表于 2020-03-26 16:16:23 回复(0)
Karn头像 Karn 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        regixMatch();
    }
 
    private static void regixMatch(){
        Scanner scanner = new Scanner(System.in);
        String p = scanner.next();
        String t = scanner.next();
 
        int pLen = p.length(), tLen = t.length();
        boolean[][] dp = new boolean[pLen][tLen];
        for(int i = pLen - 1; i >= 0; i--){
            for(int j = tLen - 1; j >= 0; j--){
                if(p.charAt(i) == '*'){
                    if(i + 1 == pLen)
                        dp[i][j] = true;
                    else{
                        for(int k = j; k < tLen; k++){
                            dp[i][j] = dp[i][j] || dp[i + 1][k];
                        }
                    }
                    continue;
                }
                boolean isMatch = p.charAt(i) == t.charAt(j) || p.charAt(i) == '?';
                if(i + 1 == pLen && j + 1 == tLen) {
                    dp[i][j] = isMatch;
                }
                else if(i + 1 < pLen && j + 1 < tLen){
                    dp[i][j] = isMatch && dp[i + 1][j + 1];
                }else {
                    dp[i][j] = false;
                }
            }
        }
        int rst = dp[0][0] ? 1 : 0;
        System.out.println(rst);
    }
}

发表于 2020-03-25 20:08:23 回复(0)
XienX头像 XienX 
#include<iostream>
#include<string>
using namespace std;

bool match(int& i, int& j, string& p, string& t);
bool xmatch(int& i, int& j, string& p, string& t);

int main() {
	string  p,  t;
	int i = 0, j = 0;

	cin >> p >> t;
	
	if (match(i, j, p, t)) {
		cout << '1';
	}
	else{
		cout << '0';
	}

	return 0;
}

bool match(int& i, int& j, string& p, string& t) {
	while (i < p.length() && j < t.length()) {
		if (p[i] == t[j] || p[i] == '?') {
			i++;
			j++;
		}
		else if (p[i] == '*') {
			if (!xmatch(i, j, p, t)) {
				return false;
			}
		}
		else {
			return false;
		}
	}

	if (i == p.length() && j == t.length()) {
		return true;
	}
	else {
		return false;;
	}
}

bool xmatch(int &i, int &j, string &p, string &t) {
	if (++i == p.length()) {
		j = t.length();
		return true;
	}
	for (; j < t.length(); j++) {
		if (match(i, j, p, t)) {
			return true;
		}
	}
	return false;
}
递归思想
编辑于 2020-03-25 16:13:45 回复(1)
北神头像 北神
importjava.util.*;
 
publicclassMain {
     
    publicstaticvoidmain(String[] args) {
        Scanner scanner = newScanner(System.in);
        String pattern = scanner.nextLine();
        String target = scanner.nextLine();
        if(match(target, pattern))
            System.out.println(1);
        else{
            System.out.println(0);
        }
    }
    publicstaticbooleanmatch(String str, String pattern) {
        if(str == null|| pattern == null)
            returnfalse;
        returnmatchCore((str+="&").toCharArray(), (pattern+="&").toCharArray(), 0, 0);
    }
 
    publicstaticbooleanmatchCore(char[] str, char[] pattern, inti, intj) {
        if(str[i] == '&'&& pattern[j] == '&')
            returntrue;
        if(str[i] != '&'&& pattern[j] == '&')
            returnfalse;
        if(pattern[j] == '*'&& j + 1< pattern.length &&
                (pattern[j + 1] == str[i] || (pattern[j + 1]=='?'&& str[i] != '&'))) {
            returnmatchCore(str, pattern, i + 1, j + 2);
        } elseif(pattern[j] == '*'&& j + 1< pattern.length &&
                (pattern[j + 1] != str[i] && (pattern[j + 1]!='?'&& str[i] != '&'))) {
            returnmatchCore(str, pattern, i + 1, j);
        }
        if(pattern[j + 1] == '*') {
            if(pattern[j] == str[i] || (pattern[j] == '?'&& str[i] != '&'))
                returnmatchCore(str, pattern, i + 1, j + 2)         // * 指1
                        || matchCore(str, pattern, i + 1, j)     // *指 >=2
                        || matchCore(str, pattern, i, j + 2);      // * 指 0
            else
                returnmatchCore(str, pattern, i, j + 2);  // * 是0
        }
        if(pattern[j] == str[i] || (pattern[j] == '?'&& str[i] != '&'))
            returnmatchCore(str, pattern, i + 1, j + 1);
        returnfalse;
    }
}
发表于 2020-03-14 19:39:46 回复(0)
提交观点

问题信息

C++工程师 美团 2020 Java工程师
上传者：小小
难度：
20条回答 5872浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号