Madiyar

Untitled

Jan 29th, 2013
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <ctime>
  11. #include <cassert>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. #define f first
  17. #define s second
  18. #define mp make_pair
  19. #define pb push_back
  20. #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
  21. #define f0(a) memset(a, 0, sizeof(a))
  22. #define all(v) v.begin(), v.end()
  23. #define pii pair<int,int>
  24. #define vi vector<int>
  25. #define ll long long
  26.  
  27. #ifdef WIN32
  28.     #define I64 "%I64d"
  29. #else
  30.     #define I64 "%lld"
  31. #endif
  32. const ll base = 31;
  33. const ll base1 = 57;
  34. const int maxn = (int)1e6;
  35. const ll mod1 = (int)1e9 + 7;
  36. const ll inf = 9223372036854775807ll;
  37. vector<int> s, t;
  38.  
  39. ll mhash[maxn], Pow[maxn], mhashr[maxn];
  40. ll mhash1[maxn], Pow1[maxn], mhashr1[maxn];
  41. char ss[maxn];
  42. map<pair<ll, ll>, int> Map;
  43.  
  44. pair<ll, ll> mHash(int l, int r) {
  45.     if (l > r) return mp(0, 0);
  46.    
  47.     ll hsh = mhash[r];
  48.     if (l > 0) hsh -= Pow[r - l + 1] * mhash[l - 1];
  49.  
  50.     ll hsh1 = mhash1[r];
  51.     if (l > 0) {
  52.         hsh1 -= (Pow1[r - l + 1] * mhash1[l - 1]) % mod1;
  53.         hsh1 = (hsh1 + mod1) % mod1;
  54.     }
  55.     return mp(hsh, hsh1);
  56. }
  57.  
  58. pair<ll, ll> mHashr(int l, int r) {
  59.     if (l > r) return mp(0, 0);
  60.  
  61.     ll hsh = mhashr[r];
  62.     if (l > 0) hsh -= Pow[r - l + 1] * mhashr[l - 1];
  63.  
  64.     ll hsh1 = mhashr1[r];
  65.     if (l > 0) {
  66.         hsh1 -= (Pow1[r - l + 1] * mhashr1[l - 1]) % mod1;
  67.         hsh1 = (hsh1 + mod1) % mod1;
  68.        
  69.     }
  70.     return mp(hsh, hsh1);
  71. }
  72.  
  73.  
  74. ll modPow(ll a, ll n, ll mod = -1) {
  75.     ll res = 1;
  76.     while (n > 0) {
  77.         if (n & 1) {
  78.             res = res * a;      
  79.             if (mod != -1) res %= mod;
  80.         }
  81.         a = a * a;
  82.         if (mod != -1) a %= mod;
  83.         n >>= 1;
  84.     }
  85.     return res;
  86. }
  87.  
  88.  
  89. void First() {     
  90.  
  91.     int mx = max(s.size() * 3, t.size() * 3);
  92.  
  93.     Pow[0] = Pow1[0] = 1;
  94.    
  95.     for (int i = 1; i <= mx + 1; ++i) {
  96.         Pow[i] = Pow[i - 1] * base;
  97.         Pow1[i] = (Pow1[i - 1] * base1) % mod1;
  98.     }
  99.    
  100.     ll hsh = 0, hsh1 = 0;
  101.     for (int i = 0; i < s.size(); ++i) {
  102.         hsh = hsh * base + s[i];       
  103.         hsh1 = (hsh1 * base1 + s[i]) % mod1;
  104.     }
  105.  
  106.     Map[mp(hsh, hsh1)] = 0;
  107.     int n = s.size();
  108.  
  109.     for (int i = 1; i < n; ++i) {
  110.         hsh -= s[i - 1] * Pow[n - 1];
  111.         hsh = hsh * base + s[i - 1];
  112.  
  113.         hsh1 = (hsh1 - (s[i - 1] * Pow1[n - 1]) % mod1 + mod1) % mod1;
  114.         hsh1 = (hsh1 * base1 + s[i - 1]) % mod1;
  115.         Map[mp(hsh, hsh1)] = i;
  116.     }
  117.  
  118.     int m = t.size();
  119.     for (int i = 0; i < m; ++i)
  120.         t.pb(t[i]);
  121.     m += m;
  122.     hsh = hsh1 = 0;
  123.     for (int i = 0; i < m; ++i) {
  124.         hsh = hsh * base + t[i];
  125.         mhash[i] = hsh;
  126.        
  127.         hsh1 = (hsh1 * base1 + t[i]) % mod1;
  128.         mhash1[i] = hsh1;
  129.     }
  130.    
  131.     reverse(all(t));
  132.     hsh = hsh1 = 0;
  133.    
  134.     for (int i = 0; i < m; ++i) {
  135.         hsh = hsh * base + t[i];
  136.         mhashr[i] = hsh;
  137.        
  138.         hsh1 = (hsh1 * base1 + t[i]) % mod1;
  139.         mhashr1[i] = hsh1;
  140.     }
  141.    
  142.     for (int i = 0; i < m / 2; ++i) {
  143.         pair<ll, ll> hsh = mHashr(m - 1 - (i + n - 1), m - 1 - i);
  144.  
  145.         if (Map.count(hsh)) {
  146.             int j = i + n, k = m / 2 - n + j - 1;
  147.             if (mHash(j, k) == mHashr(m - 1 - k, m - 1 - j)) {
  148.                 puts("Yes");
  149.        
  150.                 cout << Map[hsh] + 1 << " " << j % (m / 2) + 1 << endl;
  151.                 return;
  152.             }
  153.         }
  154.     }
  155.     puts("No");
  156.  
  157.  
  158. }
  159.  
  160. void Second() {
  161.  
  162.     swap(s, t);
  163.     int mx = max(s.size() * 3, t.size() * 3);
  164.  
  165.     Pow[0] = 1;
  166.     Pow1[0] = 1;
  167.     for (int i = 1; i <= mx + 1; ++i) {
  168.         Pow[i] = Pow[i - 1] * base;    
  169.         Pow1[i] = (Pow1[i - 1] * base1) % mod1;
  170.     }
  171.  
  172.     ll hsh = 0;
  173.     ll hsh1 = 0;
  174.    
  175.     for (int i = (int)s.size() - 1; i >= 0; --i) {
  176.         hsh = hsh * base + s[i];       
  177.         hsh1 = (hsh1 * base1 + s[i]) % mod1;
  178.     }
  179.    
  180.     Map[mp(hsh, hsh1)] = 0;
  181.     int n = s.size();
  182.  
  183.     for (int i = 1; i < n; ++i) {
  184.         hsh = (hsh - s[i - 1]) * modPow(base, inf);
  185.         hsh = hsh + Pow[n - 1] * s[i - 1];
  186.    
  187.         hsh1 = ((hsh1 - s[i - 1] + mod1) % mod1 * modPow(base1, mod1 - 2, mod1)) % mod1;
  188.         hsh1 = (hsh1 + (Pow1[n - 1] * s[i - 1]) % mod1) % mod1;
  189.    
  190.         Map[mp(hsh, hsh1)] = i;
  191.     }
  192.  
  193.     int m = t.size();
  194.     for (int i = 0; i < m; ++i)
  195.         t.pb(t[i]);
  196.  
  197.     m += m;
  198.     hsh = hsh1 = 0;
  199.     for (int i = 0; i < m; ++i) {
  200.         hsh = hsh * base + t[i];
  201.         hsh1 = (hsh1 * base1 + t[i]) % mod1;
  202.        
  203.         mhash[i] = hsh;
  204.         mhash1[i] = hsh1;
  205.     }
  206.    
  207.     reverse(all(t));
  208.     hsh = hsh1 = 0;
  209.     for (int i = 0; i < m; ++i) {
  210.         hsh = hsh * base + t[i];
  211.         mhashr[i] = hsh;
  212.        
  213.         hsh1 = (hsh1 * base1 + t[i]) % mod1;
  214.         mhashr1[i] = hsh1;
  215.     }
  216.    
  217.     for (int i = 0; i < m / 2; ++i) {
  218.         pair<ll, ll> hsh = mHash(i, i + n - 1);
  219.  
  220.         if (Map.count(hsh)) {
  221.             int j = i + n, k = m / 2 - n + j - 1;
  222.             if (mHash(j, k) == mHashr(m - 1 - k, m - 1 - j)) {
  223.                 puts("Yes");
  224.                 cout << i + 1<< " " << Map[hsh] + 1 << endl;   
  225.                 return;
  226.             }
  227.         }
  228.     }
  229.     puts("No");
  230. }
  231. int main() {
  232.     #ifdef LOCAL
  233.         freopen("in","r",stdin);
  234.         freopen("out","w",stdout);
  235.     #endif  
  236.  
  237.     gets(ss);
  238.     for (int i = 0; ss[i]; ++i)
  239.         s.pb(ss[i] - 'a' + 1);
  240.  
  241.     gets(ss);
  242.  
  243.     for (int i = 0; ss[i]; ++i)
  244.         t.pb(ss[i] - 'a' + 1);
  245.     if (s.size() <= t.size()) First(); else
  246.     Second();
  247.     return 0;
  248. }
Advertisement
Add Comment
Please, Sign In to add comment