String/Hash/test_hash2.cpp

• View this file on GitHub
• Last update: 2025-05-30 22:12:29+07:00
• Link: https://oj.vnoi.info/problem/paliny

Depends on

• String/Hash/Rolling_Hash.h
• template.h

Code

#include "../../template.h"
#include "Rolling_Hash.h"

/* AC: https://oj.vnoi.info/problem/paliny */

bool check_even(Hash<int> &h1, Hash<int> &h2, int n, int len) {
    int half = len/2;
    for (int i = 1; i <= n-len+1; i++) {
        int l1 = i, r1 = l1 + half - 1;
        int l2 = n - (r1 + half) + 1, r2 = l2 + half - 1;
        if (h1.getHash(l1, r1) == h2.getHash(l2, r2)) {
            return true;
        }
    }
    return false;
}

int binEven(Hash<int> &h1, Hash<int> &h2, int n) {
    int l = 1, r = n/2;
    int res = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check_even(h1, h2, n, 2*mid)) {
            res = 2*mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }   
    return res;
}

bool check_odd(Hash<int> &h1, Hash<int> &h2, int n, int len) {
    int half = len/2;
    for (int i = 1; i <= n-len+1; i++) {
        int l1 = i, r1 = l1 + half - 1;
        int l2 = n - (r1 + half + 1) + 1, r2 = l2 + half - 1;
        if (h1.getHash(l1, r1) == h2.getHash(l2, r2)) {
            return true;
        }
    }
    return false;
}

int binOdd(Hash<int> &h1, Hash<int> &h2, int n) {
    int l = 1, r = (n-1)/2;
    int res = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check_odd(h1, h2, n, 2*mid+1)) {
            res = 2*mid + 1;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }   
    return res;
}

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    string x = s;
    reverse(all(x));
    Hash<int> h1(s), h2(x);
    int ans = max(binEven(h1, h2, n), binOdd(h1, h2, n));
    cout << ans;
}

#line 2 "template.h"

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MOD (ll)(1e9+7)
#define all(x) (x).begin(),(x).end()
#define unique(x) x.erase(unique(all(x)), x.end())
#define INF32 ((1ull<<31)-1)
#define INF64 ((1ull<<63)-1)
#define inf (ll)1e18

#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int mod = 998244353;

void solve();

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // cin.exceptions(cin.failbit);
    // int t; cin >> t;
    // while(t--)
        solve();
    cerr << "\nTime run: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << '\n';
    return 0;
}
#line 2 "String/Hash/Rolling_Hash.h"

template <typename T>
class Hash {
public:
    static constexpr int base = 331;
    static constexpr int mod = 1'000'000'007;
    vector<T> h, p;

    Hash() {}

    Hash(const string &s) {
        build(s);
    }

    void build(const string &s) {
        int n = s.size();
        h = hashStr(s, n);
        p = calc_pow(n);
    }

    T getHash(int l, int r) const {
        T x = (h[r] - 1ll * h[l-1] * p[r-l+1]) % mod;
        return T((x + mod) % mod);
    }

private:
    vector<T> hashStr(const string &s, int n) {
        vector<T> hash(n + 1);
        for (int i = 1; i <= n; i++) {
            int c = s[i - 1] - 'a' + 1;
            hash[i] = (1ll * hash[i-1] * base + c) % mod;
        }
        return hash;
    }

    vector<T> calc_pow(int n) {
        vector<T> P;
        P.emplace_back(1);
        for (int i = 1; i <= n; i++) {
            P.emplace_back((1ll * P[i-1] * base) % mod);
        }
        return P;
    }
};
#line 3 "String/Hash/test_hash2.cpp"

/* AC: https://oj.vnoi.info/problem/paliny */

bool check_even(Hash<int> &h1, Hash<int> &h2, int n, int len) {
    int half = len/2;
    for (int i = 1; i <= n-len+1; i++) {
        int l1 = i, r1 = l1 + half - 1;
        int l2 = n - (r1 + half) + 1, r2 = l2 + half - 1;
        if (h1.getHash(l1, r1) == h2.getHash(l2, r2)) {
            return true;
        }
    }
    return false;
}

int binEven(Hash<int> &h1, Hash<int> &h2, int n) {
    int l = 1, r = n/2;
    int res = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check_even(h1, h2, n, 2*mid)) {
            res = 2*mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }   
    return res;
}

bool check_odd(Hash<int> &h1, Hash<int> &h2, int n, int len) {
    int half = len/2;
    for (int i = 1; i <= n-len+1; i++) {
        int l1 = i, r1 = l1 + half - 1;
        int l2 = n - (r1 + half + 1) + 1, r2 = l2 + half - 1;
        if (h1.getHash(l1, r1) == h2.getHash(l2, r2)) {
            return true;
        }
    }
    return false;
}

int binOdd(Hash<int> &h1, Hash<int> &h2, int n) {
    int l = 1, r = (n-1)/2;
    int res = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check_odd(h1, h2, n, 2*mid+1)) {
            res = 2*mid + 1;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }   
    return res;
}

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    string x = s;
    reverse(all(x));
    Hash<int> h1(s), h2(x);
    int ans = max(binEven(h1, h2, n), binOdd(h1, h2, n));
    cout << ans;
}

Back to top page