Programme C pour imprimer les positions des caractères disposés afin qu'ils deviennent un palindrome

vous donne une chaîne de longueur n. Imprimez la position de chaque élément dans la chaîne pour qu'il puisse former un palindrome, sinon imprimez le message "Pas de palindrome" à l'écran.

Qu'est-ce qu'un palindrome ?

Palindrome est un mot dont la séquence de caractères lue dans le sens inverse ou arrière est la même que la séquence de caractères lue dans le sens avant, par exemple MADAME, voiture de course.

Pour savoir si une séquence ou un mot est un palindrome, nous stockons généralement l'inverse du mot dans une chaîne séparée et comparons les deux, s'ils sont identiques, alors le mot ou la séquence donné est un palindrome. Mais dans ce problème, nous devons imprimer les permutations pour former les mots ou les séquences du palindrome.

Genre, il y a une chaîne str = "tinni" alors ça peut être intni ou nitin donc on doit revenir comme index à partir de 1 et l'ordre de permutation du résultat peut être 2 3 1 4 5 ou 3 2 1 5 4 l'un des deux.

Le problème ci-dessus nécessite une solution comme l'exemple ci-dessous -

Exemple

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

Algorithme

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

Exemple

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

Sortie

Si nous exécutons le programme ci-dessus, il générera la sortie suivante -

2 3 1 4 5

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!