题目描述：

在BaiDu搜索引擎里,如何提高搜索效率是研发人员为之奋斗的目标。现在,JOBDU密码库里也有一段数字片段S(0<长度<=100,000),HQ想通过智能搜索得到包含关键字P(0<长度<=100,000)的某个数段长度,如果存在多个这样的数段,则选择长度最小的。例如,数字片段123456789,关键字为257.显然S本身就包含257,所以长度9是一个符合的数段,但是HQ从S中找到子串234567也包含关键字,并且无法找到更短的子串满足条件,因此返回结果6。PS：JOBDU密码库里的数字片段可能包含“*”,表示这一位可以是(0~9)中任意1个,具体见案例2。

 

 

 

输入：

输入有多个测试案例,每个测试案例1行,包括两个字串。

第一个为数字片段S(0<长度<=100,000),第二个为关键字P(0<长度<=100,000)。

 

 

 

输出：

根据输入案例返回查找结果,如果不存在包含关键字的数字片段则返回0。

 

 

 

 

 

样例输入：

123456789 25733**2*** 113

样例输出：

63

题目要求找到包含关键字的最短字段的长度。
需要用尺取法求解。
至于什么是尺取法，搜索一下，网上讲的非常好

代码如下

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6  7 char str[100002], test[100002]; 8 int goal[12]; 9 int has[12];10 11 12 bool isOk(int help) {13     for(int i = 0; i <= 9; i++) {14         if(has[i] < goal[i]) {15             int cha = goal[i] - has[i];16             if(help < cha) {17                 return false;18             }19             help = help - cha;20         }21     }22     return true;23 }24 25 int main(int argc, char const *argv[])26 {27     while(scanf("%s %s",str, test) != EOF) {28         memset(goal, 0, sizeof(goal));29         memset(has, 0, sizeof(has));30         int any = 0;31 32         int lent = strlen(test);33         for(int i = 0; i < lent; i++) {34             goal[test[i] - ‘0‘]++;35         }36         int ans = 100002;37         int from = 0, to = 0;38         int lens = strlen(str);39         bool isSuccess = true;40         while(to < lens) {41             while(to==0 || (!isOk(any) && to < lens)) {42                 43                 if(str[to] == ‘*‘) {44                     any++;45                 }46                 else {47                     has[str[to] - ‘0‘]++;48                 }49                 to++;50             }51             if(from == 0 && to == lens && !isOk(any)) {52                 isSuccess = false;53                 break;54             }55             int fir = true;56             while(fir || isOk(any)) {57                 58                 fir = false;59                 if(str[from] == ‘*‘) {60                     any--;61                 }62                 else {63                     has[str[from] - ‘0‘]--;64                 }65                 from++;66                 67             }68             int len = to - from + 1;69             ans = min(ans,len);70             71         }72         if(!isSuccess) {73             ans = 0;74         }75         printf("%d\n", ans);76     }    77     return 0;78 }

 

九度oj 题目1397：查找数段