Bagaimana cara memeriksa bahwa sebuah string adalah palindrome menggunakan ekspresi reguler?

93

Itu adalah pertanyaan wawancara yang tidak bisa saya jawab:

Bagaimana cara memeriksa bahwa sebuah string adalah palindrome menggunakan ekspresi reguler?

ps Sudah ada pertanyaan " Bagaimana cara memeriksa apakah string yang diberikan adalah palindrome? " dan ini memberikan banyak jawaban dalam berbagai bahasa, tetapi tidak ada jawaban yang menggunakan ekspresi reguler.

Degvik
sumber
1
stackoverflow.com/questions/3644266/… dapat memberikan ide.
Prakhar
2
Untuk saat ini (2018) dan siapa yang mencari "the palindrome regex", lihat diskusi tentang PCRE yang mendukung pola rekursif di tautan Prakhar, dan regex rekursif saya di bawah, dengan perbandingan .
Peter Krauss

Jawaban:

151

Jawaban atas pertanyaan ini adalah "tidak mungkin". Lebih khusus lagi, pewawancara bertanya-tanya apakah Anda memperhatikan kelas teori komputasi Anda.

Di kelas teori komputasi Anda, Anda belajar tentang mesin keadaan hingga. Mesin negara hingga terdiri dari node dan edge. Setiap tepi diberi anotasi dengan huruf dari alfabet terbatas. Satu atau lebih node adalah node "penerima" khusus dan satu node adalah node "start". Karena setiap huruf dibaca dari kata tertentu, kami melintasi tepi yang diberikan di mesin. Jika kita berakhir dalam keadaan menerima maka kita mengatakan bahwa mesin "menerima" kata itu.

Ekspresi reguler selalu dapat diterjemahkan ke dalam mesin keadaan hingga yang setara. Yaitu, salah satu yang menerima dan menolak kata yang sama dengan ekspresi reguler (di dunia nyata, beberapa bahasa regexp memungkinkan untuk fungsi arbitrer, ini tidak dihitung).

Tidak mungkin untuk membangun mesin negara hingga yang menerima semua palindrome. Pembuktiannya bergantung pada fakta bahwa kita dapat dengan mudah membangun string yang membutuhkan node dalam jumlah besar secara sembarangan, yaitu string

a ^ xba ^ x (mis., aba, aabaa, aaabaaa, aaaabaaaa, ....)

dimana a ^ x adalah x kali berulang. Ini membutuhkan setidaknya x node karena, setelah melihat 'b' kita harus menghitung mundur sebanyak x kali untuk memastikan itu adalah palindrome.

Terakhir, kembali ke pertanyaan awal, Anda dapat memberi tahu pewawancara bahwa Anda dapat menulis ekspresi reguler yang menerima semua palindrom yang lebih kecil dari beberapa panjang tetap yang terbatas. Jika pernah ada aplikasi dunia nyata yang memerlukan identifikasi palindrom maka hampir pasti tidak akan menyertakan palindrom yang panjang secara sembarangan, jadi jawaban ini akan menunjukkan bahwa Anda dapat membedakan kemustahilan teoretis dari aplikasi dunia nyata. Namun, regexp sebenarnya akan cukup panjang, lebih panjang dari program 4 baris yang setara (latihan mudah bagi pembaca: tulis program yang mengidentifikasi palindrom).

Jose M Vidal
sumber
6
@SteveMoser Di Ruby 1.9.x, ekspresi reguler tidak lagi Reguler (dalam pengertian Teori Automata) dan dengan demikian hal-hal seperti memeriksa palindrom dimungkinkan. Namun, untuk maksud dan tujuan, palindrome tidak dapat diperiksa dengan Reguler Reguler (masuk akal?).
1
@SteveMoser Ada catatan bagus tentang mesin ekspresi reguler Ruby ( >=1.9) di sini
@ John benar, jadi dalam konteks pertanyaan Jose benar dan HQt salah.
Steve Moser
2
Dalam istilah akademis, ekspresi reguler memiliki batas khusus (mendefinisikan DFA). Pada kenyataannya, banyak mesin regexp (Perl dan kerabat utamanya) mendukung referensi latar yang melanggar definisi akademis (menjadi NFA atau bahkan lebih luas). Jadi pertanyaan ini memiliki jawaban yang berbeda tergantung pada kerangka acuan penanya.
jiggy
Dalam pengujian lisan, Anda harus menggunakan "formalz itu tidak mungkin", tetapi Anda harus menunjukkan bahwa beberapa mesin regex mengizinkannya.
Oliver A.
46

