首页 > 试题广场 >

字符串通配符

[编程题]字符串通配符

热度指数：187084 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 在计算机中，通配符是一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。让我们来学习通配符的匹配规则：
$\hspace{23pt}\bullet\,$ $\texttt{`*'}$ 符号代表匹配 $0$ 个或以上的数字或字母；
$\hspace{23pt}\bullet\,$ $\texttt{`?'}$ 符号代表匹配 $1$ 个数字或字母；
$\hspace{23pt}\bullet\,$ 小写字母字符代表匹配自身和自身的大写字母形态；
$\hspace{23pt}\bullet\,$ 大写字母字符代表匹配自身和自身的小写字母形态；
$\hspace{23pt}\bullet\,$ 其他字符代表匹配自身。

$\hspace{15pt}$ 现在，对于给定的通配符字符串 $s$ 和目标字符串 $p$ ，不考虑大小写，请判断 $s$ 是否可以匹配得到 $p$ 。如果可以，输出 $\rm true$ ；否则，输出 $\rm false$ 。

$\hspace{15pt}$ 在本题中，给定的字符串由 ASCII 码在 $33$ 到 $126$ 范围内的可见字符构成。您可以参阅下表获得其详细信息（您可能关注的内容是，这其中不包含空格、换行）。 ../图片/AllAscii.png

输入描述:

第一行输入一个长度为 、由可见字符构成的通配符字符串 。
第二行输入一个长度为  、由可见字符构成的目标字符串 。

输出描述:

如果可以匹配得到，输出 ；否则，输出 。

示例1

输入

z
zz

输出

false

示例2

输入

Z*
zz

输出

true

说明

在这个样例中， 匹配 。注意，由于不区分大小写， 可以匹配 。

示例3

输入

?*
zz

输出

true

说明

在这个样例中， 匹配 、 匹配 。

示例4

输入

**Z
0QZz

输出

true

说明

在这个样例中，其中一种匹配方法是：
第一个  匹配 ；
第二个  匹配 ；
第三个  匹配 。

示例5

输入

??**
zz

输出

true

说明

 可以匹配  个字符。

示例6

输入

HH?*
HH##1

输出

false

说明

可被  和  匹配的字符不包含 。

算法知识视频讲解

希望奇迹发生的鳄鱼很爱看电影

#include <stdio.h>
#include <string.h>
char s[101] = {0};
char p[101] = {0};
int result;
int cnt;
 int max;
void dfs(int sp, int pp) {
    if (cnt > max) return;
    if (sp == strlen(s)&&pp==strlen(p)) {
        result = 1;
        return;
    }
    int i = sp, j = pp;
    for (; i < strlen(s); i++, j++) {
        if (s[i] != p[j]) {
            if (s[i] =='?') {//拿S去对比p，遇到?看对面是不是?、数字、字母
                if (p[j] == '?' || (p[j] >= 0 && p[j] <= 9) || (p[j] >= 'a' && p[j] <= 'z'))
                    continue;
            } else if (s[i] == '*') { //遇到*，找到p中与s[i]=*后面第一个字符匹配的所有位置，对每个匹配位置的情况分析
                while (s[i] == '*') i++;
                if(i>=strlen(s)){
                    result = 1;
                    return;
                }
                if(s[i]!='?'){
                    int nj = j;
                    for (; nj < strlen(p); nj++) { //发现需要递归回溯
                        if (p[nj] == s[i]) {                       
                            cnt += nj - j;
                            dfs(i, nj);
                            cnt -= nj - j;
                        }
                    }
                }else if(s[i]=='?'){
                    int nj = j;
                    for (; nj < strlen(p); nj++) { //发现需要递归回溯
                        if (p[j] == '?' || (p[j] >= 0 && p[j] <= 9) || (p[j] >= 'a' && p[j] <= 'z')) { 
                            cnt += nj - j;
                            dfs(i, nj);
                            cnt -= nj - j;
                        }
                    }
                }
                continue;
            }
            break;
        }
    }
    if (i == strlen(s)&&j==strlen(p)) result = 1;
}




int main() {

    scanf("%s%s", s, p);
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') 
        s[i] = 'a' + s[i] - 'A';
    }
    for (int i = 0; i < strlen(p); i++) {
        if (p[i] >= 'A' && p[i] <= 'Z')
        p[i] = 'a' + s[i] - 'A';
    }
    int lens = 0; //s中非*字符个数
    int Fstar = 0;

    for (int i = 0; i < strlen(s); i++) {
        if (s[i] != '*') lens++;
        if (s[i] == '*') Fstar = 1;
    }
    if (lens == strlen(p)) {
        int ii = 0, jj = 0;
        for (; ii < strlen(s); ii++, jj++) {
            while (s[ii] == '*') ii++;
            if (s[ii] != p[jj]) {
                if (s[ii] == '?') {
                    if (p[jj] == '?' || (p[jj] >= 0 && p[jj] <= 9) || (p[jj] >= 'a' && p[jj] <= 'z'))
                        continue;
                }
                break;
            }
        }
        if (ii == strlen(s)) result = 1;
    } else if (lens < strlen(p)) {//2.一个有，一个没有 lens<lenp有*匹配
        if (Fstar) {
            max = strlen(p) - lens; //最大可匹配字数
            dfs(0, 0);
        }
    }
    if (!result) {
        printf("false");
    } else {
        printf("true");
    }
    return 0;
}

