주어진 문자열에 대해 짝수 위치에 있는 모든 요소를 문자열의 끝으로 전송합니다. 요소를 전송하는 동안 모든 짝수 위치 및 홀수 위치 요소의 상대적 순서를 동일하게 유지하십시오.
예를 들어 주어진 문자열이 "a1b2c3d4e5f6g7h8i9j1k2l3m4"인 경우 O(n) 시간 복잡도에서 제자리에서 "abcdefghijklm1234567891234"로 변환합니다.
다음 단계
-
3^k + 1 형식의 가장 높은 접두사 부분 문자열을 잘라냅니다. 이 단계에서는 3^k+1이 n(문자열 길이 )
-
이 하위 문자열에 대해 인덱스 1, 3, 9……부터 시작하여 사이클 리더 반복 알고리즘(아래에 설명되어 있음)을 구현합니다. 사이클 리더 반복 알고리즘은 이 하위 문자열의 모든 항목을 올바른 위치로 전송합니다. 즉, 모든 알파벳은 하위 문자열의 왼쪽 절반으로 이동하고 모든 숫자는 이 하위 문자열의 오른쪽 절반으로 이동합니다. .
-
단계 번호를 재귀적으로 구현하는 나머지 하위 문자열을 처리합니다. 1과 아니요. 2.
-
현재로서는 처리된 하위 문자열을 함께 결합하기만 하면 됩니다. 끝에서 시작(예:왼쪽부터), 두 개의 하위 문자열을 선택하고 다음 단계를 구현하십시오. −
-
첫 번째 부분 문자열의 후반부와 반대 방향 또는 반대 방향입니다.
-
두 번째 하위 문자열의 전반부를 반대하거나 반대로 합니다.
-
첫 번째 하위 문자열의 후반부와 두 번째 하위 문자열의 전반부를 함께 반대하거나 반대로 합니다.
-
-
단계 번호를 반복합니다. 4 모든 하위 문자열이 결합될 때까지 및 제외됩니다. 첫 번째 하위 문자열이 두 번째 하위 문자열과 결합되는 k-way 병합과 동일합니다. 결과는 세 번째 등과 병합됩니다.
코드는 위의 알고리즘을 기반으로 아래에 제공됩니다 -
// 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