Meskipun mesin PCRE mendukung ekspresi reguler rekursif (lihat jawaban oleh Peter Krauss ), Anda tidak dapat menggunakan regex di ICU mesin (seperti yang digunakan, misalnya, oleh Apple) untuk mencapai ini tanpa kode tambahan. Anda perlu melakukan sesuatu seperti ini:

Ini mendeteksi palindrome apa pun, tetapi memerlukan loop (yang akan diperlukan karena ekspresi reguler tidak dapat dihitung).

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";
Airsource Ltd
sumber
4
Jawaban yang bagus. Pertanyaan tersebut tidak meminta satu regexp yang mendeteksi palindrome langsung dari kotaknya - pertanyaan tersebut hanya menanyakan metode untuk mendeteksi palindrome yang menggunakan regexps. Selamat atas wawasan Anda yang melihatnya dengan cara ini.
Stewart
1
Lihat juga pencocokan paling sederhana (tanpa manipulasi string) hanya menggunakan satu regex, stackoverflow.com/a/48608623/287948
Peter Krauss
Terima kasih @PeterKrauss. Tidak tahu bahwa PCRE mengalami rekursi. Referensi jawaban Anda.
Airsource Ltd
32

Itu tidak mungkin. Palindrom tidak didefinisikan oleh bahasa biasa. (Lihat, saya TELAH belajar sesuatu dalam teori komputasi)

ZCHudson
sumber
2
Sebagian besar mesin ekspresi reguler menangkap lebih dari bahasa biasa (misalnya, net dapat menangkap tanda kurung yang cocok). Hanya ekspresi reguler standar yang dibatasi untuk bahasa reguler.
Santiago Palladino
Pertanyaan itu memang menggunakan istilah "ekspresi reguler" ... jadi jawaban ZCHudson benar.
paxos1977
2
@austirg: Jawaban ZCHudson benar tetapi tidak lengkap. Ekspresi reguler yang digunakan dalam bahasa pemrograman modern dan ekspresi reguler yang digunakan dalam kelas CS teoretis adalah binatang yang berbeda. Istilah itu hanyalah warisan sejarah. Lihat stackoverflow.com/questions/233243#235199 dan jawaban saya.
jfs
2
@ JF Sebastian - Saya harus setuju dengan austirg tentang ini. Ketika istilah ekspresi reguler digunakan tanpa disebutkan bahasa pemrograman tertentu, maka definisi comp sci berlaku. Tidak semua bahasa yang mendukung regex dapat melakukan ini, jadi sebaiknya kita tidak menganggap bahasa yang digunakan di sini dapat melakukannya.
Rontologis
@Rontologist: Saya tidak melihat batasan pada pilihan bahasa pemrograman dalam pertanyaan, sehingga bahasa apapun diperbolehkan. Lihat ke kanan: apa yang dimaksud dengan "regular expression" pada pertanyaan terkait? Apakah bahasa pemrograman tertentu disebutkan di salah satunya?
jfs
27

Dengan Perl regex:

/^((.)(?1)\2|.?)$/

Meskipun, seperti yang ditunjukkan banyak orang, ini tidak dapat dianggap sebagai ekspresi reguler jika Anda ingin bersikap tegas. Ekspresi reguler tidak mendukung rekursi.

