एक दी गई स्ट्रिंग के लिए, सभी सम स्थित वाले तत्वों को स्ट्रिंग के अंत में स्थानांतरित करें। तत्वों को स्थानांतरित करते समय, सभी सम स्थित और विषम स्थित तत्वों का सापेक्ष क्रम समान रखें।
उदाहरण के लिए, यदि दी गई स्ट्रिंग "a1b2c3d4e5f6g7h8i9j1k2l3m4" है, तो इसे "abcdefghijklm1234567891234" में इन-प्लेस और O(n) समय जटिलता में बदलें।
निम्नलिखित चरण हैं
3^k + 1 रूप के आकार का उच्चतम प्रीफिक्स सब-स्ट्रिंग काटें। इस चरण में, हम उच्चतम गैर-ऋणात्मक पूर्णांक k ढूंढते हैं जैसे कि 3^k+1, n (स्ट्रिंग की लंबाई) से कम या बराबर है
साइकिल लीडर पुनरावृत्ति एल्गोरिदम लागू करें (यह नीचे समझाया गया है), इंडेक्स 1, 3, 9... से शुरू करके इस सब-स्ट्रिंग पर। साइकिल लीडर पुनरावृत्ति एल्गोरिदम इस सब-स्ट्रिंग के सभी आइटम्स को उनकी सही स्थितियों में स्थानांतरित करता है, यानी, सभी वर्णमाला सब-स्ट्रिंग के बाएं आधे हिस्से में चली जाती हैं और सभी अंक इस सब-स्ट्रिंग के दाएं आधे हिस्से में चले जाते हैं।
चरण 1 और 2 को लागू करके शेष सब-स्ट्रिंग को पुनरावर्ती रूप से प्रोसेस करें।
वर्तमान में, हमें केवल प्रोसेस किए गए सब-स्ट्रिंग्स को एक साथ जोड़ने की आवश्यकता है। किसी भी अंत से शुरू करें (मान लें बाएं से), दो सब-स्ट्रिंग्स चुनें और निम्नलिखित चरण लागू करें -
पहले सब-स्ट्रिंग के दूसरे आधे को उल्टा करें।
दूसरे सब-स्ट्रिंग के पहले आधे को उल्टा करें।
पहले सब-स्ट्रिंग के दूसरे आधे और दूसरे सब-स्ट्रिंग के पहले आधे को एक साथ उल्टा करें।
चरण 4 को तब तक दोहराएं जब तक सभी सब-स्ट्रिंग्स जुड़ न जाएं। यह k-वे मर्जिंग के समान है जहां पहला सब-स्ट्रिंग दूसरे के साथ जुड़ता है। परिणाम तीसरे के साथ मर्ज होता है और इसी तरह।
उपरोक्त एल्गोरिदम पर आधारित कोड नीचे दिया गया है -
// उपरोक्त दृष्टिकोण का C++ एप्लिकेशन #include <bits/stdc++.h> using namespace std; // कैरेक्टर्स को स्वैप करने के लिए यूटिलिटी फ़ंक्शन void swap ( char* a1, char* b1 ) { char t = *a1; *a1 = *b1; *b1 = t; } // स्ट्रिंग str1[low1..high1] को उल्टा करने के लिए यूटिलिटी फ़ंक्शन void reverse ( char* str1, int low1, int high1 ) { while ( low < high ) { swap(&str1[low1], &str1[high1] ); ++low1; --high1; } } // सभी सम स्थित वाले तत्वों को अंत में शिफ्ट करने के लिए साइकिल लीडर एल्गोरिदम 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{ // विषम इंडेक्स if ( j & 1 ) j = len1 / 2 + j / 2; // सम इंडेक्स या स्थिति else j /= 2; // नए इंडेक्स या स्थिति पर तत्व का बैकअप रखें swap (&str1[j + shift1], &item1); } while ( j != i ); } } // स्ट्रिंग को बदलने के लिए मुख्य फ़ंक्शन। यह फ़ंक्शन // मुख्य रूप से रूपांतरित करने के लिए cycleLeader() का उपयोग करता है void moveNumberToSecondHalf( char* str1 ) { int k, lenFirst1; int lenRemaining1 = strlen( str1); int shift1 = 0; while ( lenRemaining1) { k = 0; // चरण 1: 3^k + 1 रूप का उच्चतम प्रीफिक्स // सबएरे ढूंढें while ( pow( 3, k ) + 1 <= lenRemaining1) k++; lenFirst1 = pow( 3, k - 1 ) + 1; lenRemaining1 -= lenFirst1; // चरण 2: उच्चतम सबएरे के लिए साइकिल लीडर एल्गोरिदम लागू करें cycleLeader ( str1, shift1, lenFirst1 ); // चरण 4.1: पहले सबएरे के दूसरे आधे को उल्टा करें reverse ( str1, shift1/2, shift1 - 1 ); // चरण 4.2: दूसरे सब-स्ट्रिंग के पहले आधे को उल्टा करें। reverse ( str1, shift1, shift1 + lenFirst1 / 2 - 1 ); // चरण 4.3 पहले सब-स्ट्रिंग के दूसरे आधे और दूसरे सब-स्ट्रिंग के पहले आधे को एक साथ उल्टा करें reverse ( str1, shift1 / 2, shift1 + lenFirst1 / 2 - 1 ); // अब पहले सबएरे की लंबाई बढ़ाएं Shift1 += lenFirst1; } } // उपरोक्त फ़ंक्शन को टेस्ट/सत्यापित करने के लिए ड्राइवर प्रोग्राम int main() { char str1[] = "a1b2c3d4e5f6g7"; moveNumberToSecondHalf( str1 ); cout<<str1; return 0; }आउटपुट
abcdefg1234567