Czy wyraz jest palindromem?

Coldpeer

Palindrom

anagram odwrotny - wyraz, liczba, możliwy do odczytania zarówno od lewej do prawej, jak i od prawej do lewej. Palindromem jest np. wyraz "kajak" oraz liczba 656 zapisana w systemie dziesiętnym (chociaż jeśli jest sformatowana, to tak na prawdę taka liczba również już jest tekstem). Ponadto, ciąg składający się z zera lub jednego znaku - jest palindromem (np. litera "K" lub pusty ciąg znaków "").

Językoznawcy, na pewno przewracają się w grobie, ponieważ całe zdania również mogą być palindromem, np Mr. Owl ate my metal worm. Należałoby tu pominąć znaki diaryktyczne, spacje oraz wielkośc liter. Podane implementacje tutaj mają zastosowanie jedynie do pojedynczych wyrazów.

Implementacje

C/C++:

bool is_palindrome(char* s)
{
  int n = strlen(s);
  int i = n / 2;
  while(i--) {
    if (s[i] != s[n - i - 1]) return false;
  }
  return true;
}

C++:

bool isPalindrome(const std::string &s) {
  return std::equal(s.cbegin(), s.cbegin() + s.length() / 2, s.crbegin());
}

C#

static bool isPalindrome(string s)
{
    int n = s.Length;
    int i = n / 2;
    while (i-- > 0)
    {
        if (s[i] != s[n - i - 1]) return false;
    }
    return true;
}

Pascal:

function IsPalindrome(S: String): Boolean;
var I : Integer;
begin
  I := Length(S) div 2;
  IsPalindrome := True;
  while (I > 0) do
  begin
    Dec(I);
    if (S[I+1] <> S[Length(S) - I]) then
    begin
      IsPalindrome := False;
      Exit;
    end;
  end;
end;

Python:

def is_palindrome(s):
  i = len(s)/2
  while i:
    i -= 1
    if s[i] != s[-i-1]: return False
  return True
def is_palindrome(s):
    return s[::-1] == s

Ruby:

def is_palindrome(s)
  i = s.size/2;
  while i > 0
    i -= 1
    if s[i] != s[s.size-i-1] then return false end
  end
  return true
end

PHP:

function is_palindrome($s)
{
  $i = (int)(strlen($s) / 2);
  while($i--)
    if($s[$i] != $s[strlen($s)-$i-1]) return false;
  return true;
}

JavaScript (EcmaScript):

function isPalindrome(s)
{
  var i = parseInt(s.length/2);
  while(i--)
    if(s.charAt(i) != s.charAt(s.length-i-1)) return false;
  return true;
}

Implementacje w językach funkcyjnych

Ze względu na specyficzność języków funkcyjnych i deklaratywnych, implementacje tego algorytmu mogą wyglądać w nich zupełnie inaczej.

Prolog:

is_palindrome(A, A).
is_palindrome([_|A], A).
is_palindrome([H|T], L) :-
	is_palindrome(T, [H|L]).

23 komentarzy

Można by to wykonać bez strlen i strrev - wystarczy najpierw znaleźć sąsiadujące takie same znaki w rodzaju "...bb..." lub "...bcb..." a potem już tylko porównywać następne znaki z tym co już było.

bool isPalindrome(string s)
{
int i = s.Lenght() / 2;
while (i > 0)
{
if(s[i] != s[n - i - 1] ) return false;
i--;
}
return true;
}

gdzie tutaj masz n zadeklarowane wcześniej ??

// w ANSI C
#include <stdio.h>
#include <stdlib.h>

int palindrom(int n,char napis[]){

for(int i=0;i<(n/2);i++){
if(napis[i]!=napis[n-1-i])
{
return 0;
}
}
return 1;

}

int main(){
system("cls");

char napis[]="ANA";
int n=sizeof(napis)-1;

if(palindrom(n,napis)==1){
printf("Anagram");
}else{
printf("Nie jest");
}

}

Jestem tu nowy i wygląda to dziwnie !!! :D

sorki ale naprawde niewiem jakie ma ograniczenia Pascal wzgledem delphi :(

@Jojersztajner: w obecnym GeSHi na 4p nie ma kolorowania składni dla Ruby, a składnia Pythona jest dość podobna.
PS. jest różnica w JS między string[x] a string.charAt(x)?
PS2. no i zamieniłeś isPalindrome w pętli w Pascalu na Result, które występuje chyba tylko w Delphi? (w TP nie, nie pamiętam jak np. FPC)

lol ale gafa, racja i prawda nie sprawdzalem :D sorki juz poprawiam

@sasio, czy nie stworzyłeś pętli nieskończonej? W końcu pred(i) nie obniży i, prawda?

Sprawdziłeś ten kod?

sasio: nie mówię, że jest coś w tym złego... ale po prostu kod powinien być też dla użytkowników np. Turbo Pascala.

a jest cos w tym zlego ? i-- to wkoncu wymysl C xD. Pozatym moj kod jest 100x szybszy (samo const daje speed-a :D). Ale zostawmy ten temat arytkul na 5 , prosty, niedlugi i wystarczajacy.

Warto wspomnieć, że Pred to wymysł Delphi.
PS. moja pierwsza wersja tego tekstu zawierała kod Pascala, zbliżony ideologią trochę do Twojego :)

function IsPalindrome(const s: string): Boolean;
var i,l: integer;
begin
  Result := False;

  l := Length(s);
  i := l div 2;

  while i <> 0 do
  begin
    Dec(i);
    if s[i+1] <> s[l-i] then Exit;
  end;

  Result := True;
end;

Tutaj macie a wieeeeele szybsza funkcje xD

haha, no fakt, przecież można całość odbić :D

kz_x: oszukujesz, odwracasz całość :P
Jeżeli tak na to patrzeć to:
Python:

p=lambda s:s==s[::-1]

PHP:

function p($s){ return $s==strrev($s));}

Boję się pomyśleć, jak to w perlu by wyglądało...

Tak dla zabawy. Jednolinijkowiec [PHP]:

function is_palindrome($w){return strlen($w) == 1 || substr($w, 0, strlen($w)/2) == strrev(substr($w, -strlen($w)/2));}

Tak dla zabawy. Jednolinijkowiec [Python]:

def is_palindrome(s): return len(s) <=1 or list(s[:len(s)/2])==list(reversed(s[-(len(s)/2):]))

:) Hmm, ale dlaczego tekstu nie ma w kategorii JavaScript/FAQ, pomimo, że dodałem {{Cat:JavaScript/FAQ}}?

Jak tu ładnie widać przewagę konstrukcji a'la C nad konstrukcją Pascala :)

Hmm, masz trochę racji, ale jak to wyglądałoby w dziale Delphi, gdzie jest głównie sam opis języka?
Usunąłem już z Algorytmów - teraz jest 1x.
// kurdę, znowu się coś z kategoryzacją skrzaczyło.

I to się nazywa art o algorytmie!
Pseudokod + implementacje w wielu językach - super!

Tylko dlaczego 2x w Algorytmach. I te 4 FAQ wygląda śmiesznie :/

Jednolinijkowiec w CLI (cli.up.pl): p(x):=(x=str_revert(x)); (nie za szybkie, ale krótkie)
Kto da mniej?