daily pastebin goal
8%
SHARE
TWEET

Untitled

a guest Jan 18th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // C++ program to find smallest window containing
  2. // all characters of a pattern.
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. const int no_of_chars = 256;
  7.  
  8. // Function to find smallest window containing
  9. // all characters of 'pat'
  10. string findSubString(string str, string pat)
  11. {
  12.     int len1 = str.length();
  13.     int len2 = pat.length();
  14.  
  15.     // check if string's length is less than pattern's
  16.     // length. If yes then no such window can exist
  17.     if (len1 < len2)
  18.     {
  19.         cout << "No such window exists";
  20.         return "";
  21.     }
  22.  
  23.     int hash_pat[no_of_chars] = {0};
  24.     int hash_str[no_of_chars] = {0};
  25.  
  26.     // store occurrence ofs characters of pattern
  27.     for (int i = 0; i < len2; i++)
  28.         hash_pat[pat[i]]++;
  29.  
  30.     int start = 0, start_index = -1, min_len = INT_MAX;
  31.  
  32.     // start traversing the string
  33.     int count = 0; // count of characters
  34.     for (int j = 0; j < len1 ; j++)
  35.     {
  36.         // count occurrence of characters of string
  37.         hash_str[str[j]]++;
  38.  
  39.         // If string's char matches with pattern's char
  40.         // then increment count
  41.         if (hash_pat[str[j]] != 0 &&
  42.             hash_str[str[j]] <= hash_pat[str[j]] )
  43.             count++;
  44.  
  45.         // if all the characters are matched
  46.         if (count == len2)
  47.         {
  48.             // Try to minimize the window i.e., check if
  49.             // any character is occurring more no. of times
  50.             // than its occurrence in pattern, if yes
  51.             // then remove it from starting and also remove
  52.             // the useless characters.
  53.             while ( hash_str[str[start]] > hash_pat[str[start]]
  54.                 || hash_pat[str[start]] == 0)
  55.             {
  56.  
  57.                 if (hash_str[str[start]] > hash_pat[str[start]])
  58.                     hash_str[str[start]]--;
  59.                 start++;
  60.             }
  61.  
  62.             // update window size
  63.             int len_window = j - start + 1;
  64.             if (min_len > len_window)
  65.             {
  66.                 min_len = len_window;
  67.                 start_index = start;
  68.             }
  69.         }
  70.     }
  71.  
  72.     // If no window found
  73.     if (start_index == -1)
  74.     {
  75.     cout << "No such window exists";
  76.     return "";
  77.     }
  78.  
  79.     // Return substring starting from start_index
  80.     // and length min_len
  81.     return str.substr(start_index, min_len);
  82. }
  83.  
  84. // Driver code
  85. int main()
  86. {
  87.     string str = "this is a test string";
  88.     string pat = "tist";
  89.  
  90.     cout << "Smallest window is : \n"
  91.         << findSubString(str, pat);
  92.     return 0;
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top