发表于 2025-10-15 15:41:30 回复(0)

牛客71635794号

//6ms递归

#include <ctype.h>

#include <stdio.h>

int ans(char *a, int lenA, int i, char *b, int lenB, int j) {
if (!(i < lenA) && j < lenB) return 0;
if (!(i < lenA) && !(j < lenB)) return 1;
if (a[i] == '?') {
return isalnum(b[j]) && ans(a, lenA, i+1, b, lenB, j+1);
} else if (a[i] == '*') {
while(a[i+1] == '*') {
i++;
}
if (a[i+1] == '\0') {
return 1;
}
for (int k = j; k < lenB; ++k) {
if (ans(a, lenA, i+1, b, lenB, k)) {
return 1;
}
}
return 0;
} else {
return tolower(a[i]) == tolower(b[j]) && ans(a, lenA, i+1, b, lenB, j+1);
}
}

int main() {
char a[101];
char b[101];
scanf("%s", a);
scanf("%s", b);
if (ans(a, strlen(a), 0, b, strlen(b), 0)) {
printf("true");
} else {
printf("false");
}
return 0;
}

发表于 2024-09-22 21:37:11 回复(0)

彭洋a

//确实是很多时候就是递归想不明白，还是需要借鉴一下递归

#include <stdio.h>

#include <string.h>

#include <ctype.h>

int cmp_str(char *std, char *str)

{

int i = 0, j = 0;

while (i < strlen(std) && j < strlen(str))

{

if (std[i] == '?')

{

if (isdigit(str[j])||isalpha(str[j]))

j++, i++;

else

return 0;

}

else if (std[i] == str[j])

i++, j++;

else if (std[i] == '*')

{

while (std[i + 1] == '*')

i++;

//三种情况匹配0个字符匹配下一个字符，匹配多个（std不动，还是*在匹配，str下移）

return cmp_str(std + i + 1, str + j) || cmp_str(std + i + 1, str + j + 1) || cmp_str(std + i, str + j + 1);

}

else

return 0;

}

if (i == strlen(std) && j == strlen(str))

return 1;

else

return 0;

}

int main()

{

char std[200];

char str[200];

while (scanf("%s %s",std,str) != EOF)

{

for (int k = 0; k < strlen(str); k++)

{

str[k] = tolower(str[k]);

}

for (int k = 0; k < strlen(std); k++)

{

std[k] = tolower(std[k]);

}

//全部替换成小写

if (cmp_str(std, str) == 1)

{

printf("true\n");

}

else

printf("false\n");

}

return 0;

}

发表于 2023-10-23 16:50:57 回复(0)

我不叫李大侠

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>

bool isCor(char c)
{
    if (isdigit(c) || islower(c)) {
        return true;
    }

    return false;
}

bool match(char *s1, char *s2)
{
    int i = 0; 
    int j = 0;
    int i_pre = 0;
    int j_pre = 0;
    int flag = 0;

    while (s2[j] != '\0') {
        s1[i] = tolower(s1[i]);
        s2[j] = tolower(s2[j]);
        if (s1[i] == '*' && isCor(s2[i])) {
            i_pre = i;
            j_pre = j;
            flag = 1;
            i++;
        } else if (s1[i] == '*') {
            i++;
        } else if (flag) {
            i = i_pre;
            j = j_pre + 1;
            flag = 0;
        } else {
            return false;
        }
    }

    while (s1[i] != '\0') {
        if (s1[i] != '*') {
            return false;
        }
        i++;
    }

    return true;
}
int main() {
    char str1[100] = {0};
    char str2[100] = {0};

    gets(str1);
    gets(str2);

    char *ret = match(str1, str2) ? "true" : "false";
    printf("%s\n", ret);
    return 0;
}

发表于 2023-08-31 10:59:29 回复(1)

学术垃圾

为什么这个用例匹配结果是false啊，求大神指点

te?t*123

text1234

发表于 2023-04-16 18:51:37 回复(2)

已注销

#include <stdio.h>
#include <string.h>
#define    N    100
int main()
{
    char s[N],p[N];
    int dp[N][N]={1},i,lenp,lens,j,k,flag;
    scanf("%s%s",p,s);
    lenp=strlen(p);
    lens=strlen(s);
    for(i=0;i<lenp;i++)
        if(p[i]>='A'&&p[i]<='Z')
            p[i]+='a'-'A';
    for(i=0;i<lens;i++)
        if(s[i]>='A'&&s[i]<='Z')
            s[i]+='a'-'A';
    for(i=0;i<lenp;i++)
    {
        for(j=0;j<lens;j++)
        {
            if(dp[i][j])
            {
                if(p[i]==s[j])
                {
                    dp[i+1][j+1]=1;
                }
                else if(p[i]=='*')
                {
                    dp[i+1][j]=1;
                    k=j;
                    while((s[k]>='0'&&s[k]<='9')||(s[k]>='a'&&s[k]<='z'))
                    {
                        dp[i+1][k+1]=1;
                        k++;
                    }
                }
                else if(p[i]=='?'&&((s[j]>='0'&&s[j]<='9')||(s[j]>='a'&&s[j]<='z')))
                {
                    dp[i+1][j+1]=1;
                }
            }
        }
    }
    if(dp[lenp][lens])
        printf("true");
    else
        printf("false");
    return 0;
}