Markus Jarderot
sumber
ini tidak berfungsi di PCRE (tidak cocok dengan "ababa"), tetapi berfungsi di Perl 5.10
newacct
Kamu benar. PCRE tampaknya memperlakukan rekursi sebagai kelompok atom, sementara Perl mengizinkan pengulangan di dalamnya. Saya rasa tidak mungkin melakukan pemeriksaan ini di PCRE.
Markus Jarderot
1
Anehnya, tidak berfungsi untuk bahasa non-Latin, misalnya bahasa Armenia.
Temujin
3
@Temujin Ini karena karakter unicode cocok sebagai byte yang dikodekan (tambahkan /upengubah ), atau karena karakter kombinator. (ganti .dengan \Xescape sequence ).
Markus Jarderot
1
Pola saya tidak berfungsi di PCRE. Ini berfungsi di Perl. Pola Anda gagal saat substring diulang. Misalnya abababa. Tidak mungkin membuatnya bekerja dengan rekursi untuk setiap input saat menggunakan mesin regex berbasis PCRE. Casimirs regex menggunakan pendekatan yang berbeda, menggunakan iterasi dan status bisa berubah, dan cukup menarik.
Markus Jarderot
15

Ini satu untuk mendeteksi palindrom 4 huruf (misalnya: akta), untuk semua jenis karakter:

\(.\)\(.\)\2\1

Ini satu untuk mendeteksi palindrom 5 huruf (misalnya: radar), hanya memeriksa huruf:

\([a-z]\)\([a-z]\)[a-z]\2\1

Jadi sepertinya kita membutuhkan regex yang berbeda untuk setiap panjang kata yang memungkinkan. Posting ini di milis Python menyertakan beberapa detail mengapa (Finite State Automata dan pumping lemma).

UNTUK
sumber
14

Bergantung pada seberapa yakin Anda, saya akan memberikan jawaban ini:

Saya tidak akan melakukannya dengan ekspresi reguler. Ini bukan penggunaan ekspresi reguler yang tepat.

Jon Skeet
sumber
3
Saya berharap Anda memberikan sedikit penjelasan lebih lanjut, untuk menunjukkan bahwa Anda benar-benar memahami batasan regex. Jawaban sederhana Anda mungkin akan dianggap sebagai "Saya bingung".
Scott Wegner
Oleh karena itu klausa dependen yang dia berikan.
Will Bickford
13

Ya , Anda dapat melakukannya di .Net!

(?<N>.)+.?(?<-N>\k<N>)+(?(N)(?!))

Kamu bisa cek di sini ! Ini pos yang luar biasa!

kev
sumber
Inti dari Regex rasa .NET adalah bahwa mereka tidak biasa karena mereka bukan automata keadaan terbatas; mereka tidak benar-benar regex dalam arti teoritis.
kucing
12

StackOverflow penuh dengan jawaban seperti "Ekspresi reguler? Tidak, mereka tidak mendukungnya. Mereka tidak bisa mendukungnya.".

Yang benar adalah bahwa ekspresi reguler tidak ada hubungannya dengan tata bahasa reguler lagi.Ekspresi reguler modern menampilkan fungsi seperti rekursi dan grup penyeimbang, dan ketersediaan implementasinya terus bertambah (lihat contoh Ruby di sini, misalnya). Menurut pendapat saya, berpegang pada keyakinan lama bahwa ekspresi reguler di bidang kita sama sekali bukan konsep pemrograman hanyalah kontraproduktif. Alih-alih membenci mereka karena pilihan kata yang tidak lagi sesuai, sekarang saatnya kita menerima sesuatu dan melanjutkan hidup.

Berikut kutipan dari Larry Wall , pencipta Perl itu sendiri:

(…) Umumnya berkaitan dengan apa yang kita sebut "ekspresi reguler", yang hanya sedikit terkait dengan ekspresi reguler nyata. Namun demikian, istilah tersebut telah berkembang dengan kemampuan mesin pencocokan pola kami, jadi saya tidak akan mencoba melawan kebutuhan linguistik di sini. Saya akan, bagaimanapun, umumnya menyebutnya "regexes" (atau "regexen", ketika saya dalam mood Anglo-Saxon).

