fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5. 	string s,t;
  6. 	cin>>s>>t;
  7.  
  8. 	int n = s.length();
  9. 	int m = t.length();
  10.  
  11. 	if(m>n){
  12. 		cout<<"0\n";
  13. 		exit(0);
  14. 	}
  15.  
  16. 	//sliding window from line 16 - 34
  17. 	string temp = "";
  18. 	vector<int>start_index;
  19. 	for(int i=0;i<m;++i){
  20. 		temp+=s[i];
  21. 	}
  22.  
  23. 	if(temp == t){
  24. 		start_index.push_back(0);
  25. 	}
  26.  
  27. 	for(int i=m;i<n;++i){
  28. 		temp.erase(temp.begin());
  29. 		temp+=s[i];
  30.  
  31. 		if(temp == t){
  32. 			start_index.push_back((i+1)-m);
  33. 		}
  34. 	}
  35.  
  36. 	int c=0;
  37. 	int sz = start_index.size();
  38. 	c = min(1,sz);
  39.  
  40. 	for(int i=1;i<sz;++i){
  41. 		if(start_index[i]-start_index[i-1]>=m){
  42. 			c++;
  43. 		}
  44. 	}
  45.  
  46. 	//all equal substring are overlapping ones 
  47. 	// so size of start_index  is equal to overlappinng substrings 
  48.  
  49. 	// c is the non overlapping substring equal to 't'
  50.  
  51. 	cout<<" Overlapping substrings equal to 't' "<<sz<<endl;
  52. 	cout<<" Non overlpaping substring equal to 't' "<<c<<endl;
  53.  
  54. }
Success #stdin #stdout 0s 5508KB
comments (?)
stdin
copy 
aaa
aa
stdout
copy 
 Overlapping substrings equal to 't' 2
 Non overlpaping substring equal to 't' 1
https://ideone.com/FHZsJM
aaa
aa
language:
C++14 (gcc 8.3)
created:
2 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!