疯狂打补丁。。。

发表于 2022-05-04 08:58:05 回复(0)

牛客743102380号

#include<stdio.h>
#include<string.h>

int max(int a, int b)
{
    return a>b?a:b;
}
int match(char a[] ,char b[])
{
    int lena = strlen(a);
    int lenb = strlen(b);
    int dp[100][100] = {0};
    dp[0][0] = 1;
    for(int j = 0;j < lenb;j++)
    {
        if((b[j] == '.') || ((b[j] >= '0') && (b[j] <= '9')) || ((b[j] >= 'a') && (b[j] <= 'z')) || ((b[j] >= 'A') && (b[j] <= 'Z')))
        {
            continue;
        }
        else
        {
            return 0;
        }
    }
    for(int i = 1;i <= lena;i++)
    {
        if(a[i - 1] == '*')
        {
            dp[i][0] = 1;
        }
        else
        {
            break;
        }
    }
    for(int i = 1;i <= lena;i++)
    {
        for(int j = 1;j <= lenb;j++)
        {
            if(a[i - 1] == '?')
            {
                dp[i][j] = max(dp[i][j] , dp[i-1][j-1]);
            }
            if((a[i - 1] == b[j - 1]) || (a[i - 1] == b[j - 1] + 32) || (a[i - 1] == b[j - 1] - 32))
            {
                dp[i][j] = max(dp[i][j] , dp[i-1][j-1]);
            }
            if(a[i - 1] == '*')
            {
                dp[i][j] = max(dp[i][j] , (dp[i-1][j] || dp[i][j - 1]));
            }
        }
    }
    return dp[lena][lenb];
    
}

int main()
{
    int m;
    char a[100],b[100];
    while(scanf("%s",&a) != EOF)
    {
        scanf("%s",&b) ;
        m = match(a, b);
         if(m == 1)
    {
        printf("true\n");
    }
    else{
        printf("false\n");
    }
    }
}

发表于 2021-08-24 01:29:51 回复(0)

80后大叔

没全对，差一点点

#include<stdio.h>
int isChar(char C) {
    if((C >= 'A' && C <= 'Z') || (C >= '0' && C <= '9') || C == '.') {
        return 1;
    } else {
        return 0;
    }
}

char changeUp(char C) {
    if(C >= 'a' && C <= 'z') {
        C -= 32;
    }
    return C;
}
int getDP(char a[500], char b[500]) {
    int m = strlen(a);
    int n = strlen(b);
    int dp[500][500] = {0}, maxlen = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            char p = changeUp(a[i]);
            char q = changeUp(b[j]);
            if((p == q) || 
               ((p == '?' || p == '*') && isChar(q) == 1 )) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if(dp[i][j] > maxlen) {
                    maxlen = dp[i][j];
//                     break;
//                     i--;
                }
            }
        }
    }
    return maxlen;
}
int main() {
    char a[500], b[500];
    while(gets(a) && gets(b)) {
        if(strstr(a, "*") == NULL && strstr(a, "?") == NULL) {
            if(strlen(a) == strlen(b)) {
                int result = 1;
                for(int i = 0; i < strlen(a); i++) {
                    if(a[i] != b[i]){
                        result = 0;;
                    }
                }
                if(result == 1) {
                    printf("true\n");
                } else {
                    printf("false\n");
                }
            } else {
                printf("false\n");
            }
            continue;
        }
        char sub[500] = {0};
        char *p = &a;
        char *q = p;
        while(*p != '\0') {
            if(*p != '*' && *p != '?') {
                q = p;
                break;
            }
            p++;
        }
        if(*p == '\0') {
            printf("true\n"); // 通配符字符串只包含*?，直接表示true
            continue;
        }
        int maxlen = 0;
        maxlen = getDP(a, b);
        int smallLen = strlen(a) < strlen(b) ? strlen(a): strlen(b);
//        printf("%d ", maxlen);
//        printf("%d\n", smallLen);
        if(maxlen >= smallLen) {
            printf("true\n");
        } else {
            printf("false\n");
        }

    }
}

发表于 2021-08-21 21:46:02 回复(0)

提交观点

问题信息

字符串

难度：

8条回答 3120收藏 38138浏览

通过挑战的用户

查看代码

猪儿拱

2023-02-26 22:43:42
帅阿衰

2023-01-08 10:20:13
hnSS

2023-01-02 16:02:27
芊樱烛渊

2022-10-30 20:15:16
牛客39961...

2022-10-30 10:33:48

字符串通配符

输入描述:

输出描述:

输入

输出

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题