fork download
copy 
  1. // C++ program to count total anagram 
  2. // substring of a string 
  3. #include <bits/stdc++.h> 
  4. using namespace std; 
  5.  
  6. // Total number of lowercase characters 
  7. #define MAX_CHAR 26 
  8.  
  9. // Utility method to return integer index 
  10. // of character 'c' 
  11. int toNum(char c) 
  12. { 
  13. 	return (c - 'a'); 
  14. } 
  15.  
  16. // Returns count of total number of anagram 
  17. // substrings of string str 
  18. int countOfAnagramSubstring(string str) 
  19. { 
  20. 	int N = str.length(); 
  21.  
  22. 	// To store counts of substrings with given 
  23. 	// set of frequencies. 
  24. 	map<vector<int>, int> mp; 
  25.  
  26. 	// loop for starting index of substring 
  27. 	for (int i=0; i<N; i++) 
  28. 	{ 
  29. 		vector<int> freq(MAX_CHAR, 0); 
  30.  
  31. 		// loop for length of substring 
  32. 		for (int j=i; j<N; j++) 
  33. 		{ 
  34. 			// update freq array of current 
  35. 			// substring 
  36. 			freq[toNum(str[j])]++; 
  37.  
  38. 			// increase count corresponding 
  39. 			// to this freq array 
  40. 			mp[freq]++; 
  41. 		} 
  42. 	} 
  43.  
  44. 	// loop over all different freq array and 
  45. 	// aggregate substring count 
  46. 	int result = 0; 
  47. 	for (auto it=mp.begin(); it!=mp.end(); it++) 
  48. 	{ 
  49. 		int freq = it->second; 
  50. 		result += ((freq) * (freq-1))/2; 
  51. 	} 
  52. 	return result; 
  53. } 
  54.  
  55. // Driver code to test above methods 
  56. int main() 
  57. { 
  58. 	string str = "abba"; 
  59. 	cout << countOfAnagramSubstring(str) << endl; 
  60. 	return 0; 
  61. } 
  62.  
Success #stdin #stdout 0s 4324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/b53ZU4
language:
C++14 (gcc 8.3)
created:
4 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!