Dan inilah posting blog oleh salah satu pengembang inti PHP :

Karena artikelnya cukup panjang, berikut ringkasan poin utamanya:

  • “Ekspresi reguler” yang digunakan oleh pemrogram memiliki sedikit kesamaan dengan pengertian asli tentang keteraturan dalam konteks teori bahasa formal.
  • Ekspresi reguler (setidaknya PCRE) dapat cocok dengan semua bahasa tanpa konteks. Dengan demikian, mereka juga dapat mencocokkan HTML yang dibentuk dengan baik dan hampir semua bahasa pemrograman lainnya.
  • Ekspresi reguler dapat cocok setidaknya dengan beberapa bahasa yang peka konteks.
  • Pencocokan ekspresi reguler adalah NP-complete. Dengan demikian, Anda dapat menyelesaikan masalah NP lainnya menggunakan ekspresi reguler.

Karena itu, Anda dapat mencocokkan palindrome dengan ekspresi reguler menggunakan ini:

^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$

... yang jelas tidak ada hubungannya dengan tata bahasa biasa.
Info lebih lanjut di sini: http://www.regular-expressions.info/balancing.html

rr-
sumber
9

Seperti yang telah dikatakan beberapa orang, tidak ada satu ekspresi reguler yang akan mendeteksi palindrom umum di luar kotak, tetapi jika Anda ingin mendeteksi palindrom hingga panjang tertentu, Anda dapat menggunakan sesuatu seperti

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
Stewart
sumber
7

Itu bisa dilakukan di Perl sekarang. Menggunakan referensi rekursif:

if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){
    print $istr," is palindrome\n";
}

dimodifikasi berdasarkan bagian terakhir http://perldoc.perl.org/perlretut.html

Hui Liu
sumber
6

Di ruby ​​Anda dapat menggunakan grup penangkapan bernama. jadi sesuatu seperti ini akan berhasil -

def palindrome?(string)
  $1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\z/x
end

coba, berhasil ...

1.9.2p290 :017 > palindrome?("racecar")
 => "racecar" 
1.9.2p290 :018 > palindrome?("kayak")
 => "kayak" 
1.9.2p290 :019 > palindrome?("woahitworks!")
 => nil 
Taylor
sumber
1
Grup tangkapan bernama tidak sepenuhnya regex. willamette.edu/~fruehr/LLC/lab5.html
Steve Moser
2
Anda benar. Itulah mengapa saya menunjukkan bahwa Anda harus menggunakan grup penangkapan bernama.
Taylor
Bisakah seseorang secara kebetulan menjelaskan karakter RE itu demi karakter untuk seorang pemula? Saya memahami semua berikut ini (koma memisahkan 'atom') /, \ A, (, |, \ w, |, (, (, \ w,),),), \ z, /, x tetapi saya tidak tidak memahami semua ini? <p>,?:,? <l>, \ g <p>, \ k <l + 0> dan saya menggunakan rubular.com untuk bantuan dan tampaknya memahami RE ( secara alami), tetapi itu tidak membantu saya melihatnya, dan bahkan "Untuk panduan regex Ruby lengkap, lihat Beliung." tidak membantu, karena situs yang ditautkan dengan 'Beliung' tidak menjelaskan atom yang gagal saya pahami. Aku tahu ? MENGIKUTI kecocokan Nol atau salah satu, tapi? mendahului karakter?
Kevin Ford kapal selam
Ah, kelompok penangkap bernama ! Bagus. @SteveMoser yang sekarang menjadi tautan rusak, tetapi saya menemukan yang lain . Terima kasih Taylor untuk menyebutkannya, karena jika tidak, saya tidak akan tahu apa yang dimaksud dengan? <p> dan? <l> dan?: (Grup penangkap tidak menangkap) dan \ g <p> dan \ k <l + 0>. Saya masih tidak bisa melihat apa? <p> | adalah. Tidak | berarti "atau"? Saya tidak dapat menemukan dokumentasi penggunaan pipa tersebut di RE. Saya masih senang melihat penjelasan rinci untuk RE yang sangat bagus ini.
Kevin Ford si kapal selam
5

