Hard KMP Problem

Hard KMP Problem"/>

Hard KMP Problem

题目描述

给定两个串 SSS 和 TTT，你可以对这两个串分别进行重排，定义匹配度为最大的非负整数 xxx 使得能从 SSS 中选出 xxx 个不相交子串满足这几个子串都等于 TTT。请问重排后能获得的最大匹配度为多少。

输入描述:

本题多组数据。第一行一个数 t(1≤t≤5)t(1\leq t\leq 5)t(1≤t≤5)，表示数据组数。对于每组数据，一行为两个字符串 S,T(1≤∣S∣,∣T∣≤105)S,T(1\leq |S|,|T|\leq 10^5)S,T(1≤∣S∣,∣T∣≤105)，保证字符集为小写字母集。

输出描述:

TTT 个数，表示答案。

示例1

输入

2
abcadc
ac
bbbbbbb
bd

输出

2
0

代码

#include<bits/stdc++.h>
#include<string.h>
#include<cstring>
using namespace std;
#define IOO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//const int maxLine=5000+10;
//#define ll long long int
#define int long long int
#define um unordered_map<int,int>
#define vec vector<int>
const int maxLine=1e4+10;
//#define DEBUG true
//int n,m,k;//int arr[maxLine];//调用可以进行重定向
void initRedict() {
#ifdef DEBUGcout<<"执行重定向"<<endl;//重定向输入freopen("../redict/demo/demo_in.txt","r",stdin);
#endif
}int check(map<char,int> a,map<char,int> b){for (int i=1;;i++) for(map<char,int>::iterator it=b.begin();it!=b.end();it++){if (a[it->first]<b[it->first]*i) return i-1;}
}
int n;
string a,b;
signed main() {cin>>n;for(int i=0;i<n;i++){cin>>a>>b;map<char,int> mymap1,mymap2;for(int j=0;j<a.size();j++) mymap1[a[j]]++;for(int j=0;j<b.size();j++) mymap2[b[j]]++;int res=check(mymap1,mymap2);cout<<res<<endl;}return 0;
}

总能搜索得到一个倍数，表示map1最大能表示多少个map2

中途直接死循环，找不到满足条件的i就直接返回即可。