fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5.  
  6.  
  7. const int M = 1000000007;
  8. const int N = 3e5+9;
  9. const int INF = 2e9+1;
  10. const int MAXN = 100000;
  11. const int LINF = 2000000000000000001;
  12.  
  13. //_ ***************************** START Below *******************************
  14.  
  15.  
  16.  
  17. string a;
  18. string b;
  19.  
  20.  
  21.  
  22. //* Find a in-side b 
  23. //* b == main string
  24.  
  25.  
  26. //* Template 1 : 
  27.  
  28. bool consistency1(int m, int n){
  29.  
  30. 	if(m>n) return false;	
  31.  
  32. 	unordered_map<char, int> mp;
  33. 	for(int i=0; i<m; i++){
  34. 	    mp[a[i]]++;
  35. 	}
  36. 	int size = mp.size();	
  37. 	int s = 0, e = 0;
  38. 	while(e<n){
  39. 	    if(mp.count(b[e])){
  40. 	        mp[b[e]]--;
  41. 	        if(mp[b[e]] == 0) size--;
  42. 	    }	
  43. 	    if(e-s+1 < m){
  44. 	        e++;
  45. 	    }
  46. 	    else{
  47. 	        if(size==0) return true;	
  48. 	        if(mp.count(b[s])){
  49. 	            mp[b[s]]++;
  50. 	            if(mp[b[s]] == 1) size++;
  51. 	        }
  52. 	        s++;
  53. 	        e++;
  54. 	    }
  55. 	}	
  56. 	return false;
  57. }
  58.  
  59.  
  60.  
  61.  
  62.  
  63. //* Find a in-side b 
  64. //* b == main string
  65.  
  66. //* Template 2 : 
  67.  
  68. bool consistency2(int m, int n){
  69.  
  70. 	if(m>n) return false;	
  71.  
  72. 	int k = m;
  73.  
  74.     unordered_map<char, int> mp;
  75.     for(auto& t : a) mp[t]++;
  76.  
  77.     int sz = mp.size(); 
  78.  
  79.     for(int i=0; i<n; i++){
  80.  
  81.         if(mp.count(b[i])){
  82.             mp[b[i]]--;
  83.             if(mp[b[i]] == 0) sz--;
  84.         }   
  85.  
  86.         //* Maintain window =>  By  removing  i-k - th element from window
  87.         if(i-k>=0){
  88.             if(mp.count(b[i-k]) ){
  89.                 mp[b[i-k]]++;
  90.                 if(mp[b[i-k]] == 1) sz++;
  91.             }
  92.         }   
  93.  
  94.         //* K sized  window  
  95.         if(i-k+1 >= 0){
  96.         	if(sz == 0) return true;    
  97.         }
  98.     }   
  99.  
  100.     return false;
  101. }
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115. //* Find a in-side b 
  116. //* b == main string
  117.  
  118. bool practice(int m, int n){
  119.  
  120. 	return true;
  121. }
  122.  
  123.  
  124.  
  125.  
  126. void solve() {
  127.  
  128. 	cin >> a >> b;
  129. 	int m = a.size();
  130. 	int n = b.size();
  131.  
  132. 	cout << boolalpha << consistency1(m, n) << " " << consistency2(m, n) << endl;
  133.  
  134. 	// cout << boolalpha << consistency1(m, n) << " -> " << practice(m, n) << endl;
  135.  
  136. }
  137.  
  138.  
  139.  
  140.  
  141.  
  142. int32_t main() {
  143.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  144.  
  145.     int t = 1;
  146.     cin >> t;
  147.     while (t--) {
  148.         solve();
  149.     }
  150.  
  151.     return 0;
  152. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
2
hello ooolleoooleh
hello ooolleooolehl
stdout
copy 
false false
true true
https://ideone.com/83NNDn
language:
C++14 (gcc 8.3)
created:
14 hours 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!