Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <stdio.h>
- using namespace std;
- #define F first
- #define S second
- #define lb lower_bound
- #define ub upper_bound
- #define pb push_back
- #define pf push_front
- #define ppb pop_back
- #define mp make_pair
- #define bpp __builtin_popcount
- #define sqr(x) ((x) * (x))
- #define al 0x3F3F3F3F
- #define sz(x) x.size()
- #define all(x) x.begin(), x.end()
- #define in insert
- #define ppf pop_front
- #define endl '\n'
- #define int long long
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- const int mod = (int)1e9 + 7;
- const int N = (int)2e5 + 123;
- const ll inf = 3e18 + 1;
- const double pi = acos(-1.0);
- const double eps = 1e-7;
- const int dx[] = {0, 0, 1, 0, -1};
- const int dy[] = {0, 1, 0, -1, 0};
- string s, t;
- int z[N];
- inline void boost () {
- ios_base :: sync_with_stdio(NULL);
- cin.tie(NULL), cout.tie(NULL);
- }
- inline void Solve () {
- boost ();
- cin >> s >> t;
- int m = sz (t);
- t += t;
- t += s;
- int n = sz (s);
- for (int i = 1, l = 0, r = 0; i < n; i ++) {
- if (i <= r) z[i] = min (r - i + 1, z[i - l]);
- while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i] ++;
- if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
- }
- for (int i = n; i < sz (t); i ++) {
- if (z[i] >= m) {
- cout << i - n, exit (0);
- }
- }
- }
- main () {
- // freopen("headmasters.in", "r", stdin);
- // freopen("headmasters.out", "w", stdout);
- int tt = 1;
- // cin >> tt;
- while (tt --) {
- Solve ();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement