fork(3) download
copy 
  1. /**
  2.  * Calculate the number of occurances of ALL permutations of a given word in a given text.
  3.  * INPUT: 
  4.  *	|word| |text|
  5.  *	word
  6.  *	text
  7.  * OUTPUT:
  8.  *	The number of times "word" or any permutation of it appears in "text".
  9.  * ALGORITHM: 
  10.  *   - Create a multiset of letters in "word".
  11.  *   - Go over "text", and check if any letter appears in the multiset.
  12.  *
  13.  * @author Erel Segal
  14.  * @date 2010-11-04
  15.  */
  16.  
  17. #include <iostream>
  18. #include <string>
  19. #include <algorithm>
  20. using namespace std;
  21.  
  22. typedef unsigned short ushort;
  23. typedef unsigned int uint;
  24.  
  25. // A multiset of letters - counts how many times each letter appears:
  26. class EnglishLettersMultiset {
  27. 	ushort caps[26], noncaps[26];
  28. 	ushort myCount;
  29. public:
  30. 	EnglishLettersMultiset() {
  31. 		fill_n(caps,26, (ushort)0);
  32. 		fill_n(noncaps,26, (ushort)0);
  33. 		myCount = 0;
  34. 	}
  35.  
  36. 	EnglishLettersMultiset& operator= (const EnglishLettersMultiset& other) {
  37. 		copy(other.caps,other.caps+26, caps);
  38. 		copy(other.noncaps,other.noncaps+26, noncaps);
  39. 		myCount = other.myCount;
  40. 		return *this;
  41. 	}
  42.  
  43. 	// Increase the counter for a single letter:
  44. 	void add(char c) {
  45. 		if ('A'<=c && c<='Z') {
  46. 			caps[c-'A']++;
  47. 			myCount++;
  48. 		} else if ('a'<=c && c<='z') {
  49. 			noncaps[c-'a']++;
  50. 			myCount++;
  51. 		} else throw string("tried to add an illegal char '")+c+string("'");
  52. 	}
  53.  
  54. 	// Decrease the counter for a single letter; returns true iff it exists.
  55. 	bool testAndRemove(char c) {
  56. 		if ('A'<=c && c<='Z') {
  57. 			if (caps[c-'A']>0) {
  58. 				caps[c-'A']--;
  59. 				myCount--;
  60. 				return true;
  61. 			} else return false;
  62. 		}	else if ('a'<=c && c<='z') {
  63. 			if (noncaps[c-'a']>0) {
  64. 				noncaps[c-'a']--;
  65. 				myCount--;
  66. 				return true;
  67. 			} else return false;
  68. 		} else throw string("tried to remove an illegal char '")+c+string("'");
  69. 	}
  70.  
  71. 	bool count() const { return myCount; }
  72. 	bool empty() const { return myCount==0; }
  73. }; // class EnglishLettersMultiset
  74.  
  75.  
  76.  
  77. uint countPermutations(const string& word, const string& text) {
  78. 	// Initialization: create a multiset of letters in word
  79. 	EnglishLettersMultiset wordLetters;
  80. 	string::const_iterator cWord, cText;
  81. 	for (cWord=word.begin(); cWord!=word.end(); ++cWord)
  82. 		wordLetters.add(*cWord);
  83.  
  84. 	uint count=0;
  85. 	EnglishLettersMultiset tempWordLetters=wordLetters;
  86. 	bool changed=true;
  87. 	for (cText=text.begin(); cText!=text.end(); ++cText) {
  88. 		//cout << *cText << ":";
  89. 		if (changed) {
  90. 			tempWordLetters = wordLetters; // restore the temporary multiset for the next iteration
  91. 			changed=false;
  92. 		}
  93. 		for (cWord=cText; cWord!=text.end(); ++cWord) {
  94. 			//cout << *cWord;
  95. 			if (!tempWordLetters.testAndRemove(*cWord)) { // no permutation starts at cText
  96. 				//cout << "-";
  97. 				break;
  98. 			} else {
  99. 				changed = true;
  100. 				if (tempWordLetters.empty()) { // found a permutation
  101. 					//cout << "+";
  102. 					count++;
  103. 					break;
  104. 				}
  105. 			}
  106. 		}
  107. 	//	cout << " ";
  108. 	}
  109. 	return count;
  110. }
  111.  
  112.  
  113.  
  114. void assertCount(string word, string text, uint expected) {
  115. 	time_t before = time(NULL);
  116. 	uint a = countPermutations(word,text);
  117. 	if (a!=expected) {
  118. 		cerr << "ERROR: Count of " << word << " in " << text << " should be " << expected << " but was " << a << endl;
  119. 	} else {
  120. 		time_t after = time(NULL);
  121. 		cout << "calculated cost of " << word.length() << "x" << text.size() << " chars in " << (after-before) << " seconds" << endl;
  122. 	}
  123. }
  124.  
  125.  
  126. void testIdentical(int N) {
  127. 	string word1(1, 'a');
  128. 	string word2(2, 'a');
  129. 	string text(N, 'a');
  130. 	assertCount(word1, text, N);
  131. 	assertCount(word2, text, N-1);
  132. 	assertCount(text, word1, 0);
  133. 	assertCount(text, word2, 0);
  134. }
  135.  
  136. void testAlmostIdentical(int N) {
  137. 	string word("ab");
  138. 	string text(N, 'a'); text += 'b';
  139. 	assertCount(word, text, 1);
  140. }
  141.  
  142.  
  143.  
  144. int main() {
  145. 	try {
  146. 		/* tests:  
  147. 		assertCount("cAda","AbrAcadAbRa",2);
  148. 		testIdentical(13);
  149. 		testAlmostIdentical(13);
  150. 		*/
  151.  
  152. 		uint nWord, nText;
  153. 		cin >> nWord >> nText;
  154.  
  155. 		string word, text;
  156. 		cin >> word >> text;
  157.  
  158. 		cout << countPermutations(word,text) << endl;
  159. 	} catch (string message) {
  160. 		cerr << "ERROR: " << message << endl;
  161. 	}
  162. }
  163.  
Success #stdin #stdout 0s 2868KB
comments (?)
stdin
copy 
4 11
cAda
AbrAcadAbRa
stdout
copy 
2
https://ideone.com/oCtej
language:
C++ (gcc 8.3)
created:
13 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!