fork download 
  1. #include<bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. const int no_of_chars = 256; 
  5.  
  6.  
  7. string findSubString(string str, string pat) 
  8. { 
  9.     int len1 = str.length(); 
  10.     int len2 = pat.length(); 
  11.  
  12.  
  13.  
  14.     int hash_pat[no_of_chars] = {0}; 
  15.     int hash_str[no_of_chars] = {0}; 
  16.  
  17.  
  18.     for (int i = 0; i < len2; i++) 
  19.         hash_pat[pat[i]]++; 
  20.  
  21.     int start = 0, start_index = -1, min_len = INT_MAX; 
  22.  
  23.  
  24.     int count = 0;  
  25.     for (int j = 0; j < len1 ; j++) 
  26.     { 
  27.         hash_str[str[j]]++; 
  28.  
  29.  
  30.         if (hash_pat[str[j]] != 0 && 
  31.             hash_str[str[j]] <= hash_pat[str[j]] ) 
  32.             count++; 
  33.  
  34.  
  35.         if (count == len2) 
  36.         { 
  37.  
  38.             while ( hash_str[str[start]] > hash_pat[str[start]] 
  39.                 || hash_pat[str[start]] == 0) 
  40.             { 
  41.  
  42.                 if (hash_str[str[start]] > hash_pat[str[start]]) 
  43.                     hash_str[str[start]]--; 
  44.                 start++; 
  45.             } 
  46.  
  47.  
  48.             int len_window = j - start + 1; 
  49.             if (min_len > len_window) 
  50.             { 
  51.                 min_len = len_window; 
  52.                 start_index = start; 
  53.             } 
  54.         } 
  55.     } 
  56.  
  57.  
  58.  
  59.     return str.substr(start_index, min_len); 
  60. } 
  61.  
  62. int main() 
  63. { 
  64.     string str;
  65.     string pat;
  66.  
  67.     getline(cin,str);
  68.     getline(cin,pat);
  69.  
  70.     cout << findSubString(str, pat)<<endl;
  71.     return 0; 
  72. } 
  73.  
  74.  
  75.  
Success #stdin #stdout 0s 4280KB
comments (?)
stdin 
qwerty asdfgh qazxsw
qas
stdout 
qazxs
https://ideone.com/vjPxmx
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!