Advertisement
Guest User

Untitled

a guest
May 27th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.99 KB | None | 0 0
  1. //.h
  2.  
  3. //
  4. // Created by max on 26.05.18.
  5. //
  6.  
  7. #ifndef LAB10_2_STRING_H
  8. #define LAB10_2_STRING_H
  9.  
  10.  
  11. #include <cstddef>
  12. #include <string>
  13. #include <vector>
  14. #include <iostream>
  15.  
  16. class SubstringIterator;
  17.  
  18. class String {
  19.  
  20. private:
  21. std::string string, sub;
  22. std::vector<std::string> palindromes;
  23.  
  24. friend class SubstringIterator;
  25.  
  26. void palindrome_search();
  27. bool check_palindrome(std::string substring);
  28. void next_sub();
  29.  
  30. public:
  31. size_t index;
  32. String(std::string s): string(s), index(0) {
  33.  
  34. palindrome_search();
  35. }
  36.  
  37. SubstringIterator begin();
  38. SubstringIterator end();
  39.  
  40. friend std::ostream& operator<< (std::ostream& os, const String& s) {
  41.  
  42. os << s.sub;
  43. return os;
  44. }
  45. };
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52. class SubstringIterator {
  53.  
  54. private:
  55.  
  56. size_t index_now, index_end;
  57. bool is_default;
  58.  
  59. bool is_end() const { return index_end == index_now; }
  60.  
  61. public:
  62. String *sub;
  63. SubstringIterator(): is_default(true) {}
  64.  
  65. explicit SubstringIterator(String &s): sub(&s),
  66. index_now(s.index),
  67. index_end(s.palindromes.size()),
  68. is_default(false) {
  69.  
  70. //std::cout << s.index << std::endl;
  71. }
  72.  
  73. bool operator == (const SubstringIterator &other) const;
  74. bool operator != (const SubstringIterator &other) const;
  75. String operator* ();
  76. SubstringIterator& operator++ ();
  77. SubstringIterator operator++ (int);
  78. };
  79.  
  80.  
  81. #endif //LAB10_2_STRING_H
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93. /////////////////////////////////////////////////
  94.  
  95. //.cpp
  96.  
  97. //
  98. // Created by max on 26.05.18.
  99. //
  100.  
  101. #include "String.h"
  102. #include <sstream>
  103. #include <unordered_set>
  104. #include <iostream>
  105.  
  106. bool String::check_palindrome(std::string substring) {
  107.  
  108. size_t len = substring.length();
  109. for(size_t i = 0; i < len / 2; i++)
  110. if (substring.at(i) != substring.at(len-i-1))
  111. return false;
  112.  
  113. return true;
  114. }
  115.  
  116. void String::palindrome_search() {
  117.  
  118. size_t size = string.size();
  119. std::unordered_set<std::string> hash_set;
  120. std::vector<int> options;
  121. for (size_t i = 0; i < size; i++)
  122. options.push_back(0);
  123.  
  124. int max = 1 << size;
  125.  
  126. for (int i = 1; i < max; i++) {
  127.  
  128. for (int j = 0; j < size; j++) {
  129.  
  130. if (i & (1 << j))
  131. options.at(size_t(j)) = 1;
  132. else
  133. options.at(size_t(j)) = 0;
  134. }
  135.  
  136. std::stringstream str;
  137. for (size_t j = 0; j < size; j++) {
  138.  
  139. if (options[j]) {
  140. str << string.at(j);
  141. }
  142. }
  143.  
  144. std::string substring;
  145. str >> substring;
  146. if (check_palindrome(substring) && (hash_set.find(substring) == hash_set.end())) {
  147.  
  148. hash_set.emplace(substring);
  149. if (i == 1)
  150. sub = substring;
  151. else
  152. palindromes.push_back(substring);
  153. }
  154. }
  155. }
  156.  
  157. void String::next_sub() {
  158.  
  159. //std::cout << "ind:" << index << " ";
  160. sub = palindromes.at(index++);
  161. //std::cout << "sub:" << sub << " ";
  162. }
  163.  
  164. SubstringIterator String::begin() {
  165.  
  166. return SubstringIterator(*this);
  167. }
  168.  
  169. SubstringIterator String::end() {
  170.  
  171. String x = *this;
  172. for (; x.index != x.palindromes.size(); x.next_sub());
  173.  
  174. return SubstringIterator(x);
  175. }
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183. bool SubstringIterator::operator==(const SubstringIterator &other) const {
  184.  
  185. return (is_default && other.is_default) ||
  186. (is_default && other.is_end()) ||
  187. (is_end() && other.is_default) ||
  188. (sub->index == other.sub->index);
  189. }
  190.  
  191. bool SubstringIterator::operator!=(const SubstringIterator &other) const {
  192.  
  193. return !(*this == other);
  194. }
  195.  
  196. String SubstringIterator::operator*() {
  197.  
  198. if (is_default || is_end()) {
  199. throw "Not initialized iterator";
  200. }
  201.  
  202. return String(*sub);
  203. }
  204.  
  205. SubstringIterator& SubstringIterator::operator++() {
  206.  
  207. if (is_default) {
  208. throw "Not Initialized iterator";
  209. }
  210.  
  211. if (is_end()) {
  212. throw "Iterator overflow";
  213. }
  214.  
  215. index_now++;
  216. sub->next_sub();
  217.  
  218. return *this;
  219. }
  220.  
  221. SubstringIterator SubstringIterator::operator++(int) {
  222.  
  223. SubstringIterator tmp(*this);
  224. operator++();
  225.  
  226. return tmp;
  227. }
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241. /////////////////////////////////////////////////////////
  242.  
  243. //main
  244.  
  245. #include <iostream>
  246. //#include "subsequence.h"
  247. #include "String.h"
  248. #include "subsequence.h"
  249.  
  250. int main() {
  251.  
  252. String s("qwewty");
  253.  
  254. auto end = s.end();
  255. std::cout << end.sub->index << std::endl;
  256.  
  257. try {
  258. for (auto it = s.begin(); it != s.end(); it++) {
  259. std::cout << it.sub->index << " " << end.sub->index << " ";
  260. //std::cout << *it << " ";
  261. }
  262. }
  263. catch (const char *err) {
  264. std::cout << err << std::endl;
  265. }
  266.  
  267. std::cout << std::endl;
  268. std::cout << end.sub->index << std::endl;
  269.  
  270. return 0;
  271. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement