fork(2) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. #include <unordered_map>
  6. using namespace std;
  7.  
  8. constexpr size_t MAX_WORD_LEN = 20;
  9.  
  10. unordered_map<string, string> anagrams;
  11.  
  12. string get_sorted_word(const string& word)
  13. {
  14. 	auto sorted_word = word;
  15. 	sort(sorted_word.begin(), sorted_word.end());
  16. 	return sorted_word;
  17. }
  18.  
  19.  
  20. template<typename IteratorOfStrings>
  21. void prepare_anagrams(IteratorOfStrings first, IteratorOfStrings last)
  22. {
  23.     for (; first != last; ++first)
  24.     {
  25.         const std::string& word = *first;
  26.         anagrams.emplace(get_sorted_word(word), word);
  27.     }
  28. }
  29.  
  30. unordered_map<size_t, bool> _check_cache;
  31.  
  32. bool _check(const string& sentence)
  33. {
  34. 	if (sentence.length() <= MAX_WORD_LEN and anagrams.find(get_sorted_word(sentence)) != anagrams.end())
  35. 		return true;
  36.  
  37. 	size_t max_len = min(MAX_WORD_LEN, sentence.length());
  38. 	for (size_t i = 1; i < max_len; ++i)
  39. 	{
  40. 		auto prefix = get_sorted_word(sentence.substr(0, i));
  41. 		if (anagrams.find(prefix) == anagrams.end())
  42. 			continue;
  43. 		// Check cache.
  44. 		auto it = _check_cache.find(i);
  45. 		if (it != _check_cache.end())
  46. 		{
  47. 			if (it->second) return true;
  48. 			else continue;
  49. 		}
  50. 		// Calculate from scratch.
  51. 		auto sufix = sentence.substr(i);
  52. 		bool result = _check(sufix);
  53. 		_check_cache.emplace(i, result);
  54. 		if (result)
  55. 			return true;
  56. 	}
  57. 	return false;
  58. }
  59.  
  60. template<typename IterableOfStrings>
  61. bool check(
  62. 	const IterableOfStrings& words,
  63. 	const string& sentence
  64. )
  65. {
  66. 	prepare_anagrams(words.begin(), words.end());
  67. 	return _check(sentence);
  68. }
  69.  
  70.  
  71. int main() {
  72. 	vector<string> words = {"a", "aa", "aaa", "aaaa", "aaaaa"};
  73. 	string sentence = string(64'000, 'a') + string(1000, 'b');
  74. 	cout << check(words, sentence) << endl;
  75.  
  76. 	string test = "даладнаєї 我下午4點開始有空。";
  77.  
  78. 	cout << test << endl;
  79. 	for (size_t i=0; i < test.length(); ++i)
  80. 		cout << i << " " << test[i];
  81. 	cout << endl;
  82. 	for (const auto& c : test)
  83. 		cout << c;
  84. 	cout << endl;
  85.  
  86. 	return 0;
  87. }
Success #stdin #stdout 1.22s 2077132KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
даладнаєї 我下午4點開始有空。
0 �1 �2 �3 �4 �5 �6 �7 �8 �9 �10 �11 �12 �13 �14 �15 �16 �17 �18  19 �20 �21 �22 �23 �24 �25 �26 �27 �28 429 �30 �31 �32 �33 �34 �35 �36 �37 �38 �39 �40 �41 �42 �43 �44 �45 �46 �
даладнаєї 我下午4點開始有空。
https://ideone.com/njcrG4
language:
C++14 (gcc 8.3)
created:
15 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!