fork download
  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
stdin
Standard input is empty
compilation info
prog.c:7:20: fatal error: iostream: No such file or directory
 #include <iostream>
                    ^
compilation terminated.
stdout
Standard output is empty