Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <iostream>
- #include <iterator>
- #include <map>
- #include <set>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <stack>
- #include <deque>
- #include <queue>
- #include <climits>
- #define int long long
- #define db double
- #define ff first
- #define ss second
- using namespace std;
- const int MOD = 1e9 + 7;
- // const int INF = LONG_MAX;
- const int INF = INT_MAX;
- const int K = 31;
- int hash_substring(vector<int>& h, vector<int>& k, int l, int r, int n) {
- return (h[r] - h[l]) * k[n - l] % MOD;
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- string s;
- cin >> s;
- vector<int> hash1(s.size());
- vector<int> hash2(s.size());
- vector<int> k(s.size() + 1);
- k[0] = 1;
- for (int i = 1; i < s.size() + 1; i++) {
- k[i] = k[0] * K;
- }
- int h = 0;
- for (int i = 0; i < s.size(); i++) {
- int x = s[i] - 'a' + 1;
- h = (h * K + x) % MOD;
- hash1[i] = h;
- }
- h = 0;
- for (int i = s.size() - 1; i >= 0; i--) {
- int x = s[i] - 'a' + 1;
- h = (h * K + x) % MOD;
- hash2[s.size() - 1 - i] = h;
- }
- int h1 = 0, h2 = 0;
- int l = 0, r = 1;
- h1 = hash_substring(hash1, k, l, r, s.size());
- h2 = hash_substring(hash2, k, s.size() - 1 - r, s.size() - 1 - l, s.size());
- if (h1 == h2) {
- cout << "YES";
- }
- else {
- cout << "NO";
- }
- }
- // a ka + a k^2a + ka + a
- // k^2a + ka + a ka + a a
- // aaa
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement