SHARE
TWEET

dasdasd

a guest May 26th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. vector <ll> POW, Hash;
  120. const ll MOD = 1e9 + 7, P = 101;
  121.  
  122. ll get_hash (int l, int r) {
  123.     return (MOD * MOD + Hash[r + 1] - Hash[l] * POW[r - l + 1]) % MOD;
  124. };
  125.  
  126.  
  127.  
  128. int main() {
  129.     string s;
  130.     cin >> s;
  131.     int n = s.size();
  132.     Hash.resize(n + 1);
  133.     POW.resize(n + 1);
  134.     POW[0] = 1;
  135.  
  136.  
  137.     // Насчет степеней и хэша
  138.     for (int i = 0; i < n; ++i) {
  139.         Hash[i + 1] = (Hash[i] * P + s[i] - 'a' + 1) % MOD + 1;
  140.         POW[i + 1] = (POW[i] * P) % MOD;
  141.     }
  142.  
  143.  
  144.  
  145.     if(s.size() == 1){
  146.         cout << "1 1";
  147.         return 0;
  148.     }
  149.  
  150.  
  151.  
  152.     int ans = 1;
  153.     int l = 0, r = 0;
  154.     for(int i = 0; i < n - 1; ++i){
  155.  
  156.         ll tmp1 = get_hash(i, i); // hash от s[i]
  157.         ll tmp2 = get_hash(i, i + 1); // hash от s[i + 1]
  158.         // cout << tmp1 << " " << tmp2 << endl;
  159.  
  160.         // Хэши 2 соседних строк фибоначи
  161.  
  162.         int size1 = 1, size2 = 2;
  163.  
  164.         // Размеры 2 рассматриваемых строк фибоначи
  165.  
  166.         int l1 = i , r1 = i + 1; // Границы текущего ответа
  167.         while(r1 + size1 < n){
  168.             // cout << get_hash((r1 + 1), (r1 + size1)) << endl;
  169.             if(get_hash((r1 + 1), (r1 + size1)) == tmp1){
  170.                 r1 = r1 + size1;
  171.                 size1 = size2;
  172.                 size2 = (r1 - l1 + 1);
  173.                 tmp1 = tmp2;
  174.                 tmp2 = get_hash(l1, r1);
  175.             }
  176.             else{
  177.                 break;
  178.             }
  179.         }
  180.         // cout << l1 << "g " << r1 << endl;
  181.         if(r1 - l1 + 1 >= ans){
  182.             l = l1;
  183.             r = r1;
  184.             ans = r1 - l1 + 1;
  185.         }
  186.  
  187.     }
  188.     cout << ++l << ' ' << ++r;
  189.     return 0;
  190. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top