Sebenarnya lebih mudah melakukannya dengan manipulasi string daripada ekspresi reguler:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

Saya menyadari ini tidak benar-benar menjawab pertanyaan wawancara, tetapi Anda dapat menggunakannya untuk menunjukkan bagaimana Anda mengetahui cara yang lebih baik dalam melakukan tugas, dan Anda bukan tipe "orang dengan palu, yang melihat setiap masalah sebagai paku. . "

Dan
sumber
Sedangkan saya sangat menyukai jawaban ini, saya pikir Anda akan mendapatkan poin ekstra dengan menggunakan BreakIterator untuk membagi string dengan benar menjadi karakter visual.
Trejkaz
5

Inilah jawaban saya untuk level 5 Regex Golf (Seorang pria, rencana). Ia bekerja hingga 7 karakter dengan Regexp browser (Saya menggunakan Chrome 36.0.1985.143).

^(.)(.)(?:(.).?\3?)?\2\1$

Ini satu untuk maksimal 9 karakter

^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$

Untuk meningkatkan jumlah maksimal karakter yang berfungsi, Anda akan berulang kali mengganti .? dengan (?: (.).? \ n?)? .

pbatey.dll
sumber
1
Saya berhasil yang satu dengan karakter yang sedikit lebih sedikit, ^ (.) (.) (.)?.? \ 3 \ 2 \ 1 $
Ben Ellis
Terima kasih banyak karena telah memanjakan saya :-)
U10-Forward
Mengapa orang-orang lainnya memiliki 13 tetapi ini adalah 19
U10-Maju
5

Ekspresi Reguler Rekursif dapat melakukannya!

Algoritme yang sangat sederhana dan terbukti dengan sendirinya untuk mendeteksi string yang berisi palindrome:

   (\w)(?:(?R)|\w?)\1

Di rexegg.com/regex-recursion , tutorial menjelaskan cara kerjanya.


Ini berfungsi dengan baik dengan bahasa apa pun, berikut contoh yang diadaptasi dari sumber yang sama (tautan) sebagai bukti-konsep, menggunakan PHP:

$subjects=['dont','o','oo','kook','book','paper','kayak','okonoko','aaaaa','bbbb'];
$pattern='/(\w)(?:(?R)|\w?)\1/';
foreach ($subjects as $sub) {
  echo $sub." ".str_repeat('-',15-strlen($sub))."-> ";
  if (preg_match($pattern,$sub,$m)) 
      echo $m[0].(($m[0]==$sub)? "! a palindrome!\n": "\n");
  else 
      echo "sorry, no match\n";
}

keluaran

dont ------------> sorry, no match
o ---------------> sorry, no match
oo --------------> oo! a palindrome!
kook ------------> kook! a palindrome!
book ------------> oo
paper -----------> pap
kayak -----------> kayak! a palindrome!
okonoko ---------> okonoko! a palindrome!
aaaaa -----------> aaaaa! a palindrome!
bbbb ------------> bbb

Perbandingan

Ekspresi reguler ^((\w)(?:(?1)|\w?)\2)$ melakukan pekerjaan yang sama, tetapi sebagai yes / not, bukan "berisi".
PS: menggunakan definisi di mana "o" bukan palimbrome, format "dapat-elba" dengan tanda hubung bukan palindrome, tetapi "ableelba "adalah. Menamainya definisi1 .
Ketika "o" dan "mampu-elba" adalah palindrones, definisi penamaan2 .

Membandingkan dengan "palindrome regexes" lainnya,

  • ^((.)(?:(?1)|.?)\2)$basis-regex di atas tanpa \wbatasan, menerima "mampu-elba".

  • ^((.)(?1)?\2|.)$( @LilDevil ) Gunakan definisi2 (menerima "o" dan "mampu-elba" sehingga membedakan juga dalam pengenalan string "aaaaa" dan "bbbb").

  • ^((.)(?1)\2|.?)$( @Markus ) tidak terdeteksi "kook" dan "bbbb"

  • ^((.)(?1)*\2|.?)$( @Csaba ) Gunakan definisi2 .


