স্ট্রিং ট্রান্সফর্মেশনের ইন-প্লেস অ্যালগরিদম C++-এ

সমস্যা বিবরণ

একটি স্ট্রিং দেওয়া আছে। স্ট্রিং-এর সব ইভেন পজিশনের এলিমেন্টগুলো শেষে নিয়ে যেতে হবে। এলিমেন্ট সরানোর সময় ইভেন ও ওড পজিশনের রিলেটিভ অর্ডার অক্ষুণ্ণ রাখতে হবে।

উদাহরণ: "a1b2c3d4e5f6g7h8i9j1k2l3m4" → "abcdefghijklm1234567891234" (ইন-প্লেস, O(n) টাইম)।

ধাপসমূহ

1. সর্বোচ্চ প্রিফিক্স সাব-স্ট্রিং কাটা হয় যেটির আকার 3^k + 1 রূপে। অর্থাৎ সর্বোচ্চ non-negative integer k খুঁজে বের করুন যাতে 3^k+1 ≤ n (স্ট্রিং দৈর্ঘ্য)।
2. সাইকেল লিডার ইটারেশন অ্যালগরিদম প্রয়োগ করুন (নিচে ব্যাখ্যা করা আছে), ইনডেক্স ১, ৩, ৯... থেকে শুরু করে সাব-স্ট্রিং-এ। এটি সাব-স্ট্রিং-এর এলিমেন্টগুলো তাদের সঠিক পজিশনে নিয়ে যায় (অ্যালফাবেট বামে, ডিজিট ডানে)।
3. বাকি সাব-স্ট্রিং-এ রিকার্সিভলি ধাপ ১ ও ২ প্রয়োগ করুন।
4. প্রসেস করা সাব-স্ট্রিংগুলো জড়িয়ে দিন:
   • প্রথম সাব-স্ট্রিং-এর দ্বিতীয় অর্ধেক রিভার্স করুন।
   • দ্বিতীয় সাব-স্ট্রিং-এর প্রথম অর্ধেক রিভার্স করুন।
   • উভয় রিভার্স করা অংশ একসাথে রিভার্স করুন।
5. সব সাব-স্ট্রিং জড়িয়ে যাওয়া পর্যন্ত ধাপ ৪ রিপিট করুন (k-way merging-এর মতো)।

C++ কোড উদাহরণ

// C++ implementation of above approach 
#include <bits/stdc++.h> 
using namespace std; 

void swap(char* a1, char* b1) { 
    char t = *a1; *a1 = *b1; *b1 = t; 
} 

void reverse(char* str1, int low1, int high1) { 
    while (low1 < high1) { 
        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); 
    } 
} 

void moveNumberToSecondHalf(char* str1) { 
    int k, lenFirst1; 
    int lenRemaining1 = strlen(str1); 
    int shift1 = 0; 
    while (lenRemaining1) { 
        k = 0; 
        while (pow(3, k) + 1 <= lenRemaining1) k++; 
        lenFirst1 = pow(3, k - 1) + 1; 
        lenRemaining1 -= lenFirst1; 
        cycleLeader(str1, shift1, lenFirst1); 
        reverse(str1, shift1/2, shift1 - 1); 
        reverse(str1, shift1, shift1 + lenFirst1/2 - 1); 
        reverse(str1, shift1/2, shift1 + lenFirst1/2 - 1); 
        shift1 += lenFirst1; 
    } 
} 

int main() { 
    char str1[] = "a1b2c3d4e5f6g7"; 
    moveNumberToSecondHalf(str1); 
    cout << str1; 
    return 0; 
}

আউটপুট

abcdefg1234567