C-Programm zum Ausdrucken der angeordneten Zeichenpositionen, sodass daraus ein Palindrom wird

ergibt einen String str der Länge n. Geben Sie die Position jedes Elements in der Zeichenfolge aus, damit es ein Palindrom bilden kann. Andernfalls wird die Meldung „Kein Palindrom“ auf dem Bildschirm angezeigt.

Was ist ein Palindrom?

Palindrom ist ein Wort, dessen aus der Rückwärts- oder Rückwärtsrichtung gelesene Zeichenfolge mit der aus der Vorwärtsrichtung gelesenen Zeichenfolge übereinstimmt, z. B. MADAM, Rennwagen.

Um herauszufinden, ob eine Sequenz oder ein Wort ein Palindrom ist, speichern wir normalerweise die Umkehrung des Worts in einer separaten Zeichenfolge und vergleichen die beiden. Wenn sie gleich sind, ist das gegebene Wort oder die gegebene Sequenz ein Palindrom. Aber in diesem Problem müssen wir Permutationen drucken, um Wörter oder Sequenzen in Palindromen zu bilden.

Es gibt zum Beispiel eine Zeichenfolge str = „tinni“, dann kann sie intni oder nitin sein, also müssen wir als Index beginnend bei 1 zurückkehren und die Permutationsreihenfolge des Ergebnisses kann 2 3 1 4 5 oder 3 2 1 5 sein 4 einer von beiden.

Das obige Problem erfordert eine Lösung wie im unten angegebenen Beispiel –

Beispiel

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

Algorithmus

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

Beispiel

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

Ausgabe

Wenn wir das obige Programm ausführen, generiert es die folgende Ausgabe –

2 3 1 4 5

Das obige ist der detaillierte Inhalt vonC-Programm zum Ausdrucken der angeordneten Zeichenpositionen, sodass daraus ein Palindrom wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!