九度oj 题目1397：查找数段

题目描述：: 在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 257

33**2*** 113

样例输出：

6

3

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

代码如下

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 using namespace std;

 char str[], test[];

 int goal[];

 int has[];

 bool isOk(int help) {

     for(int i = ; i <= ; i++) {

         if(has[i] < goal[i]) {

             int cha = goal[i] - has[i];

             if(help < cha) {

                 return false;

             }

             help = help - cha;

         }

     }

     return true;

 }

 int main(int argc, char const *argv[])

 {

     while(scanf("%s %s",str, test) != EOF) {

         memset(goal, , sizeof(goal));

         memset(has, , sizeof(has));

         int any = ;

         int lent = strlen(test);

         for(int i = ; i < lent; i++) {

             goal[test[i] - '']++;

         }

         int ans = ;

         int from = , to = ;

         int lens = strlen(str);

         bool isSuccess = true;

         while(to < lens) {

             while(to== || (!isOk(any) && to < lens)) {

                 if(str[to] == '*') {

                     any++;

                 }

                 else {

                     has[str[to] - '']++;

                 }

                 to++;

             }

             if(from ==  && to == lens && !isOk(any)) {

                 isSuccess = false;

                 break;

             }

             int fir = true;

             while(fir || isOk(any)) {

                 fir = false;

                 if(str[from] == '*') {

                     any--;

                 }

                 else {

                     has[str[from] - '']--;

                 }

                 from++;

             }

             int len = to - from + ;

             ans = min(ans,len);

         }

         if(!isSuccess) {

             ans = ;

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

九度oj 题目1397：查找数段

最新文章

热门文章