Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int p = 239;
- vector<unsigned long long> p_pow;
- void getP(int n) {
- p_pow.push_back(1);
- for (int i = 0; i < n; ++i) {
- p_pow.push_back(p_pow[i] * p);
- }
- }
- void hasher(string s, vector<unsigned long long> & hash) {
- hash.push_back(0);
- for (int i = 0; i < s.size(); ++i) {
- hash.push_back(hash[i] * p + s[i]);
- }
- }
- void suf_hasher(string s, vector<unsigned long long> & hash) {
- reverse(s.begin(), s.end());
- hash.push_back(0);
- for (int i = 0; i < s.size(); ++i) {
- hash.push_back(hash[i] * p + s[i]);
- }
- }
- int main() {
- getP(50000);
- string s1, s2;
- cin >> s1 >> s2;
- vector<unsigned long long> hash1, hash2, suf_hash1;
- hasher(s1, hash1);
- suf_hasher(s1, suf_hash1);
- hasher(s2, hash2);
- unsigned long long match = hash2[s2.size()] - hash2[0] * p_pow[s2.size()];
- int ans = -1;
- for (int i = 0; i < s1.size(); ++i) {
- unsigned long long h1 = hash1[s1.size()] - hash1[i] * p_pow[s1.size() - i];
- h1 *= p_pow[i];
- unsigned long long h2 = suf_hash1[s1.size()] - suf_hash1[s1.size() - i] * p_pow[i];
- if (h1 + h2 == match) {
- ans = s1.size() - i;
- break;
- }
- }
- if (ans == -1) {
- printf("No");
- return 0;
- }
- printf("Yes\n");
- printf("%d", s1.size() - ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement