একটি প্রদত্ত স্ট্রিং এর জন্য, স্ট্রিং এর শেষে সমস্ত এমনকি অবস্থান করা উপাদান স্থানান্তর করুন। উপাদান স্থানান্তর করার সময়, সমস্ত জোড় অবস্থান এবং বিজোড় অবস্থানের উপাদানগুলির আপেক্ষিক ক্রম একই রাখুন৷
উদাহরণস্বরূপ, যদি প্রদত্ত স্ট্রিংটি "a1b2c3d4e5f6g7h8i9j1k2l3m4" হয়, তাহলে এটিকে "abcdefghijklm1234567891234"-এ এবং O(n) সময়ের জটিলতায় রূপান্তর করুন৷
নিম্নলিখিত ধাপগুলি
-
3^k + 1 ফর্মের আকারের সর্বোচ্চ উপসর্গ সাব-স্ট্রিংটি কেটে ফেলুন। এই ধাপে, আমরা সর্বোচ্চ অ-ঋণাত্মক পূর্ণসংখ্যা k সনাক্ত করি যাতে 3^k+1 n এর থেকে কম বা সমান (স্ট্রিংয়ের দৈর্ঘ্য) )
-
এই সাব-স্ট্রিং-এ সূচক 1, 3, 9…… দিয়ে শুরু করে চক্র লিডার পুনরাবৃত্তি অ্যালগরিদম (এটি নীচে ব্যাখ্যা করা হয়েছে) প্রয়োগ করুন। সাইকেল লিডার পুনরাবৃত্তি অ্যালগরিদম এই সাব-স্ট্রিং-এর সমস্ত আইটেমকে তাদের সঠিক অবস্থানে স্থানান্তরিত করে, অর্থাৎ, সমস্ত বর্ণমালা সাব-স্ট্রিং-এর বাম অর্ধেক এবং সমস্ত অঙ্ক এই সাব-স্ট্রিং-এর ডান অর্ধেকে সরানো হয়। .
-
অবশিষ্ট সাব-স্ট্রিংটি পুনরাবৃত্তিমূলকভাবে পদক্ষেপ নং বাস্তবায়ন করে প্রক্রিয়া করুন। 1 এবং ন. 2.
-
বর্তমানে, আমাদের শুধুমাত্র প্রক্রিয়াকৃত সাব-স্ট্রিংগুলিকে একসাথে যোগদান করতে হবে। যেকোনো প্রান্ত থেকে শুরু করুন (বাম থেকে বলুন), দুটি উপ-স্ট্রিং নির্বাচন করুন এবং নিম্নলিখিত পদক্ষেপগুলি বাস্তবায়ন করুন −
-
প্রথম সাব-স্ট্রিং-এর দ্বিতীয়ার্ধের ঠিক বিপরীত বা বিপরীত।
-
দ্বিতীয় সাব-স্ট্রিং-এর প্রথমার্ধের ঠিক বিপরীত বা বিপরীত।
-
প্রথম সাব-স্ট্রিং-এর দ্বিতীয়ার্ধ এবং দ্বিতীয় সাব-স্ট্রিং-এর প্রথমার্ধের ঠিক বিপরীত বা বিপরীত।
-
-
ধাপ নং পুনরাবৃত্তি করুন. 4 যতক্ষণ না সব সাব-স্ট্রিং যুক্ত না হয়। এটি k-ওয়ে মার্জিংয়ের মতো যেখানে প্রথম সাব-স্ট্রিং দ্বিতীয়টির সাথে যুক্ত হয়। ফলাফল তৃতীয় এবং এর সাথে একত্রিত হয়।
উপরের অ্যালগরিদম -
এর উপর ভিত্তি করে কোডটি নীচে দেওয়া হয়েছে// C++ application of above approach
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap characters void swap ( char* a1, char* b1 ) {
char t = *a1; *a1 = *b1; *b1 = t;
}
// A utility function to reverse string str1[low1..high1]
void reverse ( char* str1, int low1, int high1 ) {
while ( low < high ) {
swap(&str1[low1], &str1[high1] ); ++low1; --high1;
}
}
// Cycle leader algorithm to shift all even
// positioned elements at the end.
void cycleLeader ( char* str1, int shift1, int len1 ) {
int j;
char item1;
for (int i = 1; i < len1; i *= 3 ) {
j = i; item1 = str1[j + shift1];
do{
// odd index if ( j & 1 )
j = len1 / 2 + j / 2;
// even index or position else j /= 2;
// keep the back-up of element at new index or position
swap (&str1[j + shift1], &item1);
}
while ( j != i );
}
}
// The main function to convert a string. This function
// mainly implements cycleLeader() to convert void moveNumberToSecondHalf( char* str1 ) {
int k, lenFirst1; int lenRemaining1 = strlen( str1); int shift1 = 0;
while ( lenRemaining1) {
k = 0;
// Step 1: Find the highest prefix
// subarray of the form 3^k + 1
while ( pow( 3, k ) + 1 <= lenRemaining1)
k++; lenFirst1 = pow( 3, k - 1 ) + 1;
lenRemaining1 -= lenFirst1;
// Step 2: Implement cycle leader algorithm
// for the highest subarray cycleLeader ( str1, shift1, lenFirst1 );
// Step 4.1: Just opposite or reverse the second half of first subarray reverse ( str1,
shift1/2, shift1 - 1 );
// Step 4.2: Just opposite or reverse the first half of second sub-string. reverse ( str1,
shift1, shift1 + lenFirst1 / 2 - 1 );
// Step 4.3 Just opposite or reverse the second half of first sub-string and first half of
second sub-string together reverse ( str1, shift1 / 2, shift1 + lenFirst1 / 2 - 1 );
// Now increase the length of first subarray Shift1 += lenFirst1;
}
}
// Driver program to verify or test above function int main() {
char str1[] = "a1b2c3d4e5f6g7"; moveNumberToSecondHalf( str1 ); cout<<str1; return 0;
} আউটপুট
abcdefg1234567
