Palindrome – kennt jeder. Zumindest jeder, in dessen Bekanntenkreis eine ‚Anna‘ vorkommt. 😉
Hier geht es kurz um das Finden eines Palindroms in einem vorhandenem String. Zurückgegriffen habe ich hierbei auf Python.
Nachfolgende Zeilen sind eigentlich schon der ganze ‚Zauber‘ – es steht jeweils in den Kommentaren, was passiert.
Der Code funktioniert so nicht – soll lediglich die Vorgehensweise verdeutlichen. Zum Nutzen / Testen bitte nach unten scrollen und die Datei downloaden 😉
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
[...] input = input("Mache eine String Eingabe!\n") s = convert(input) #s = input bestehend aus nur Kleinbuchstaben list = [] #speichert die Palindrome i = 1 #Startwert fuer den Durchlauf ii = 4 #Endwert - Differenz = 3, Palindrome mit < =2 Buchstaben haben ja nur bedingt Sinn b = "" #in jedem Durchlauf ermittelter (beliebiger) String pallen = 25 #Maximale Laenge der Palindrome, nach denen gesucht werden soll dif = ii - i [...] while ((dif <= len(s)-1) and (dif <= pallen)): #Palindrome mit mehr als 25 Buchstaben werden kaum vorkommen - der Durchlauf waere ansonsten halt len(s) mal... b = s[i-1:ii-1:1] #Extended Slices: b = String gebildet aus Startwert i und Endwert ii #Wenn man nur Ein-Wort Palindrome sucht: if (b == b[::-1]): #b == invertiertes b (/Palindrom)? (erreicht durch step -1) list.append(b) #Wenn man Satz-Palindrome sucht: """ einfach Kommentare loeschen if (b.replace(" ", "") == b[::-1].replace(" ", "")): list.append(b) """ dif = ii - i print(i, ii, dif, b) if ((dif == pallen) or (ii == len(s)+1)): #Am Ende des Strings angekommen --> wieder von vorn, aber mit einem Bucshtaben mehr im "Suchstring" b (/Differenz von Start/Endwert +1) print("zweites if") i = 0 ii = dif + 1 ii +=1 #damit was vorangeht ;-) i +=1 |
Das eigentliche Erwähnenswerte ist vielleicht die Vorgehensweise:
Man nehme 3 Stellen, schiebt diese solange jeweils um ein Zeichen nach rechts und prüft, ob es sich um ein Palindrom handelt, bis man am Ende des Strings angelangt ist.
Dann fängt man wieder von vorne an zu Suchen, diesmal aber mit 4 Zeichen.
Das macht man so lange einem lustig ist (ich hab das mal bei 25 begrenzt), oder bis die Stringlänge erreicht ist.
Ich hoffe, diese Methode ist wenigstens halbwegs geschickt, habe ich ja bisher nur sehr wenig Erfahrung mit Python.
Download:
GitHub Repository:
https://github.com/mammuth/Palindroms
Alternativ: (ggf. nicht immer auf dem aktuellsten Stand)
palindroms.py (3 KB) https://mega.co.nz/#!SUcgFAKR!FK2z_RytK4QmEdsqGsPBU3h_yWQXarXnYTi_aCP3cTM