text: /*--------------------------"SABUJ-JANA"------"JADAVPUR UNIVERSITY"--------*/
  /*-------------------------------@greenindia-----------------------------------*/
  //
  //		  _____       _           _        _
  //		 / ____|     | |         (_)      | |
  //		| (___   __ _| |__  _   _ _       | | __ _ _ __   __ _
  //		 \___ \ / _` | '_ \| | | | |  _   | |/ _` | '_ \ / _` |
  //		 ____) | (_| | |_) | |_| | | | |__| | (_| | | | | (_| |
  //		|_____/ \__,_|_.__/ \__,_| |  \____/ \__,_|_| |_|\__,_|
  //		                        _/ |
  //		                       |__/
  /*---------------------- Magic. Do not touch.-----------------------------*/
  /*------------------------------God is Great/\---------------------------------*/
  #include <bits/stdc++.h>
  using namespace std;
  #define crap ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  //cout<<fixed<<showpoint<<setprecision(12)<<ans<<endl;
  #define int long long int
  #define double long double
  #define PI acos(-1)
  
  void print1d(const vector<int>& vec) {for (auto val : vec) {cout << val << " ";} cout << endl;}
  
  void print2d(const vector<vector<int>>& vec) {for (auto row : vec) {for (auto val : row) {cout << val << " ";} cout << endl;}}
  
  vector<int> ZF(string str) {
  	int n = (int) str.length();
  	vector<int> z(n);
  	int l = 0, r = 0;
  
  	for (int i = 1; i < n; ++i) {
  		if (i <= r)
  			z[i] = min (r - i + 1, z[i - l]);
  		while (i + z[i] < n && str[z[i]] == str[i + z[i]])
  			++z[i];
  		if (i + z[i] - 1 > r)
  			l = i, r = i + z[i] - 1;
  	}
  	return z;
  }
  
  void ZAlgo(string str, string pat){
  	string dummy = pat + '$' + str;
  	vector<int> Z = ZF(dummy);
  
  	int n = dummy.length();
  	int x = pat.length();
  	
  	for(int i=0; i<n; i++){
  		if(Z[i] == x)
  			cout << "Pattern found at position " << i - x  - 1 << endl;
  	}
  }
  
  signed main() {
  #ifndef ONLINE_JUDGE
  	freopen("input.txt", "r", stdin);
  	freopen("error.txt", "w", stderr);
  #endif
  	crap;
  
  	string str = "sabujxxabujxxabuj";
  	string pat = "abuj";
  
  	ZAlgo(str, pat);
  
  
  	return 0;
  }
  
  
  
  
  