当前位置: 代码迷 >> 综合 >> poj 2973 无序字符串含通配符的匹配
  详细解决方案

poj 2973 无序字符串含通配符的匹配

热度:34   发布时间:2024-01-19 06:22:34.0

题意:

求两个无序字符串含通配符的匹配。

分析:

直接统计字符频率即可。

代码:

//poj 2973
//sepNINE
#include <iostream>
#include <map>
#include <string>
using namespace std;
string dictionary[1024];
int num[32];
int tmp[32];
int main()
{int i,j,n;while(cin>>n&&n){for(i=1;i<=n;++i)cin>>dictionary[i];string c;cin>>c;			int cnt=0,ans=0;memset(num,0,sizeof(num));for(i=0;i<c.length();++i)if(c[i]=='_')++cnt;		else++num[c[i]-'A'];for(i=1;i<=n;++i){memset(tmp,0,sizeof(tmp));for(j=0;j<dictionary[i].length();++j)++tmp[dictionary[i][j]-'A'];int sum=0;for(j=0;j<='Z'-'A';++j)if(tmp[j]>num[j])sum+=tmp[j]-num[j];if(sum<=cnt)++ans;}printf("%d\n",ans);}return 0;	
}