CATATAN: untuk membandingkan Anda dapat menambahkan lebih banyak kata di $subjectsdan satu baris untuk setiap ekspresi reguler yang dibandingkan,

  if (preg_match('/^((.)(?:(?1)|.?)\2)$/',$sub)) echo " ...reg_base($sub)!\n";
  if (preg_match('/^((.)(?1)?\2|.)$/',$sub)) echo " ...reg2($sub)!\n";
  if (preg_match('/^((.)(?1)\2|.?)$/',$sub)) echo " ...reg3($sub)!\n";
  if (preg_match('/^((.)(?1)*\2|.?)$/',$sub)) echo " ...reg4($sub)!\n";
Peter Krauss
sumber
5

Anda juga dapat melakukannya tanpa menggunakan rekursi:

\A(?:(.)(?=.*?((?(2)\1\2|\1))\z))*?.?\2\z

untuk mengizinkan satu karakter:

\A(?:(?:(.)(?=.*?((?(2)\1\2|\1))\z))*?.?\2|.)\z

Bekerja dengan Perl, PCRE

demo

Untuk Java:

\A(?:(.)(?=.*?(\1\2\z|(?<!(?=\2\z).{0,1000})\1\z)))*?.?\2\z

demo

Casimir et Hippolyte
sumber
1
Ini adalah jawaban yang sangat menarik untuk pertanyaan regex. Sebenarnya satu-satunya pola, yang lolos dari beberapa ujian saya . Terima kasih untuk Casimir yang satu ini :)
gelembung berbandul
1
@bobblebubble: Terima kasih atas dukungan Anda. Seperti yang Anda lihat, saya mengedit jawaban ini baru-baru ini karena versi sebelumnya salah (selama tiga tahun, sayang sekali).
Casimir et Hippolyte
4

Mengenai ekspresi PCRE (dari MizardX):

/^((.)(?1)\2i>.?)$/

Sudahkah Anda mengujinya? Pada PHP 5.3 saya di bawah Win XP Pro gagal pada: aaaba Sebenarnya, saya mengubah ekspresi ekspresi sedikit, untuk membaca:

/^((.)(?1)*\2i>.?)$/

Saya pikir apa yang terjadi adalah bahwa sementara pasangan luar dari karakter berlabuh, yang dalam tidak. Ini bukanlah jawaban yang lengkap karena meskipun salah menyampaikan pada "aaaba" dan "aabaacaa", namun gagal dengan benar pada "aabaaca".

Saya bertanya-tanya apakah ada perbaikan untuk ini, dan juga, Apakah contoh Perl (oleh JF Sebastian / Zsolt) lulus tes saya dengan benar?

Csaba Gabor dari Wina


sumber
4
/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/

ini berlaku untuk mesin Oniguruma (yang digunakan di Ruby)

diambil dari Rak Buku Pragmatis

mpugach.dll
sumber
3

Di Perl (lihat juga jawaban Zsolt Botykai ):

$re = qr/
  .                 # single letter is a palindrome
  |
  (.)               # first letter
  (??{ $re })??     # apply recursivly (not interpolated yet)
  \1                # last letter
/x;

while(<>) {
    chomp;
    say if /^$re$/; # print palindromes
}
jfs
sumber
2

Seperti yang ditunjukkan oleh ZCHudson , menentukan apakah sesuatu adalah palindrome tidak dapat dilakukan dengan regexp biasa, karena himpunan palindrome bukanlah bahasa biasa.

Saya sama sekali tidak setuju dengan Airsource Ltd ketika dia mengatakan bahwa "itu tidak mungkin" bukanlah jenis jawaban yang dicari pewawancara. Selama wawancara, saya sampai pada pertanyaan seperti ini ketika saya menghadapi kandidat yang baik, untuk memeriksa apakah dia dapat menemukan argumen yang tepat ketika kami melamarnya untuk melakukan sesuatu yang salah. Saya tidak ingin mempekerjakan seseorang yang akan mencoba melakukan sesuatu dengan cara yang salah jika dia lebih tahu.

Nicolas
sumber
2

Saya akan menjelaskan kepada pewawancara bahwa bahasa yang terdiri dari palindrome bukanlah bahasa biasa tetapi bebas konteks.

Ekspresi reguler yang akan cocok dengan semua palindrome adalah tak terbatas . Sebaliknya saya akan menyarankan dia membatasi dirinya baik pada ukuran maksimum palindrome untuk diterima; atau jika semua palindrom diperlukan, gunakan minimal beberapa jenis NDPA, atau cukup gunakan teknik pembalikan / sama dengan string sederhana.

Api
sumber
2

Hal terbaik yang dapat Anda lakukan dengan regex, sebelum Anda kehabisan grup tangkapan:

/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/

Ini akan cocok dengan semua palindrome dengan panjang hingga 19 karakter.

Pemecahan programat untuk semua panjang itu sepele:

str == str.reverse ? true : false
Chris
sumber
Regex Anda tidak berfungsi. Misalnya, ini akan menunjukkan bahwa "abac" adalah pertandingan ...
Darwin Airola
2

Saya belum memiliki perwakilan untuk mengomentari sebaris, tetapi ekspresi reguler yang disediakan oleh MizardX, dan dimodifikasi oleh Csaba, dapat dimodifikasi lebih lanjut agar berfungsi di PCRE. Satu-satunya kegagalan yang saya temukan adalah string karakter tunggal, tetapi saya dapat mengujinya secara terpisah.

/^((.)(?1)?\2|.)$/

Jika Anda bisa membuatnya gagal di string lain, silakan beri komentar.

Lil Devil
sumber
2
#!/usr/bin/perl

use strict;
use warnings;

print "Enter your string: ";
chop(my $a = scalar(<STDIN>));    
my $m = (length($a)+1)/2;
if( (length($a) % 2 != 0 ) or length($a) > 1 ) { 
  my $r; 
  foreach (0 ..($m - 2)){
    $r .= "(.)";
  }
  $r .= ".?";
  foreach ( my $i = ($m-1); $i > 0; $i-- ) { 
    $r .= "\\$i";
  } 
  if ( $a =~ /(.)(.).\2\1/ ){
    print "$a is a palindrome\n";
  }
  else {
    print "$a not a palindrome\n";
 }
exit(1);
}
print "$a not a palindrome\n";
sapam
sumber
2

Dari teori automata, mustahil untuk menyamai paliandrome dengan panjang apa pun (karena itu membutuhkan jumlah memori yang tak terbatas). Tapi MUNGKIN mencocokkan Paliandromes of Fixed Length. Katakanlah mungkin untuk menulis regex yang cocok dengan semua paliandrom dengan panjang <= 5 atau <= 6 dll, tetapi tidak> = 5 dll di mana batas atasnya tidak jelas

Vijeenrosh PW
sumber
2

Di Ruby Anda bisa menggunakan \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\buntuk mencocokkan kata-kata palindrome seperti a, dad, radar, racecar, and redivider. ps: regex ini hanya cocok dengan kata palindrome dengan jumlah huruf ganjil.

Mari kita lihat bagaimana ekspresi reguler ini cocok dengan radar. Batas kata \ b cocok di awal string. Mesin regex memasukkan "kata" grup penangkap. [az] cocok dengan r yang kemudian disimpan dalam tumpukan untuk "huruf" grup penangkap pada tingkat rekursi nol. Sekarang mesin regex memasuki rekursi pertama dari grup "kata". (? 'letter' [az]) cocok dan menangkap pada tingkat rekursi satu. Regex memasuki rekursi kedua dari grup "kata". (? 'letter' [az]) menangkap d pada tingkat rekursi dua. Selama dua rekursi berikutnya, grup menangkap a dan r di level tiga dan empat. Rekursi kelima gagal karena tidak ada karakter tersisa di string untuk [az] agar cocok. Mesin regex harus mundur.

