帶通配符的字符串匹配 -开发者知识库

帶通配符的字符串匹配 -开发者知识库,第1张

描述

通配符是一類鍵盤字符,當我們不知道真正字符或者不想鍵入完整名字時,常常使用通配符代替一個或多個真正字符。通配符有問號(?)和星號(*)等,其中,“?”可以代替一個字符,而“*”可以代替零個或多個字符。 

你的任務是,給出一個帶有通配符的字符串和一個不帶通配符的字符串,判斷他們是否能夠匹配。 

例如,1?456 可以匹配 12456、13456、1a456,但是卻不能夠匹配23456、1aa456; 
2*77?8可以匹配 24457798、237708、27798。

輸入輸入有兩行,每行為一個不超過20個字符的字符串,第一行帶通配符,第二行不帶通配符輸出如果兩者可以匹配,就輸出“matched”,否則輸出“not matched”樣例輸入
1*456?
11111114567
樣例輸出
matched

區間動規,對於字符st[i]討論:

'?' :f[i][j] = f[i-1][j-1]

‘*’:f[i][j] = f[i-1][j-1] || f[i][j-1] || f[i-1][j] 

'1'~'9':f[i][j]=f[i-1][j-1] & a[i-1]==b[j-1]

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 20
using namespace std;
int f[N][N];
string a,b;
void init(){
getline(cin,a);
getline(cin,b);
memset(f,0,sizeof f);
f[1][1]=1;
if (a[0]=='*') f[1][0]=1;
if (a[0]=='?') f[0][0]=1;
}
int main(){
init();
for (int i=1;i<=a.size();i )
for(int j=1;j<=b.size();j )
{
if (a[i-1]=='?') f[i][j]=f[i-1][j-1];
else if (a[i-1]=='*' && (f[i-1][j-1] || f[i][j-1] || f[i-1][j])) f[i][j]=1;
else if (a[i-1]==b[j-1] && f[i-1][j-1]) f[i][j]=1;
}
if (f[a.size()][b.size()]) cout <<"matched"<<endl;
else cout << "not matched" <<endl;
return 0;
}

 

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复