首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#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&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;cmath&gt; #include&lt;string&gt; #include&lt;cstring&gt; 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&amp;&amp;y==0)return;     int lx=x-1,ly=prt[x][y];     if(st1[x]=='*'&amp;&amp;y!=ly){q[++q[0]]=y-ly;}     Get(lx,ly);} int main() {   cin&gt;&gt;st1&gt;&gt;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&lt;=len1;i++)        for(j=0;j&lt;=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&gt;=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&lt;&lt;"matched\n";}     else cout&lt;&lt;"not matched";     return 0;}</pre><pre class="brush:cpp;toolbar:false">//解法2 动态规划 #include &lt;bits/stdc++.h&gt;   using namespace std;  string s1,s2; bool dp[30][30];//dp[i][j] 表示模式串s1的前i个字符和字符串s2的前j个字符是否匹配 int main() { cin&gt;&gt;s1&gt;&gt;s2; int l1=s1.size(); int l2=s2.size(); dp[0][0]=true;//将dp[0][0]置为 true,表示空字符串匹配 for(int i=1;i&lt;=l1;i++) for(int j=0;j&lt;=l2;j++){ //如果s1[i-1]是*,则在dp[i-1][k]中寻找最后一个为true的位置(其中k&gt;=j), //如果找到,则将dp[i][j]置为true。 if(s1[i-1]=='*'){ for(int k=j;k&gt;=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]=='?') &amp;&amp; (j &amp;&amp; dp[i-1][j-1])) dp[i][j]=true; } } if(dp[l1][l2]) cout&lt;&lt;"matched"; else cout&lt;&lt;"not matched"; return 0; }</pre>
这道题暂未补解析。