fork download
copy 
  1. // C++ program to search all anagrams of a pattern in a text 
  2. #include<iostream> 
  3. #include<cstring> 
  4. #define MAX 256 
  5. using namespace std; 
  6.  
  7. // This function returns true if contents of arr1[] and arr2[] 
  8. // are same, otherwise false. 
  9. bool compare(int arr1[], int arr2[]) 
  10. { 
  11. 	for (int i=0; i<MAX; i++) 
  12. 		if (arr1[i] != arr2[i]) 
  13. 			return false; 
  14. 	return true; 
  15. } 
  16.  
  17. // This function search for all permutations of pat[] in txt[] 
  18. void search(char *pat, char *txt) 
  19. { 
  20. 	int M = strlen(pat), N = strlen(txt); 
  21.  
  22. 	// countP[]: Store count of all characters of pattern 
  23. 	// countTW[]: Store count of current window of text 
  24. 	int countP[MAX] = {0}, countTW[MAX] = {0}; 
  25. 	for (int i = 0; i < M; i++) 
  26. 	{ 
  27. 		(countP[pat[i]])++; 
  28. 		(countTW[txt[i]])++; 
  29. 	} 
  30.  
  31. 	// Traverse through remaining characters of pattern 
  32. 	for (int i = M; i < N; i++) 
  33. 	{ 
  34. 		// Compare counts of current window of text with 
  35. 		// counts of pattern[] 
  36. 		if (compare(countP, countTW)) 
  37. 			cout << "Found at Index " << (i - M) << endl; 
  38.  
  39. 		// Add current character to current window 
  40. 		(countTW[txt[i]])++; 
  41.  
  42. 		// Remove the first character of previous window 
  43. 		countTW[txt[i-M]]--; 
  44. 	} 
  45.  
  46. 	// Check for the last window in text 
  47. 	if (compare(countP, countTW)) 
  48. 		cout << "Found at Index " << (N - M) << endl; 
  49. } 
  50.  
  51. /* Driver program to test above function */
  52. int main() 
  53. { 
  54. 	char txt[] = "AAABABAA"; 
  55. 	char pat[] = "AABA"; 
  56. 	search(pat, txt); 
  57. 	return 0; 
  58. } 
  59.  
Success #stdin #stdout 0s 4312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Found at Index 0
Found at Index 1
Found at Index 4
https://ideone.com/tocxBc
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!