简答题
偏难
#7380
带通配符的字符串匹配 通配符是一类键盘字符,当我们不知道真正字符或者不想键入完整名字时,常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等,…
带通配符的字符串匹配
通配符是一类键盘字符,当我们不知道真正字符或者不想键入完整名字时,常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等,其中,“?”可以代替一个字符,而“*”可以代替零个或多个字符。
你的任务是,给出一个带有通配符的字符串和一个不带通配符的字符串,判断他们是否能够匹配。
例如,1?456 可以匹配 12456、13456、1a456,但是却不能够匹配23456、1aa456;
2*77?8可以匹配 24457798、237708、27798。
时间限制:1000
内存限制:65536
输入
输入有两行,每行为一个不超过20个字符的字符串,第一行带通配符,第二行不带通配符
输出
如果两者可以匹配,就输出“matched”,否则输出“not matched”
样例输入
1*456? 11111114567
样例输出
matched
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int f[3005][3005]={0},q[3005]={0},prt[3005][3005]={0};
string st1,st2;
int gcd(int a,int b)
{ if(b==0)return a;
return gcd(b,a%b);}
void Get(int x,int y)
{ if(x==0&&y==0)return;
int lx=x-1,ly=prt[x][y];
if(st1[x]=='*'&&y!=ly){q[++q[0]]=y-ly;}
Get(lx,ly);}
int main()
{ cin>>st1>>st2;
int i,j,k,bj,div,ans=0,len1=st1.length(),len2=st2.length();
st1=' '+st1;st2=' '+st2;
f[0][0]=1;
for(i=1;i<=len1;i++)
for(j=0;j<=len2;j++)
{if(st1[i]=='?'||st1[i]==st2[j])
{f[i][j]=f[i-1][j-1];
if(f[i][j])prt[i][j]=j-1;}
else if(st1[i]=='*')
{for(k=j,bj=0;k>=0;k--)
if(f[i-1][k]){bj=1;break;}
if(bj){f[i][j]=1;prt[i][j]=k;}}}
if(f[len1][len2])
{cout<<"matched\n";}
else cout<<"not matched";
return 0;}</pre><pre class="brush:cpp;toolbar:false">//解法2 动态规划
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
bool dp[30][30];//dp[i][j] 表示模式串s1的前i个字符和字符串s2的前j个字符是否匹配
int main() {
cin>>s1>>s2;
int l1=s1.size();
int l2=s2.size();
dp[0][0]=true;//将dp[0][0]置为 true,表示空字符串匹配
for(int i=1;i<=l1;i++)
for(int j=0;j<=l2;j++){
//如果s1[i-1]是*,则在dp[i-1][k]中寻找最后一个为true的位置(其中k>=j),
//如果找到,则将dp[i][j]置为true。
if(s1[i-1]=='*'){
for(int k=j;k>=0;k--){
if(dp[i-1][k]){
dp[i][j]=true;
break;
}
}
}else {
//如果当前字符可以匹配(即s1[i-1]==s2[j-1]或者s1[i-1]=='?')
//且前面的子问题匹配成功(dp[i-1][j-1] 为 true),则将dp[i][j]置为true。
if((s1[i-1]==s2[j-1]||s1[i-1]=='?') && (j && dp[i-1][j-1]))
dp[i][j]=true;
}
}
if(dp[l1][l2]) cout<<"matched";
else cout<<"not matched";
return 0;
}</pre>
这道题暂未补解析。