किसी दिए गए स्ट्रिंग के लिए, सभी समान स्थिति वाले तत्वों को स्ट्रिंग के अंत में स्थानांतरित करें। तत्वों को स्थानांतरित करते समय, सभी सम स्थिति और विषम स्थिति वाले तत्वों का सापेक्ष क्रम समान रखें।
उदाहरण के लिए, यदि दी गई स्ट्रिंग "a1b2c3d4e5f6g7h8i9j1k2l3m4" है, तो इसे "abcdefghijklm1234567891234" में इन-प्लेस और O(n) समय जटिलता में रूपांतरित करें।
निम्न चरण हैं
-
फॉर्म 3^k + 1 के आकार के उच्चतम उपसर्ग उप-स्ट्रिंग को काटें। इस चरण में, हम उच्चतम गैर-ऋणात्मक पूर्णांक k का पता लगाते हैं जैसे कि 3^k+1 n से कम या बराबर है (स्ट्रिंग की लंबाई )
-
इस उप-स्ट्रिंग के सूचकांक 1, 3, 9…… से शुरू होकर चक्र नेता पुनरावृत्ति एल्गोरिथ्म (इसे नीचे समझाया गया है) को लागू करें। साइकिल लीडर इटरेशन एल्गोरिथम इस सब-स्ट्रिंग के सभी आइटम्स को उनकी सही स्थिति में स्थानांतरित करता है, अर्थात, सभी अक्षर सब-स्ट्रिंग के बाएं आधे हिस्से में ले जाया जाता है और सभी अंकों को इस सब-स्ट्रिंग के दाहिने आधे हिस्से में ले जाया जाता है। ।
-
शेष उप-स्ट्रिंग को पुनरावर्ती रूप से लागू करने वाले चरण संख्या को संसाधित करें। 1 और नहीं। 2.
-
वर्तमान में, हमें केवल संसाधित उप-स्ट्रिंग को एक साथ जोड़ने की आवश्यकता है। किसी भी छोर से शुरू करें (बाएं से कहें), दो उप-स्ट्रिंग का चयन करें और निम्नलिखित चरणों को लागू करें -
-
पहले उप-स्ट्रिंग के दूसरे भाग के ठीक विपरीत या उल्टा।
-
दूसरे उप-स्ट्रिंग के पहले भाग के ठीक विपरीत या उल्टा।
-
पहले उप-स्ट्रिंग के दूसरे भाग और दूसरे उप-स्ट्रिंग के पहले भाग के ठीक विपरीत या उल्टा करें।
-
-
चरण संख्या दोहराएं। 4 जब तक और जब तक सभी उप-स्ट्रिंग शामिल नहीं हो जाते। यह के-वे मर्जिंग के समान है जहां पहले उप-स्ट्रिंग को दूसरे के साथ जोड़ा जाता है। परिणामी को तीसरे वगैरह में मिला दिया जाता है।
उपरोक्त एल्गोरिथम के आधार पर कोड नीचे दिया गया है -
// 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