fork(7) download 
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #define INT_MAX 10000
  5. using namespace std;
  6.  
  7. bool minWindow(const char* S, const char *T, int &minWindowBegin, int &minWindowEnd) {
  8.   int sLen = strlen(S);
  9.   int tLen = strlen(T);
  10.   int needToFind[256] = {0};
  11.  
  12.   for (int i = 0; i < tLen; i++)
  13.     needToFind[T[i]]++;
  14.  
  15.   int hasFound[256] = {0};
  16.   int minWindowLen = INT_MAX;
  17.   int count = 0;
  18.   int begin,end,windowLen;
  19.   for (begin = 0, end = 0; end < sLen; end++) {
  20.  
  21.     if (needToFind[S[end]] == 0) continue;
  22.     hasFound[S[end]]++;
  23.     if (hasFound[S[end]] <= needToFind[S[end]])
  24.       count++;
  25.  
  26.  
  27.     if (count == tLen) {
  28.  
  29.       while (needToFind[S[begin]] == 0 || hasFound[S[begin]] > needToFind[S[begin]]) {
  30.         if (hasFound[S[begin]] > needToFind[S[begin]])
  31.           hasFound[S[begin]]--;
  32.         begin++;
  33.       }
  34.  
  35.       windowLen = end - begin + 1;
  36.       //cout<<windowLen<<endl;
  37.       if (windowLen < minWindowLen) {
  38.         minWindowBegin = begin;
  39.         minWindowEnd = end;
  40.         minWindowLen = windowLen;
  41.       } // end if
  42.     } // end if
  43.   } // end for
  44.  
  45.   //seeting end limit.
  46.   if(count == tLen){
  47.   while(1){
  48.   	if (needToFind[S[end]] == 0) end--;
  49.   	else break;
  50.   }//while
  51. cout<<begin<<"-"<<end<<endl;
  52. return true;
  53. }//if
  54.  
  55. return false;
  56.  
  57. }
  58. int main() {
  59. 	// your code goes here
  60. 	int begin=0, end=0;
  61. 	cout<<minWindow("this is a test string","tst",begin, end);
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 3456KB
comments (?)
stdin 
Standard input is empty
stdout 
13-16
1
https://ideone.com/79jBH9
smallest window in a string containing all characters of another string
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!