viewing paste Unknown #31449 | C++

Posted on the
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <map>
#include <set>
#include <cassert>
#include <cstring>
#include <queue>
 
#define SZ(x) int(x.size())
#define hash Hsh
#define InTheNameOfGod ios::sync_with_stdio(false); cin.tie(0);
 
using namespace std;
 
const int N = 5 * 1000 * 100 + 121;
 
typedef long long ll;
 
vector <int> p[N];
ll pbase1[N], pbase2[N], phash1[N], phash2[N], n, q, base1 = 727, base2 = 701, mod = 1000*1000*1000+7;
string s;
 
void sieve () {
        for (int i = 2; i < N; i++)
                if (p[i].empty())
                        for (int j = i; j < N; j += i)
                                p[j].push_back(i);
}
 
void partial_hash (string &s)
{
        pbase1[0] = pbase2[0] = 1;
        for (int i = 1; i  <= s.size(); i++)
        {
                phash1[i] = (1ll * phash1[i-1] * base1 + s[i-1]) % mod;
                phash2[i] = (1ll * phash2[i-1] * base2 + s[i-1]) % mod;
                pbase1[i] = 1ll * pbase1[i-1] * base1 % mod;
                pbase2[i] = 1ll * pbase2[i-1] * base2 % mod;
        }
}
 
ll get_hash(int l, int r)
{
        ll hash1 = (phash1[r] - phash1[l] * pbase1[r-l] % mod + mod) % mod;
        ll hash2 = (phash2[r] - phash2[l] * pbase2[r-l] % mod + mod) % mod;
        return hash1 * mod + hash2;
}
 
bool good(int l, int r, int k)
{
        return get_hash(l, r-k) == get_hash(l+k, r);
}
 
int main ()
{
        InTheNameOfGod;
        cin >> n >> s >> q;
        sieve();
        partial_hash(s);
        while (q--)
        {
                int l, r; cin >> l >> r; l--;
                int k = r-l;
                for (int i = 0; i < p[r-l].size(); i++)
                {
                        int v = p[r-l][i];
                        while (k % v == 0 && good(l, r, k / v))
                                k /= v;
                }
                cout << k << "\n";
        }
}
Viewed 618 times, submitted by unknown.