fork download
copy 
  1. /**
  2.  * code generated by JHelper
  3.  * More info: https://g...content-available-to-author-only...b.com/AlexeyDmitriev/JHelper
  4.  * @author RiaD
  5.  */
  6.  
  7. #include <iostream>
  8. #include <fstream>
  9.  
  10. #include <iostream>
  11. #include <algorithm>
  12. #include <vector>
  13.  
  14.  
  15. template <typename T>
  16. T phi(T x) {
  17. 	T result = x;
  18. 	for (int i = 2; i * i <= x; ++i) {
  19. 		if (x % i == 0) {
  20. 			result /= i;
  21. 			result *= i - 1;
  22. 			while (x % i == 0) {
  23. 				x /= i;
  24. 			}
  25. 		}
  26. 	}
  27. 	if (x > 1) {
  28. 		result /= x;
  29. 		result *= x - 1;
  30. 	}
  31. 	return result;
  32. }
  33. #include <cassert>
  34.  
  35.  
  36. #include <iterator>
  37.  
  38.  
  39. #include <string>
  40. #include <stdexcept>
  41.  
  42. #ifndef SPCPPL_ASSERT
  43. 	#ifdef SPCPPL_DEBUG
  44. 		#define SPCPPL_ASSERT(condition) \
  45. 		if(!(condition)) { \
  46. 			throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
  47. 		}
  48. 	#else
  49. 		#define SPCPPL_ASSERT(condition)
  50. 	#endif
  51. #endif
  52.  
  53.  
  54. /**
  55. * Support decrementing and multi-passing, but not declared bidirectional(or even forward) because
  56. * it's reference type is not a reference.
  57. *
  58. * It doesn't return reference because
  59. * 1. Anyway it'll not satisfy requirement [forward.iterators]/6
  60. *   If a and b are both dereferenceable, then a == b if and only if *a and
  61. *   b are bound to the same object.
  62. * 2. It'll not work with reverse_iterator that returns operator * of temporary which is temporary for this iterator
  63. *
  64. * Note, reverse_iterator is not guaranteed to work  now too since it works only with bidirectional iterators,
  65. * but it's seems to work at least on my implementation.
  66. *
  67. * It's not really useful anywhere except iterating anyway.
  68. */
  69. template <typename T>
  70. class IntegerIterator: public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
  71. public:
  72. 	explicit IntegerIterator(T value): value(value) {
  73.  
  74. 	}
  75.  
  76. 	IntegerIterator& operator++() {
  77. 		++value;
  78. 		return *this;
  79. 	}
  80.  
  81. 	IntegerIterator operator++(int) {
  82. 		IntegerIterator copy = *this;
  83. 		++value;
  84. 		return copy;
  85. 	}
  86.  
  87. 	IntegerIterator& operator--() {
  88. 		--value;
  89. 		return *this;
  90. 	}
  91.  
  92. 	IntegerIterator operator--(int) {
  93. 		IntegerIterator copy = *this;
  94. 		--value;
  95. 		return copy;
  96. 	}
  97.  
  98. 	T operator*() const {
  99. 		return value;
  100. 	}
  101.  
  102. 	bool operator==(IntegerIterator rhs) const {
  103. 		return value == rhs.value;
  104. 	}
  105.  
  106. 	bool operator!=(IntegerIterator rhs) const {
  107. 		return !(*this == rhs);
  108. 	}
  109.  
  110. private:
  111. 	T value;
  112. };
  113.  
  114. template <typename T>
  115. class IntegerRange {
  116. public:
  117. 	IntegerRange(T begin, T end): begin_(begin), end_(end) {
  118. 		SPCPPL_ASSERT(begin <= end);
  119. 	}
  120.  
  121. 	IntegerIterator<T> begin() const {
  122. 		return IntegerIterator<T>(begin_);
  123. 	}
  124.  
  125. 	IntegerIterator<T> end() const {
  126. 		return IntegerIterator<T>(end_);
  127. 	}
  128.  
  129. private:
  130. 	T begin_;
  131. 	T end_;
  132. };
  133.  
  134. template <typename T>
  135. class ReversedIntegerRange {
  136. 	typedef std::reverse_iterator<IntegerIterator<T>> IteratorType;
  137. public:
  138. 	ReversedIntegerRange(T begin, T end): begin_(begin), end_(end) {
  139. 		SPCPPL_ASSERT(begin >= end);
  140. 	}
  141.  
  142. 	IteratorType begin() const {
  143. 		return IteratorType(IntegerIterator<T>(begin_));
  144. 	}
  145.  
  146. 	IteratorType end() const {
  147. 		return IteratorType(IntegerIterator<T>(end_));
  148. 	}
  149.  
  150. private:
  151. 	T begin_;
  152. 	T end_;
  153. };
  154.  
  155. template <typename T>
  156. IntegerRange<T> range(T to) {
  157. 	return IntegerRange<T>(0, to);
  158. }
  159.  
  160. template <typename T>
  161. IntegerRange<T> range(T from, T to) {
  162. 	return IntegerRange<T>(from, to);
  163. }
  164.  
  165. template <typename T>
  166. IntegerRange<T> inclusiveRange(T to) {
  167. 	return IntegerRange<T>(0, to + 1);
  168. }
  169.  
  170. template <typename T>
  171. IntegerRange<T> inclusiveRange(T from, T to) {
  172. 	return IntegerRange<T>(from, to + 1);
  173. }
  174.  
  175. template <typename T>
  176. ReversedIntegerRange<T> downrange(T from) {
  177. 	return ReversedIntegerRange<T>(from, 0);
  178. }
  179.  
  180. template <typename T>
  181. ReversedIntegerRange<T> downrange(T from, T to) {
  182. 	return ReversedIntegerRange<T>(from, to);
  183. }
  184.  
  185. template <typename T>
  186. ReversedIntegerRange<T> inclusiveDownrange(T from) {
  187. 	return ReversedIntegerRange<T>(from + 1, 0);
  188. }
  189.  
  190. template <typename T>
  191. ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  192. 	return ReversedIntegerRange<T>(from + 1, to);
  193. }
  194.  
  195. #include <map>
  196.  
  197. using namespace std;
  198.  
  199. vector<int> prefix_function (string s) {
  200. 	int n = (int) s.length();
  201. 	vector<int> pi (n);
  202. 	for (int i=1; i<n; ++i) {
  203. 		int j = pi[i-1];
  204. 		while (j > 0 && s[i] != s[j])
  205. 			j = pi[j-1];
  206. 		if (s[i] == s[j])  ++j;
  207. 		pi[i] = j;
  208. 	}
  209. 	return pi;
  210. }
  211.  
  212. class TaskF {
  213. public:
  214. 	void solve(std::istream& in, std::ostream& out) {
  215. 		string s, t;
  216. 		in >> s >> t;
  217. 		if (s.front() != t.front()) {
  218. 			out << -1;
  219. 			return;
  220. 		}
  221. 		if (s.back() != t.back()) {
  222. 			out << -1;
  223. 			return;
  224. 		}
  225. 		int n = (int)s.size();
  226. 		int phi = ::phi(n - 1);
  227. 		vector<int> used(n);
  228. 		std::map<int, vector<int>> can;
  229. 		for (int i = 1; i < s.size() - 1; ++i) {
  230. 			if (used[i]) {
  231. 				continue;
  232. 			}
  233. 			string cur;
  234. 			string cur2;
  235. 			for (int j = i; !used[j]; j = (2 * j) % (n - 1)) {
  236. 				used[j] = true;
  237. 				cur += s[j];
  238. 				cur2 += t[j];
  239. 			}
  240.  
  241. 			assert(phi % cur.size() == 0);
  242. 			//swap(cur, cur2);
  243. 			//cur += cur;
  244. 			string s = cur2 + "#" + cur + cur;
  245.  
  246. 			auto pi = prefix_function(s);
  247. 			//pi.erase(pi.begin(), pi.begin() + cur.size() + cur.size());
  248.  
  249. 			auto& mapa = can[cur.size()];
  250. 			if (mapa.empty()) {
  251. 				mapa.assign(cur.size(), 1);
  252. 			}
  253.  
  254.  
  255. 			for (int u = 0; u < cur.size(); ++u) {
  256. 				if (pi[u + 2 * cur.size()] != cur.size()) {
  257. 					mapa[u] = 0;
  258. 				}
  259. 			}
  260.  
  261. 		}
  262.  
  263.  
  264. 		for (int i: range(phi)) {
  265. 			bool can_all = true;
  266. 			for (auto& p: can) {
  267. 				if (!p.second[i % p.first]) {
  268. 					can_all = false;
  269. 					break;
  270. 				}
  271. 			}
  272. 			if (can_all) {
  273. 				out << i;
  274. 				return;
  275. 			}
  276.  
  277. 		}
  278. 		out << -1;
  279. 	}
  280. };
  281.  
  282.  
  283. int main() {
  284. 	std::ios_base::sync_with_stdio(false);
  285. 	TaskF solver;
  286. 	std::istream& in(std::cin);
  287. 	std::ostream& out(std::cout);
  288. 	in.tie(0);
  289. 	out << std::fixed;
  290. 	out.precision(20);
  291. 	solver.solve(in, out);
  292. 	return 0;
  293. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:7:20: fatal error: iostream: No such file or directory
 #include <iostream>
                    ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/fGHVGX
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

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!