首页 > 代码库 > POJ 1580-String Matching(枚举)
POJ 1580-String Matching(枚举)
题目链接:http://poj.org/problem?id=1580
题意:给出两个串a,b,求它们的最大匹配度。最大匹配度=最大匹配个数*2/(len_a+len_b)
因为a和b的最开始匹配的部位都是任意的,所以枚举它们最开始匹配的部位即可。复杂度O(len_a*len_b*(k))k<=min(len_a,len_b);
其实这个穿应该都不是很长(不然这么挫的办法不可能0MS过。。)
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define ll long long #define maxn 360 #define pp pair<int,int> #define INF 0x3f3f3f3f #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; char s[100001],t[100001]; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } void solve() { int lens=strlen(s),lent=strlen(t),ans=-INF; for(int i=0;i<lens;i++) { for(int j=0;j<lent;j++) { int cnt=0; for(int k=i,m=j;k<lens&&m<lent;k++,m++) if(s[k]==t[m]) cnt++; ans=max(ans,cnt); } } ans*=2;int tem=gcd(ans,lens+lent); if(ans%(lens+lent)==0) printf("appx(%s,%s) = %d\n",s,t,ans/(lens+lent)); else printf("appx(%s,%s) = %d/%d\n",s,t,(ans/tem),(lens+lent)/tem); } int main() { while(~scanf("%s",s)&&s[0]!='-') { scanf("%s",t); solve(); } return 0; }
POJ 1580-String Matching(枚举)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。