如何检查一个string是使用正则expression式的回文？
这是一个我无法回答的面试问题：
如何检查一个string是使用正则expression式的回文？
ps已经有一个问题“ 如何检查给定的string是否是回文？ ”，它给了很多不同的语言的答案，但没有使用正则expression式的答案。
这个问题的答案是“这是不可能的”。 更具体地说，面试官想知道你是否在计算理论课上注意了。
在您的计算理论课中，您了解了有限状态机。 有限状态机由节点和边组成。 每条边都用有限字母表中的字母标注。 一个或多个节点是特殊的“接受”节点，一个节点是“开始”节点。 由于每个字母都是从给定的单词中读取的，我们将遍历机器中的给定边。 如果我们最终处于接受状态，那么我们说机器“接受”这个词。
正则expression式总是可以翻译成等价的有限状态机。 也就是说，接受和拒绝与正则expression式相同的单词（在现实世界中，一些正则expression式语言允许任意function，这些不计数）。
build立一个接受所有回文的有限状态机是不可能的。 certificate依赖于事实，我们可以很容易地build立一个string，需要任意数量的节点，即string
a ^ xba ^ x（例如，aba，aabaa，aaabaaa，aaaabaaaa，….）
其中a ^ x是重复的x次。 这需要至lessx个节点，因为在看到'b'之后，我们必须计数x次以确保它是回文。
最后，回到原来的问题，你可以告诉面试官，你可以写一个正则expression式来接受所有小于固定长度的回文。 如果有一个真实世界的应用程序需要识别回文，那么它几乎肯定不会包括任意长的，因此这个回答将表明您可以将理论上的不可行性与实际应用程序区分开来。 不过，实际的正则expression式会比较长，比同等的4行程序长得多（对于读者来说简单的练习：编写一个识别回文的程序）。
取决于他们正在寻找…这检测任何回文，但确实需要一个循环（这将是必需的，因为正则expression式不能计数）。
我不认为“这是不可能的”就是面试官正在寻找的东西。
$a = "teststring"; while(length $a > 1) { $a =~ /(.)(.*)(.)/; die "Not a palindrome: $a" unless $1 eq $3; $a = $2; } print "Palindrome";
这是不可能的。 回文不是由正规语言来定义的。 （请参阅我在计算理论中学到的东西）
用Perl正则expression式：
/^((.)(?1)\2|.?)$/
尽pipe如许多人所指出的，如果你想严格的话，这不能被认为是一个正则expression。 正则expression式不支持recursion。
这是一个检测4个字母的回文（例如：契据），用于任何types的字符：
\(.\)\(.\)\2\1
这里有一个检测5个字母的回文（例如：雷达），只检查字母：
\([az]\)\([az]\)[az]\2\1
所以我们似乎需要一个不同的正则expression式来处理每个可能的字长。 Python邮件列表上的这篇文章包含了一些关于为什么（有限状态自动机和抽象引理）的细节。
根据你有多自信，我会给出这个答案：
我不会用正则expression式来做。 这不正确的使用正则expression式。
是的 ，你可以在.Net上做！
(?<N>.)+.?(?<-N>\k<N>)+(?(N)(?!))
你可以在这里查看 ！ 这是一个美好的职位！
正如一些人已经说过的那样，没有一个正则expression式可以检测出一个普通的回文，但是如果你想检测到一定长度的回文，你可以使用类似的东西
(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
StackOverflow充满了“正则expression式？nope，他们不支持它的答案，他们不能支持它”。
事实是， 正则expression式与正规语法无关 。 现代正则expression式具有recursion和平衡组等function，其实现的可用性不断增长（例如，请参阅Ruby示例）。 在我看来，挂在我们这个领域的正则expression式不过是一个编程概念的旧信念只是适得其反。 与其憎恨他们select不再是最合适的词，现在是我们接受事物继续前行的时候了。
以下是Perl本身的创build者Larry Wall的一段话 ：
（…）通常与我们所称的“正则expression式”有关，而这些正则expression式只与实际的正则expression式有微小的关系。 尽pipe如此，这个词已经随着我们的模式匹配引擎的能力而增长，所以我不打算在这里反对语言的必然性。 但是，我通常会把它们称为“正则expression式”（regexen）（当我处于盎格鲁 – 撒克逊式的情绪时）。
下面是PHP核心开发人员的博客文章 ：
由于文章相当长，这里要点总结如下：
- 程序员使用的“正则expression式”在forms语言理论的背景下与原始的规则性概念很less相同。
- 正则expression式（至lessPCRE）可以匹配所有上下文无关的语言。 因此，它们也可以匹配格式良好的HTML和几乎所有其他编程语言。
- 正则expression式可以匹配至less一些上下文相关的语言。
- 正则expression式的匹配是NP完全的。 因此，您可以使用正则expression式解决任何其他NP问题。
这就是说，你可以使用这个匹配回文与正则expression式：
^(?'letter'[az])+[az]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$
这显然与正规语法无关。
更多信息在这里： http : //www.regular-expressions.info/balancing.html
在ruby中，您可以使用命名的捕获组。 所以像这样的东西将工作 –
def palindrome?(string) $1 if string =~ /\A(?<p>| \w | (?: (?<l>\w) \g<p> \k<l+0> ))\z/x end
尝试一下，它的作品…
1.9.2p290 :017 > palindrome?("racecar") => "racecar" 1.9.2p290 :018 > palindrome?("kayak") => "kayak" 1.9.2p290 :019 > palindrome?("woahitworks!") => nil
现在可以在Perl中完成。 使用recursion引用：
if($istr =~ /^((\w)(?1)\g{-1}|\w?)$/){ print $istr," is palindrome\n"; }
/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/
它适用于Oniguruma引擎（在Ruby中使用）
从实用书架
使用string操作而不是正则expression式实际上更容易：
bool isPalindrome(String s1) { String s2 = s1.reverse; return s2 == s1; }
我意识到这并不能真正回答面试的问题，但是你可以用它来展示你如何知道一个更好的方式来完成一项任务，而你并不是典型的“有锤子的人，把每一个问题视为一个钉子“。
在Perl中（另见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 }
这是我对正则高尔夫5级 （男人，一个计划）的回答。 它使用浏览器的正则expression式（我使用的是Chrome 36.0.1985.143）最多可以处理7个字符。
^(.)(.)(?:(.).?\3?)?\2\1$
这是一个最多9个字符
^(.)(.)(?:(.)(?:(.).?\4?)?\3?)?\2\1$
为了增加最多可以使用的字符数量，您需要反复更换。 与（？：（。）。？\ n？）？ 。
正如ZCHudson所指出的那样 ，确定回文是否不能用通常的正则expression式来完成，因为回文集不是常规的语言。
我完全不同意Airsource Ltd的观点，他说“这不可能”不是面试官寻找的那种答案。 在面试的时候，面对一个不错的候选人时，我会遇到这样一个问题，当我们提出他做错事的时候，看看他能否find正确的论点。 我不想雇用一个人，如果他知道的更好，他会尝试做错误的事情。
你可以用perl来做： http ://www.perlmonks.org/?node_id= 577368
我会向面试官解释，由回文组成的语言不是一种正规语言，而是上下文无关的。
匹配所有回文的正则expression式将是无限的 。 相反，我会build议他限制自己要么接受最大的回文大小; 或者如果所有的回文都需要使用至less一些types的NDPA，或者只是使用简单的string反转/等号技术。
关于PCREexpression（来自MizardX）：
/^((.)(?1)\2|.?)$/
你testing过了吗？ 在Win XP下我的PHP 5.3下，它失败了：aaaba其实，我稍微修改了expression式expression式：
/^((.)(?1)*\2|.?)$/
我想现在发生的事情是，外面的一对人物是固定的，其余的内在的不是。 这不是完全的答案，因为它不正确地传递“aaaba”和“aabaacaa”，它确实在“aabaaca”上失败。
我不知道是否有这样的修复，以及Perl的例子（通过JF Sebastian / Zsolt）是否正确地通过我的testing？
来自维也纳的Csaba Gabor
我还没有代表内联评论，但由MizardX提供的正则expression式，并由Csaba修改，可以进一步修改，使其在PCRE工作。 我发现唯一的失败是单个string，但我可以单独testing。
/^((.)(?1)?\2|.)$/
如果可以使其他string失败，请发表评论。
#!/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";
从自动机理论来说，不可能匹配任何长度的帕里病（因为这需要无限量的记忆）。 但是，它可能会匹配固定长度的Paliandromes。 说可能写一个正则expression式匹配所有长度<= 5或<= 6等，但不是> = 5等所有paliandromes上限不清楚
在Ruby中，您可以使用\b(?'word'(?'letter'[az])\g'word'\k'letter+0'|[az])\b来匹配回文词，例如a, dad, radar, racecar, and redivider 。 ps：这个正则expression式只匹配回文长度为奇数的字。
让我们看看这个正则expression式如何匹配雷达。 字边界\ b匹配string的开头。 正则expression式引擎进入捕获组“单词”。 [az]匹配r，然后将其存储在堆栈中，用于recursion级别0的捕获组“字母”。 现在，正则expression式引擎进入组“单词”的第一次recursion。 （？'letter'[az]）匹配并捕获recursion级别1。 正则expression式进入组“word”的第二次recursion。 （？'letter'[az]）在recursion级别2捕获d。 在接下来的两次recursion中，该小组在三级和四级捕获a和r。 第五次recursion失败，因为[az]string中没有剩余字符匹配。 正则expression式引擎必须回溯。
正则expression式引擎现在必须尝试第二个替代组内“单词”。 正则expression式中的第二个[az]匹配string中的最后一个r。 引擎现在退出成功的recursion，一级返回到第三次recursion。
匹配（＆字）后引擎达到\ k'letter + 0'。 反向引用失败，因为正则expression式引擎已经到达主题string的末尾。 所以它又回来了。 第二个select现在匹配a。 正则expression式引擎退出第三次recursion。
正则expression式引擎再次匹配（＆字），需要再次尝试反向引用。 反向引用指定+0或当前recursion级别，即2。在此级别，捕获组匹配d。 反向引用失败，因为string中的下一个字符是r。 再次回溯，第二个select匹配d。
现在，\ k'letter + 0匹配string中的第二个a。 这是因为正则expression式引擎已经返回到第一次recursion，在此期间捕获组匹配第一个a。 正则expression式引擎退出第一次recursion。
正则expression式引擎现在回到所有recursion之外。 这个级别，捕获组存储r。 反向引用现在可以匹配string中的最后一个r。 由于引擎不在任何recursion内部，所以它继续在组之后的正则expression式的剩余部分。 \ b匹配string的末尾。 正则expression式的结束已经到达，雷达作为整体匹配被返回。
这里是PL / SQL代码，它告诉给定的string是回文还是不使用正则expression式：
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;
Airsource有限公司的方法稍微改进，伪代码：
WHILE string.length > 1 IF /(.)(.*)\1/ matches string string = \2 ELSE REJECT ACCEPT
在用完捕获组之前，用正则expression式可以做的最好：
/(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\9\8\7\6\5\4\3\2\1/
这将匹配长达19个字符的所有回文。
程式化地解决所有的长度是微不足道的：
str == str.reverse ? true : false
你也可以做到这一点，而不使用recursion：
\A(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
或者排除空string：
\A(?=.)(?:(.)(?=.*?(\1\2?)\z))*?.?\2\z
适用于Perl，PCRE，Ruby，Java
演示
我的朋友='马拉雅拉姆';
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"; }
