Advertisement
Guest User

Untitled

a guest
May 21st, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3.  
  4. using namespace std;
  5.  
  6. #define F first
  7. #define S second
  8. #define lb lower_bound
  9. #define ub upper_bound
  10. #define pb push_back
  11. #define pf push_front
  12. #define ppb pop_back
  13. #define mp make_pair
  14. #define bpp __builtin_popcount
  15. #define sqr(x) ((x) * (x))
  16. #define al 0x3F3F3F3F
  17. #define sz(x) x.size()
  18. #define all(x) x.begin(), x.end()
  19. #define in insert
  20. #define ppf pop_front
  21. #define endl '\n'
  22. #define int long long
  23.  
  24. typedef unsigned long long ull;
  25. typedef long long ll;
  26. typedef long double ld;
  27. typedef pair <int, int> pii;
  28.  
  29. const int mod = (int)1e9 + 7;
  30. const int N = (int)2e5 + 123;
  31. const ll inf = 3e18 + 1;
  32.  
  33. const double pi = acos(-1.0);
  34. const double eps = 1e-7;
  35. const int dx[] = {0, 0, 1, 0, -1};
  36. const int dy[] = {0, 1, 0, -1, 0};
  37.  
  38. string s, t;
  39. int z[N];
  40.  
  41. inline void boost () {
  42. ios_base :: sync_with_stdio(NULL);
  43. cin.tie(NULL), cout.tie(NULL);
  44. }
  45.  
  46.  
  47. inline void Solve () {
  48. boost ();
  49. cin >> s >> t;
  50. int m = sz (t);
  51. t += t;
  52. t += s;
  53. int n = sz (s);
  54. for (int i = 1, l = 0, r = 0; i < n; i ++) {
  55. if (i <= r) z[i] = min (r - i + 1, z[i - l]);
  56. while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i] ++;
  57. if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  58. }
  59. for (int i = n; i < sz (t); i ++) {
  60. if (z[i] >= m) {
  61. cout << i - n, exit (0);
  62. }
  63. }
  64. }
  65.  
  66. main () {
  67. // freopen("headmasters.in", "r", stdin);
  68. // freopen("headmasters.out", "w", stdout);
  69. int tt = 1;
  70. // cin >> tt;
  71. while (tt --) {
  72. Solve ();
  73. }
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement