C 프로그램에서 회문을 만들기 위해 문자의 배열된 위치를 인쇄합니다.

길이가 n인 문자열 str이 제공됩니다. 회문을 형성할 수 있도록 문자열의 모든 요소 위치를 인쇄하고, 그렇지 않으면 화면에 "회문 없음" 메시지를 인쇄하십시오.

회문이란 무엇입니까?

Palindrome은 MADAM, racecar와 같이 정방향에서와 같이 역방향 또는 역방향에서 동일하게 읽는 단어, 문자 시퀀스입니다.

시퀀스 또는 단어가 회문을 찾기 위해 우리는 일반적으로 단어의 역순을 별도의 문자열에 저장하고 둘 다 같으면 주어진 단어 또는 시퀀스가 ​​회문임을 비교합니다. 그러나 이 질문에서는 회문에서 단어나 시퀀스를 만들기 위해 배열을 인쇄해야 합니다.

마찬가지로 str ="tinni"라는 문자열이 있고 intni 또는 nitin일 수 있으므로 1부터 시작하는 인덱스로 배열 시퀀스 중 하나를 반환해야 하며 결과는 2 3 1 4 5 또는 3 2 1 5가 될 수 있습니다. 둘 중 4개.

위의 문제는 아래 주어진 예와 같은 솔루션이 필요합니다 -

예시

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

알고리즘

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

예시

#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;
}

출력

위의 프로그램을 실행하면 다음과 같은 출력이 생성됩니다 -

2 3 1 4 5