SHARE
TWEET

String Transformation

Serega Oct 16th, 2011 410 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. using namespace std;
  5. string a, b, s1, s2;
  6. int main()
  7. {
  8.         getline(cin, a);
  9.         getline(cin, b);
  10.         if (a.length() != b.length())
  11.         {
  12.                 cout << "-1 -1";
  13.                 return 0;
  14.         }
  15.         int n = a.length();
  16.         s1 = a; reverse(s1.begin(),s1.end()); s1 += '\0' + b;
  17.         s2 = b + '\0' + a;
  18.         int *p = new int[2 * n + 1];
  19.         p[0] = 0;
  20.         for (int i = 1; i < 2 * n + 1; ++i)
  21.         {
  22.                 p[i] = p[i - 1];
  23.                 while (p[i] > 0 && s1[p[i]] != s1[i])
  24.                         p[i] = p[p[i] - 1];
  25.                 if (s1[p[i]] == s1[i])
  26.                         ++p[i];
  27.         }
  28.         int *z = new int[2 * n + 1];
  29.         z[0] = 0;
  30.         for (int i = 1, l = 0, r = 0; i < 2 * n + 1; ++i)
  31.         {
  32.                 z[i] = 0;
  33.                 if (i <= r)
  34.                         z[i] = min(z[i - l], r - i + 1);
  35.                 while (i + z[i] < 2 * n + 1 && s2[z[i]] == s2[i + z[i]])
  36.                         ++z[i];
  37.                 if (i + z[i] - 1 > r)
  38.                 {
  39.                         l = i;
  40.                         r = i + z[i] - 1;
  41.                 }
  42.         }
  43.         int ans_i = -1, ans_j = -1;
  44.         for (int i = 0; i < n - 1; ++i)
  45.         {
  46.                 if (a[i] != b[n - i - 1]) break;
  47.                 int len = p[2 * n - i - 1];
  48.                 if (z[n + i + 2] >= n - i - len - 1)
  49.                 {
  50.                         ans_i = i;
  51.                         ans_j = n - len;
  52.                 }
  53.         }
  54.         cout << ans_i << ' ' << ans_j << endl;
  55.         return 0;
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top