Mesin regex sekarang harus mencoba alternatif kedua di dalam grup "kata". [Az] kedua di ekspresi reguler cocok dengan r terakhir dalam string. Mesin sekarang keluar dari rekursi yang berhasil, naik satu tingkat kembali ke rekursi ketiga.

Setelah mencocokkan (& kata) mesin mencapai \ k'letter + 0 '. Referensi belakang gagal karena mesin regex telah mencapai akhir string subjek. Jadi itu mundur sekali lagi. Alternatif kedua sekarang cocok dengan a. Mesin regex keluar dari rekursi ketiga.

Mesin regex telah mencocokkan lagi (& kata) dan perlu mencoba referensi kembali lagi. Referensi latar menentukan +0 atau tingkat rekursi saat ini, yaitu 2. Pada tingkat ini, kelompok penangkap cocok d. Referensi belakang gagal karena karakter berikutnya dalam string adalah r. Mundur lagi, alternatif pertandingan kedua d.

Sekarang, \ k'letter + 0 'cocok dengan huruf a kedua dalam string. Itu karena mesin regex telah tiba kembali pada rekursi pertama di mana grup penangkap cocok dengan yang pertama a. Mesin regex keluar dari rekursi pertama.

Mesin regex sekarang kembali keluar dari semua rekursi. Bahwa tingkat ini, kelompok penangkap disimpan r. Referensi belakang sekarang bisa cocok dengan r terakhir dalam string. Karena mesin tidak lagi berada di dalam rekursi apa pun, mesin melanjutkan dengan sisa regex setelah grup. \ b cocok di akhir string. Akhir regex tercapai dan radar dikembalikan sebagai pertandingan keseluruhan.

Melih Altıntaş
sumber
2

berikut adalah kode PL / SQL yang memberi tahu apakah string yang diberikan adalah palindrome atau tidak menggunakan ekspresi reguler:

create or replace procedure palin_test(palin in varchar2) is
 tmp varchar2(100);
 i number := 0;
 BEGIN
 tmp := palin;
 for i in 1 .. length(palin)/2 loop
  if length(tmp) > 1 then  
    if regexp_like(tmp,'^(^.).*(\1)$') = true then 
      tmp := substr(palin,i+1,length(tmp)-2);
    else 
      dbms_output.put_line('not a palindrome');
      exit;
    end if;
  end if;  
  if i >= length(palin)/2 then 
   dbms_output.put_line('Yes ! it is a palindrome');
  end if;
 end loop;  
end palin_test;
ankush
sumber
2
my $pal='malayalam';

while($pal=~/((.)(.*)\2)/){                                 #checking palindrome word
    $pal=$3;
}
if ($pal=~/^.?$/i){                                         #matches single letter or no letter
    print"palindrome\n";
}
else{
    print"not palindrome\n";
}
Kanchan Sen Laskar
sumber
2
Meskipun kode ini dapat menjawab pertanyaan, memberikan konteks tambahan tentang bagaimana dan / atau mengapa kode ini memecahkan masalah akan meningkatkan nilai jawaban jangka panjang.
Donald Duck
2

Regex ini akan mendeteksi palindrom hingga 22 karakter yang mengabaikan spasi, tab, koma, dan tanda kutip.

\b(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*\11?[ \t,'"]*\10|\10?)[ \t,'"]*\9|\9?)[ \t,'"]*\8|\8?)[ \t,'"]*\7|\7?)[ \t,'"]*\6|\6?)[ \t,'"]*\5|\5?)[ \t,'"]*\4|\4?)[ \t,'"]*\3|\3?)[ \t,'"]*\2|\2?))?[ \t,'"]*\1\b

Mainkan di sini: https://regexr.com/4tmui

Tony Tonev
sumber
0

Sedikit penyempurnaan metode Airsource Ltd, dalam kodesemu:

WHILE string.length > 1
    IF /(.)(.*)\1/ matches string
        string = \2
    ELSE
        REJECT
ACCEPT
Stewart
sumber