Advertisement
Guest User

вфывфывф

a guest
May 26th, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.28 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long double ld;
  7. typedef long long ll;
  8. typedef unsigned long long ull;
  9. typedef pair<int, int> pii;
  10. typedef pair<long long, long long> pll;
  11.  
  12. #define pb emplace_back
  13. #define mp make_pair
  14. #define inf INFINITY
  15. #define fi first
  16. #define se second
  17. #define all(x) x.begin(), x.end()
  18. #define rall(x) x.rbegin(), x.rend()
  19.  
  20. template<class T, class U>
  21. istream &operator >> (istream &in, pair<T, U> &p) {
  22.     in >> p.fi >> p.se;
  23.     return in;
  24. }
  25.  
  26. template<class T, class U>
  27. ostream &operator << (ostream &out, const pair<T, U> &p) {
  28.     out << p.fi << ' ' << p.se;
  29.     return out;
  30. }
  31.  
  32. template<class T>
  33. istream &operator >> (istream &in, vector<T> &v) {
  34.     for (auto &i : v) {
  35.         in >> i;
  36.     }
  37.     return in;
  38. }
  39.  
  40. template<class T>
  41. ostream &operator << (ostream &out, const vector<T> &v) {
  42.     for (auto &i : v) {
  43.         out << i << '\n';
  44.     }
  45.     return out;
  46. }
  47.  
  48. inline void io(int x = 15) {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(nullptr);
  51.     cout.tie(nullptr);
  52.     srand(time(0));
  53.     cout << fixed << setprecision(x);
  54. }
  55.  
  56. vector <int> prefix_function (string s) {
  57.     int n = s.length();
  58.     vector <int> pi (n);
  59.     for (int i = 1; i < n; ++i) {
  60.         int j = pi[i - 1];
  61.         while (j > 0 && s[i] != s[j]){
  62.             j = pi[j - 1];
  63.         }
  64.         if (s[i] == s[j])  ++j;
  65.         pi[i] = j;
  66.     }
  67.     return pi;
  68. }
  69.  
  70. bool prime_test(ll n) {
  71.     for(ll i = 2; i * i <= n; ++i) if((n >= 0 && n < 2) || n % i == 0) return false;
  72.     return true;
  73. }
  74.  
  75. void prime_nums (int n, vector <char> &prime) {
  76.     //vector<char> prime (n + 1, true);
  77.     prime[0] = prime[1] = false;
  78.     for (ll i = 2; i * i <= n; ++i) {
  79.         if (prime[i]) {
  80.             for (int j = i * i; j <= n; j += i) {
  81.                 prime[j] = false;
  82.             }
  83.         }
  84.     }
  85. }
  86.  
  87. ll bin_pow(ll a, ll b, ll m = 0) {
  88.     if (m == 0) return b == 0 ? 1 : ( b % 2 ? bin_pow(a, b - 1) * a : bin_pow(a * a, b / 2) );
  89.     if (b == 0) return 1;
  90.     if (b % 2 == 0) {
  91.         ll temp = bin_pow(a, b / 2, m);
  92.         return (temp * temp) % m;
  93.     }
  94.     else return (a * bin_pow(a, b - 1, m)) % m;
  95. }
  96.  
  97. vector <pii> fact (int x) {
  98.     vector <pii> ans;
  99.     if (x == 1) {
  100.         return vector <pii> { mp(1, 1) };
  101.     }
  102.     for (int i = 2; i * i <= x; ++i) {
  103.         if (x % i == 0 && x) {
  104.             int p = 0;
  105.             while (x % i == 0) {
  106.                 ++p;
  107.                 x /= i;
  108.             }
  109.             ans.pb(mp(i, p));
  110.         }
  111.     }
  112.     if (x != 1) {
  113.         ans.pb(mp(x, 1));
  114.     }
  115.     return ans;
  116. }
  117.  
  118.  
  119.  
  120. vector <ll> POW, Hash;
  121. const ll MOD = 1e9 + 7, P = 101;
  122.  
  123. ll get_hash (int l, int r) {
  124.   return (MOD + Hash[r + 1] - Hash[l] * POW[r - l + 1]) % MOD;
  125. };
  126.  
  127.  
  128.  
  129. int main() {
  130.     io();
  131.     string s;
  132.     cin >> s;
  133.     int n = s.size();
  134.     Hash.resize(n + 1);
  135.     POW.resize(n + 1);
  136.     POW[0] = 1;
  137.  
  138.  
  139.     // Насчет степеней и хэша
  140.     for (int i = 0; i < n; i++) {
  141.         Hash[i + 1] = (Hash[i] * P + s[i] - 'a' + 1) % MOD + 1;
  142.         POW[i + 1] = (POW[i] * P) % MOD;
  143.     }
  144.    
  145.  
  146.  
  147.     if(s.size() == 1){
  148.         cout << "1 1";
  149.         return 0;
  150.     }
  151.  
  152.  
  153.  
  154.     int ans = 1;
  155.     int l = 0, r = 0;
  156.     for(int i = 0; i < n - 1; ++i){
  157.  
  158.         char a = s[i], b = s[i + 1]; // Символы из которых строится строка фибоначи
  159.  
  160.         ll tmp1 = get_hash(i, i); // hash от s[i]
  161.         ll tmp2 = get_hash(i + 1, i + 1); // hash от s[i + 1]
  162.  
  163.         // Хэши 2 соседних строк фибоначи
  164.  
  165.         int size1 = 1, size2 = 1;
  166.  
  167.         // Размеры 2 рассматриваемых строк фибоначи
  168.        
  169.         int l1 = i , r1 = i + 1; // Границы текущего ответа
  170.         while(r1 + size1 < n){
  171.             if(get_hash((r1 + 1), (r1 + size1)) == tmp1){
  172.                 r1 = r1 + size1;
  173.                 size1 = size2;
  174.                 size2 = (r1 - l1 + 1);
  175.                 tmp1 = tmp2;
  176.                 tmp2 = get_hash(l1, r1);
  177.             }
  178.             else{
  179.                 break;
  180.             }
  181.         }
  182.         if(r1 - l1 + 1 >= ans){
  183.             l = l1;
  184.             r = r1;
  185.         }
  186.  
  187.     }
  188.     cout << l << " " << r << endl;
  189.     return 0;
  190. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement