Description
小火山获得了一个字符串，然而大火山让小火山从里面截取一段字符串，并且让小火山截取的字符串满足一些字符达到一定数量。
小火山觉得很容易，但是他想要知道他至少得截取多长的字符串。
Input
首先是一个整数t(t<=100)，表示测试数据组数。接下来是两个整数n和m(n<=10000, m<=10)，n表示字符串的长度，m表示要满足一定数量的字符
的种类.(字符只包含小写英文字母)
个数（没有重复字符种类），然后有m行，每行第一个是一个字符，然后是一个整数x(x<=50），表示这种字符的的要求数量。
Output
输出最小长度，如果达不到要求输出-1
Sample Input
1
6 3
cancan
c 2
a 2
n 2
Sample Output
6
一道很好的二分函数的直接应用 因为设计了多个单词的查找 变比一般的难上一点
#include<algorithm> #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<math.h> #define LL long long using namespace std; #define INF 0x3f3f3f3f #define N 10009 char str1[N]; int qq[30][N]; struct node {int w,a,ww;char str[12]; }q[N]; int main() {int T,n,m;scanf("%d",&T);while(T--){memset(q,0,sizeof(q));scanf("%d%d%s",&n,&m,str1);for(int i=0;i<m;i++){scanf("%s%d",q[i].str,&q[i].a);q[i].w=q[i].str[0]-'a';////q[i].w主要是转换成数字 ，方便下面的应用 }for(int i=0;i<n;i++){for(int j=0;j<m;j++) ///qq[q[j].w][i]按照递增，方便二分查找 {if(str1[i]==q[j].str[0]) ///统计q[j].ww ，比较a[i] 提前判断-1的情况q[j].ww++;if(i==0){if(str1[i]==q[j].str[0]) qq[q[j].w][i]=1;else qq[q[j].w][i]=0;}else if(str1[i]==q[j].str[0])qq[q[j].w][i]=qq[q[j].w][i-1]+1;elseqq[q[j].w][i]=qq[q[j].w][i-1];}}int s=0;for(int i=0;i<m;i++)if(q[i].ww<q[i].a)s=1;if(s==1)///特殊情况的输出 {printf("-1\n");continue;}int anss=INF,ans;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(str1[i]==q[j].str[0]){int e=i,ss=0;if(qq[q[j].w][n-1]-q[j].a+1<qq[q[j].w][i])///判断后面是否还够所需要的个数 {ss=1;break;}ans=lower_bound(qq[q[j].w],qq[q[j].w]+n,qq[q[j].w][i]+q[j].a-1)-qq[q[j].w];///利用二分查找，已知当前出现是第几个，在往后找第所需要的个数for(int k=j+1;k<m+j;k++)///利用for把所需要的个数全部遍历，在其中找到最近的也是最优的 {int kk=k%m;if(qq[q[kk].w][n-1]-q[kk].a<qq[q[kk].w][i])///判断后面是否还够所需要的个数 {ss=1;break;}ans=max(ans,lower_bound(qq[q[kk].w],qq[q[kk].w]+n,q[kk].a+qq[q[kk].w][i])-qq[q[kk].w]);///同上 }if(ss==0)anss=min(anss,ans-e+1);}}}printf("%d\n",anss);}return 0; }