Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int, int> pii;
- typedef pair<long long, long long> pll;
- #define pb emplace_back
- #define mp make_pair
- #define inf INFINITY
- #define fi first
- #define se second
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- template<class T, class U>
- istream &operator >> (istream &in, pair<T, U> &p) {
- in >> p.fi >> p.se;
- return in;
- }
- template<class T, class U>
- ostream &operator << (ostream &out, const pair<T, U> &p) {
- out << p.fi << ' ' << p.se;
- return out;
- }
- template<class T>
- istream &operator >> (istream &in, vector<T> &v) {
- for (auto &i : v) {
- in >> i;
- }
- return in;
- }
- template<class T>
- ostream &operator << (ostream &out, const vector<T> &v) {
- for (auto &i : v) {
- out << i << '\n';
- }
- return out;
- }
- inline void io(int x = 15) {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- srand(time(0));
- cout << fixed << setprecision(x);
- }
- vector <int> prefix_function (string s) {
- int n = s.length();
- vector <int> pi (n);
- for (int i = 1; i < n; ++i) {
- int j = pi[i - 1];
- while (j > 0 && s[i] != s[j]){
- j = pi[j - 1];
- }
- if (s[i] == s[j]) ++j;
- pi[i] = j;
- }
- return pi;
- }
- bool prime_test(ll n) {
- for(ll i = 2; i * i <= n; ++i) if((n >= 0 && n < 2) || n % i == 0) return false;
- return true;
- }
- void prime_nums (int n, vector <char> &prime) {
- //vector<char> prime (n + 1, true);
- prime[0] = prime[1] = false;
- for (ll i = 2; i * i <= n; ++i) {
- if (prime[i]) {
- for (int j = i * i; j <= n; j += i) {
- prime[j] = false;
- }
- }
- }
- }
- ll bin_pow(ll a, ll b, ll m = 0) {
- if (m == 0) return b == 0 ? 1 : ( b % 2 ? bin_pow(a, b - 1) * a : bin_pow(a * a, b / 2) );
- if (b == 0) return 1;
- if (b % 2 == 0) {
- ll temp = bin_pow(a, b / 2, m);
- return (temp * temp) % m;
- }
- else return (a * bin_pow(a, b - 1, m)) % m;
- }
- vector <pii> fact (int x) {
- vector <pii> ans;
- if (x == 1) {
- return vector <pii> { mp(1, 1) };
- }
- for (int i = 2; i * i <= x; ++i) {
- if (x % i == 0 && x) {
- int p = 0;
- while (x % i == 0) {
- ++p;
- x /= i;
- }
- ans.pb(mp(i, p));
- }
- }
- if (x != 1) {
- ans.pb(mp(x, 1));
- }
- return ans;
- }
- vector <ll> POW, Hash;
- const ll MOD = 1e9 + 7, P = 101;
- ll get_hash (int l, int r) {
- return (MOD + Hash[r + 1] - Hash[l] * POW[r - l + 1]) % MOD;
- };
- int main() {
- io();
- string s;
- cin >> s;
- int n = s.size();
- Hash.resize(n + 1);
- POW.resize(n + 1);
- POW[0] = 1;
- // Насчет степеней и хэша
- for (int i = 0; i < n; i++) {
- Hash[i + 1] = (Hash[i] * P + s[i] - 'a' + 1) % MOD + 1;
- POW[i + 1] = (POW[i] * P) % MOD;
- }
- if(s.size() == 1){
- cout << "1 1";
- return 0;
- }
- int ans = 1;
- int l = 0, r = 0;
- for(int i = 0; i < n - 1; ++i){
- char a = s[i], b = s[i + 1]; // Символы из которых строится строка фибоначи
- ll tmp1 = get_hash(i, i); // hash от s[i]
- ll tmp2 = get_hash(i + 1, i + 1); // hash от s[i + 1]
- // Хэши 2 соседних строк фибоначи
- int size1 = 1, size2 = 1;
- // Размеры 2 рассматриваемых строк фибоначи
- int l1 = i , r1 = i + 1; // Границы текущего ответа
- while(r1 + size1 < n){
- if(get_hash((r1 + 1), (r1 + size1)) == tmp1){
- r1 = r1 + size1;
- size1 = size2;
- size2 = (r1 - l1 + 1);
- tmp1 = tmp2;
- tmp2 = get_hash(l1, r1);
- }
- else{
- break;
- }
- }
- if(r1 - l1 + 1 >= ans){
- l = l1;
- r = r1;
- }
- }
- cout << l << " " << r << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement