In vị trí đã sắp xếp của các ký tự để tạo palindrome trong C Program.

Bạn được cung cấp một chuỗi str với độ dài n nào đó. In vị trí của mọi phần tử của chuỗi để nó có thể tạo thành palindrome, nếu không thì in thông báo “Không có palindrome” trên màn hình.

palindrome là gì?

Palindrome là một từ, một chuỗi các ký tự đọc ngược lại hoặc ngược lại so với cách đọc về phía trước, như MADAM, xe đua.

Để tìm một chuỗi hoặc một từ là palindrome, chúng ta thường lưu trữ phần ngược lại của một từ trong một chuỗi riêng biệt và so sánh cả hai nếu chúng giống nhau thì từ hoặc chuỗi đã cho là palindrome. Nhưng trong câu hỏi này, chúng ta phải in ra sự sắp xếp để tạo một từ hoặc một chuỗi trong palindrome.

Giống như, có một chuỗi str =“tinni” thì nó có thể là intni hoặc nitin vì vậy chúng ta phải trả về bất kỳ một trong chuỗi sắp xếp dưới dạng chỉ mục bắt đầu từ 1 và kết quả có thể là 2 3 1 4 5 hoặc 3 2 1 5 4 trong số hai.

Vấn đề trên cần một giải pháp như ví dụ dưới đây -

Ví dụ

Input: string str = “baa”
Output: 2 1 3
Input: string str = “tinni”
Output: 2 3 1 4 5

Thuật toán

void printPalindromePos(string &str)
START
STEP 1: DECLARE vector<int> pos[MAX]
STEP 2: DECLARE AND ASSIGN n WITH LENGTH OF str
STEP 3: LOOP FOR i = 0 AND i < n AND i++
   pos[str[i]].push_back(i+1)
END LOOP
STEP 4: SET oddCount = 0
STEP 5: DECLARE oddChar
STEP 6: LOOP FOR i=0 AND i<MAX AND i++
   IF pos[i].size() % 2 != 0 THEN,
      INCREMENT oddCount BY 1
      SET oddChar AS i
   END IF
END FOR
STEP 7: IF oddCount > 1 THEN,
   PRINT "NO PALINDROME"
STEP 8: LOOP FOR i=0 AND i<MAX AND i++
   DECRLARE mid = pos[i].size()/2
   LOOP FOR j=0 AND j<mid AND j++
      PRINT pos[i][j]
   END LOOP
END LOOP
STEP 9: IF oddCount > 0 THEN,
   DECLARE AND SET last = pos[oddChar].size() - 1
   PRINT pos[oddChar][last]
   SET pos[oddChar].pop_back();
END IF
STEP 10: LOOP FOR i=MAX-1 AND i>=0 AND i--
   DECLARE AND SET count = pos[i].size()
   LOOP FOR j=count/2 AND j<count AND j++
      PRINT pos[i][j]
STOP

Ví dụ

#include <bits/stdc++.h>
using namespace std;
// Giving the maximum characters
const int MAX = 256;
void printPalindromePos(string &str){
   //Inserting all positions of characters in the given string.
   vector<int> pos[MAX];
   int n = str.length();
   for (int i = 0; i < n; i++)
      pos[str[i]].push_back(i+1);
      /* find the number of odd elements.Takes O(n) */
   int oddCount = 0;
   char oddChar;
   for (int i=0; i<MAX; i++) {
      if (pos[i].size() % 2 != 0) {
         oddCount++;
         oddChar = i;
      }
   }
   /* Palindrome can't contain more than 1 odd characters */
   if (oddCount > 1)
      cout << "NO PALINDROME";
   /* Print positions in first half of palindrome */
   for (int i=0; i<MAX; i++){
      int mid = pos[i].size()/2;
      for (int j=0; j<mid; j++)
         cout << pos[i][j] << " ";
   }
   // Consider one instance odd character
   if (oddCount > 0){
      int last = pos[oddChar].size() - 1;
      cout << pos[oddChar][last] << " ";
      pos[oddChar].pop_back();
   }
   /* Print positions in second half of palindrome */
   for (int i=MAX-1; i>=0; i--){
      int count = pos[i].size();
      for (int j=count/2; j<count; j++)
      cout << pos[i][j] << " ";
   }
}
int main(){
   string s = "tinni";
   printPalindromePos(s);
   return 0;
}

Đầu ra

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau -

2 3 1 4 5