6

Algo : Lexicographically minimul string rotationBy                     |
       Zhou Yuan                                                       |
Complexity : O(n)                                                  |          void matchPattern(string text, string pattern) {

int minExp(string s) {                                             |          		string concate;
	s = s + s;                                                     |                concate = pattern + "$" + text;
	int i = 0, j = 1, k = 0, len = s.size();                       |                int lenText = text.length();
	while (i+k<len && j+k<len) {                                   |                int lenPat = pattern.length();
		if (s[i+k] == s[j+k]) k++;                                 |                VI Z = getZarr(concate);
		else if (s[i+k] < s[j+k]) {                                |                for (int i=0; i<concate.length(); i++) {
			j = j + k + 1;                                         |                	if (Z[i] == lenPat) {
			if (j <= i) j = i + 1;                                 |                    	cout << "Found at " << (i-lenPat-1) << "\n"
			k = 0;                                                 |                    }
		}                                                          |                }
		else {                                                     |          }
			i = i + k + 1;                                         |
			if (i <= j)	i = j + 1;                                 |       >>  Manacher's Algorithm find maximum pallindrome substring
			k = 0;                                                 |           Complexity : O(n)
		}                                                          |
	}                                                              |          string preprocessManacherAlgorithm(string s) {
	return min(i, j);  // staring index of LS string               |          		int len = s.length();
}                      // swap number                              |                if (len == 0)  return "^$";
                                                                   |                string t = "^";
>> Z Algorithm                                                     |                for (int i=0; i<len; i++) {
VI getZarr(string s) {        // Z অ্যারে তৈরি                       |                	t += "#";
 	int k, k1, left, right, len = s.length();                      |                    t += s[i];
 	VI arr;                                                        |                }
 	arr.pb(0);                                                     |                t += "#$";
 	left = right = 0;                                              |                return t;
 	for (k=1; k<len; k++) {                                        |          }
 		if (k > right) {      // যদি বক্স তৈরি না হয়                 |          int manacherAlgorithm(string s) {
 			left = right = k; // তাহলে left ও right                |          		string t = preprocessManacherAlgorithm(s);
                              // একই জায়গা থেকে শুরু হবে           |                int n = t.length();
 			while (right<len && s[right]==s[right-left]) {         |                int P[1000001*2+2] = {0};
 				right++;      // যদি মিল পাওয়া যায়,                 |                int C = 0, R = 0;
 			}                 // তাহলে right index এর মান বাড়বে ।  |                int maxPalCenterID = 1;
 			arr.pb(right-left);                                    |                for (int i=0; i<n-1; i++) {
 			right--;                                               |                	int ii = 2*C - i;
 		}                                                          |                    P[i] = (R > i) ? min(R - i, P[ii]) : 0;
 		else {                                                     |                    while (t[i + 1 + P[i]] == t[i - 1- P[i]])
 			k1 = k-left;                                           |                    	P[i]++;
 			if (arr[k1] <= right-k)                                |                    if (P[i] > P[maxPalCenterID])
 				arr.pb(arr[k1]);                                   |                    	maxPalCenterID = i;
 			else {                                                 |                    if (i + P[i] > R) {
 				left = k;                                          |                    	C = i;
 				while (right < len && s[right] == s[right-left])   |                        R = i + P[i];
 					right++;                                       |                    }
 				arr.pb(right);                                     |                }
 				right--;                                           |                return P[maxPalCenterID];
 			}                                                      |           }
 		}                                                          |
 	}                                                              |
 	return arr;                                                    |
 }                                                                 |