当前位置： 文江博客话题详情

如何使用正则表达式检查字符串是否为回文？

发布于 2024-07-08 00:58:13 字数 221 浏览 11 评论 0原文

这是一个我无法回答的面试问题：

如何使用正则表达式检查字符串是否为回文？

ps 已经有一个问题“如何检查给定的字符串是回文吗？”，它给出了很多不同语言的答案，但没有使用正则表达式的答案。

原文

That was an interview question that I was unable to answer:

How to check that a string is a palindrome using regular expressions?

p.s. There is already a question "How to check if the given string is palindrome?" and it gives a lot of answers in different languages, but no answer that uses regular expressions.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（30）

勿忘初心 2024-07-15 00:58:13

这个问题的答案是“不可能”。 更具体地说，面试官想知道你是否在计算理论课上集中注意力。

在计算理论课上，您学习了有限状态机。 有限状态机由节点和边组成。 每条边都用有限字母表中的一个字母进行注释。 一个或多个节点是特殊的“接受”节点，一个节点是“起始”节点。 当从给定单词中读取每个字母时，我们会遍历机器中的给定边缘。 如果我们最终处于接受状态，那么我们就说机器“接受”了这个词。

正则表达式始终可以转换为等效的有限状态机。 也就是说，接受和拒绝与正则表达式相同的单词（在现实世界中，某些正则表达式语言允许任意函数，这些不计算在内）。

建立一个接受所有回文的有限状态机是不可能的。 证明依赖于这样的事实：我们可以轻松构建一个需要任意大量节点的字符串，即字符串

a^xba^x（例如，aba、aabaa、aaabaaa、aaaabaaaa，...），

其中 a^ x是重复x次。 这至少需要 x 个节点，因为在看到“b”之后，我们必须倒数 x 次以确保它是回文。

最后，回到原来的问题，你可以告诉面试官你可以编写一个正则表达式来接受所有小于某个有限固定长度的回文。 如果现实世界中有一个应用程序需要识别回文，那么它几乎肯定不会包含任意长的回文，因此这个答案将表明您可以区分理论上的不可能与现实世界的应用程序。 尽管如此，实际的正则表达式仍然相当长，比等效的 4 行程序长得多（对读者来说很容易练习：编写一个识别回文的程序）。

The answer to this question is that "it is impossible". More specifically, the interviewer is wondering if you paid attention in your computational theory class.

In your computational theory class you learned about finite state machines. A finite state machine is composed of nodes and edges. Each edge is annotated with a letter from a finite alphabet. One or more nodes are special "accepting" nodes and one node is the "start" node. As each letter is read from a given word we traverse the given edge in the machine. If we end up in an accepting state then we say that the machine "accepts" that word.

A regular expression can always be translated into an equivalent finite state machine. That is, one that accepts and rejects the same words as the regular expression (in the real world, some regexp languages allow for arbitrary functions, these don't count).

It is impossible to build a finite state machine that accepts all palindromes. The proof relies on the facts that we can easily build a string that requires an arbitrarily large number of nodes, namely the string

a^x b a^x (eg., aba, aabaa, aaabaaa, aaaabaaaa, ....)

where a^x is a repeated x times. This requires at least x nodes because, after seeing the 'b' we have to count back x times to make sure it is a palindrome.

Finally, getting back to the original question, you could tell the interviewer that you can write a regular expression that accepts all palindromes that are smaller than some finite fixed length. If there is ever a real-world application that requires identifying palindromes then it will almost certainly not include arbitrarily long ones, thus this answer would show that you can differentiate theoretical impossibilities from real-world applications. Still, the actual regexp would be quite long, much longer than equivalent 4-line program (easy exercise for the reader: write a program that identifies palindromes).

回复 原文
幸福不弃 2024-07-15 00:58:13

虽然 PCRE 引擎确实支持递归正则表达式（请参阅Peter Krauss 的回答），您不能在 ICU 引擎（例如，Apple 使用的）无需额外代码即可实现此目的。 您需要执行以下操作：

这会检测任何回文，但确实需要一个循环（这是必需的，因为正则表达式无法计数）。

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";

While the PCRE engine does support recursive regular expressions (see the answer by Peter Krauss), you cannot use a regex on the ICU engine (as used, for example, by Apple) to achieve this without extra code. You'll need to do something like this:

This detects any palindrome, but does require a loop (which will be required because regular expressions can't count).

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";
回复 原文
微凉徒眸意 2024-07-15 00:58:13

这是不可能的。 回文不是由常规语言定义的。 （看，我确实在计算理论中学到了一些东西）

It's not possible. Palindromes aren't defined by a regular language. (See, I DID learn something in computational theory)

回复 原文
难以启齿的温柔 2024-07-15 00:58:13

使用 Perl 正则表达式：

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

不过，正如许多人指出的那样，如果您想严格的话，这不能被视为正则表达式。 正则表达式不支持递归。

With Perl regex:

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

Though, as many have pointed out, this can't be considered a regular expression if you want to be strict. Regular expressions does not support recursion.

回复 原文
长途伴 2024-07-15 00:58:13

这里用于检测任何类型字符的 4 字母回文（例如：契约） ：

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

这是一个检测 5 字母回文的方法（例如：雷达），仅检查字母：

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

看来我们需要为每个可能的单词长度使用不同的正则表达式。
Python 邮件列表上的这篇文章包含一些详细信息，例如为什么（有限状态自动机和泵引理）。

Here's one to detect 4-letter palindromes (e.g.: deed), for any type of character:

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

Here's one to detect 5-letter palindromes (e.g.: radar), checking for letters only:

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

So it seems we need a different regex for each possible word length.
This post on a Python mailing list includes some details as to why (Finite State Automata and pumping lemma).

回复 原文
无风消散 2024-07-15 00:58:13

根据您的自信程度，我会给出以下答案：

我不会用普通的方式这样做
表达。 这不是一个合适的
使用正则表达式。

Depending on how confident you are, I'd give this answer:

I wouldn't do it with a regular
expression. It's not an appropriate
use of regular expressions.

回复 原文
十年九夏 2024-07-15 00:58:13

是的，你可以在.Net中做到这一点！

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

您可以在此处查看！ 这是一篇精彩的文章！

Yes, you can do it in .Net!

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

You can check it here! It's a wonderful post!

回复 原文
橘虞初梦 2024-07-15 00:58:13

StackOverflow 上充满了诸如“正则表达式？不，他们不支持它。他们不能支持它。”之类的答案。

事实是，正则表达式与正则语法不再有任何关系。现代正则表达式具有递归和平衡组等功能，并且其实现的可用性正在不断增长（例如，请参阅此处的 Ruby 示例）。 在我看来，坚持认为我们领域中的正则表达式根本不是一个编程概念的旧观念只会适得其反。 我们不要因为他们的用词不再合适而憎恨他们，而是应该接受事情并继续前进。

以下是 Perl 本身的创建者 Larry Wall 的引言：

(…) 通常与我们所说的“正则表达式”有关，它们与真正的正则表达式只有很少的关系。 尽管如此，这个术语随着我们的模式匹配引擎的能力而发展，所以我不会在这里尝试对抗语言的必要性。 不过，我通常会称它们为“正则表达式”（或“regexen”，当我处于盎格鲁撒克逊心情时）。

这是一篇博客文章作者：PHP 核心开发人员之一：

由于文章比较长，这里总结一下要点：

  • 程序员使用的“正则表达式”与形式语言理论背景下的原始正则概念几乎没有共同之处。
  • 正则表达式（至少 PCRE）可以匹配所有上下文无关语言。 因此，它们还可以匹配格式良好的 HTML 和几乎所有其他编程语言。
  • 正则表达式至少可以匹配某些上下文相关语言。
  • 正则表达式的匹配是 NP 完全的。 因此，您可以使用正则表达式解决任何其他 NP 问题。

话虽如此，您可以使用以下命令将回文与正则表达式匹配：

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

...这显然与常规语法无关。
更多信息请参见：http://www.regular-expressions.info/balancing.html

StackOverflow is full of answers like "Regular expressions? nope, they don't support it. They can't support it.".

The truth is that regular expressions have nothing to do with regular grammars anymore. Modern regular expressions feature functions such as recursion and balancing groups, and the availability of their implementations is ever growing (see Ruby examples here, for instance). In my opinion, hanging onto old belief that regular expressions in our field are anything but a programming concept is just counterproductive. Instead of hating them for the word choice that is no longer the most appropriate, it is time for us to accept things and move on.

Here's a quote from Larry Wall, the creator of Perl itself:

(…) generally having to do with what we call “regular expressions”, which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I’m not going to try to fight linguistic necessity here. I will, however, generally call them “regexes” (or “regexen”, when I’m in an Anglo-Saxon mood).

And here's a blog post by one of PHP's core developers:

As the article was quite long, here a summary of the main points:

  • The “regular expressions” used by programmers have very little in common with the original notion of regularity in the context of formal language theory.
  • Regular expressions (at least PCRE) can match all context-free languages. As such they can also match well-formed HTML and pretty much all other programming languages.
  • Regular expressions can match at least some context-sensitive languages.
  • Matching of regular expressions is NP-complete. As such you can solve any other NP problem using regular expressions.

That being said, you can match palindromes with regexes using this:

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

...which obviously has nothing to do with regular grammars.
More info here: http://www.regular-expressions.info/balancing.html

回复 原文
何必那么矫情 2024-07-15 00:58:13

正如一些人已经说过的，没有一个正则表达式可以开箱即用地检测一般回文，但是如果您想检测达到一定长度的回文，您可以使用类似的东西

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1

As a few have already said, there's no single regexp that'll detect a general palindrome out of the box, but if you want to detect palindromes up to a certain length, you can use something like

(.?)(.?)(.?)(.?)(.?).?\5\4\3\2\1
回复 原文
杯别 2024-07-15 00:58:13

您也可以不使用递归来实现：

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

允许单个字符：

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

与 Perl、PCRE 配合使用

demo

对于 Java：

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

演示

You can also do it without using recursion:

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

to allow a single character:

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

Works with Perl, PCRE

demo

For Java:

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

demo

回复 原文
空‖城人不在 2024-07-15 00:58:13

现在可以用 Perl 来完成。 使用递归引用：

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

根据最后一部分修改 http://perldoc.perl.org/perlretut.html< /a>

It can be done in Perl now. Using recursive reference:

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

modified based on the near last part http://perldoc.perl.org/perlretut.html

回复 原文
与他有关 2024-07-15 00:58:13

在 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

In ruby you can use named capture groups. so something like this will work -

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

try it, it works...

1.9.2p290 :017 > palindrome?("racecar")
 => "racecar" 
1.9.2p290 :018 > palindrome?("kayak")
 => "kayak" 
1.9.2p290 :019 > palindrome?("woahitworks!")
 => nil
回复 原文
不气馁 2024-07-15 00:58:13

递归正则表达式可以做到！

如此简单且不言而喻的算法来检测包含回文的字符串：

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

在 rexegg.com/regex-递归教程解释了它是如何工作的。

它适用于任何语言，这里是一个使用 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";
}

输出

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

比较

正则表达式 ^((\w)(?:(?1)| \w?)\2)$ 做同样的工作，但是用 yes/not 代替“包含”。
PS：它使用的定义中“o”不是回文，“able-elba”连字符格式不是回文，但“ableelba”是。 将其命名为definition1。
当“o”和“able-elba”为回文时，命名为definition2。

与另一个“回文正则表达式”相比，

  • ^((.)(?:(?1)|.?)\2)$ 上面的基本正则表达式没有 \w< /code> 限制，接受“able-elba”。

  • ^((.)(?1)?\2|.)$ (@LilDevil) 使用definition2（接受“o”和“able-elba”，因此在“aaaaa”和“bbbb”字符串的识别上也有所不同）。

  • ^((.)(?1)\2|.?)$ (@Markus) 未检测到“kook”和“bbbb”

  • ^((.)(?1)*\2|.?)$ (@Csaba) 使用定义2。

注意：要进行比较，您可以在 $subjects 处添加更多单词，并为每个比较的正则表达式添加一行，

  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";

Recursive Regular Expressions can do it!

So simple and self-evident algorithm to detect a string that contains a palindrome:

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

At rexegg.com/regex-recursion the tutorial explains how it works.

It works fine with any language, here an example adapted from the same source (link) as proof-of-concept, using 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";
}

outputs

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

Comparing

The regular expression ^((\w)(?:(?1)|\w?)\2)$ do the same job, but as yes/not instead "contains".
PS: it is using a definition where "o" is not a palimbrome, "able-elba" hyphened format is not a palindrome, but "ableelba" is. Naming it definition1.
When "o" and "able-elba" are palindrones, naming definition2.

Comparing with another "palindrome regexes",

  • ^((.)(?:(?1)|.?)\2)$ the base-regex above without \w restriction, accepting "able-elba".

  • ^((.)(?1)?\2|.)$ (@LilDevil) Use definition2 (accepts "o" and "able-elba" so differing also in the recognition of "aaaaa" and "bbbb" strings).

  • ^((.)(?1)\2|.?)$ (@Markus) not detected "kook" neither "bbbb"

  • ^((.)(?1)*\2|.?)$ (@Csaba) Use definition2.

NOTE: to compare you can add more words at $subjects and a line for each compared regex,

  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";
回复 原文
余厌 2024-07-15 00:58:13

这是我对Regex Golf 的第五级（一个人，一个计划）的回答。 它适用于浏览器的正则表达式最多 7 个字符（我使用的是 Chrome 36.0.1985.143）。

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

这是最多 9 个字符的字符

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

要增加其适用的最大字符数，您需要反复将 .? 替换为 (?:(.).?\n?) ？。

Here's my answer to Regex Golf's 5th level (A man, a plan). It works for up to 7 characters with the browser's Regexp (I'm using Chrome 36.0.1985.143).

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

Here's one for up to 9 characters

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

To increase the max number of characters it'd work for, you'd repeatedly replace .? with (?:(.).?\n?)?.

回复 原文
时常饿 2024-07-15 00:58:13

实际上，使用字符串操作而不是正则表达式更容易：

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

我意识到这并不能真正回答面试问题，但你可以用它来展示你如何知道更好的完成任务的方法，而且你不是典型的“拿着锤子的人，把所有问题都看成钉子”。

It's actually easier to do it with string manipulation rather than regular expressions:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

I realize this doesn't really answer the interview question, but you could use it to show how you know a better way of doing a task, and you aren't the typical "person with a hammer, who sees every problem as a nail."

回复 原文
俏︾媚 2024-07-15 00:58:13

关于PCRE表达式（来自MizardX）：

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

你测试过吗？ 在我的 Win XP Pro 下的 PHP 5.3 上，它失败了：aaaba
实际上，我稍微修改了表达式表达式，读取：

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

我认为发生的情况是，虽然外部字符对被锚定，但剩余的内部字符对一些则不然。 这并不是完整的答案，因为虽然它错误地传递了“aaaba”和“aabaacaa”，但它确实在“aabaaca”上正确失败了。

我想知道是否有解决办法，而且，
Perl 示例（由 JF Sebastian / Zsolt 编写）是否正确通过了我的测试？

来自维也纳的 Csaba Gabor

Regarding the PCRE expression (from MizardX):

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

Have you tested it? On my PHP 5.3 under Win XP Pro it fails on: aaaba
Actually, I modified the expression expression slightly, to read:

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

I think what is happening is that while the outer pair of characters are anchored, the remaining inner ones are not. This is not quite the whole answer because while it incorrectly passes on "aaaba" and "aabaacaa", it does fail correctly on "aabaaca".

I wonder whether there a fixup for this, and also,
Does the Perl example (by JF Sebastian / Zsolt) pass my tests correctly?

Csaba Gabor from Vienna

回复 原文
马蹄踏│碎落叶 2024-07-15 00:58:13
/\A(?<a>|.|(?:(?<b>.)\g<a>\k<b+0>))\z/

它对 Oniguruma 引擎（在 Ruby 中使用）有效，

取自 Pragmatic Bookshelf

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

it is valid for Oniguruma engine (which is used in Ruby)

took from Pragmatic Bookshelf

回复 原文
思念绕指尖 2024-07-15 00:58:13

在 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
}

In Perl (see also Zsolt Botykai's answer):

$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
}
回复 原文
浸婚纱 2024-07-15 00:58:13

正如 ZCHudson< 所指出的/a>，确定某物是否是回文不能用通常的正则表达式来完成，因为回文集不是常规语言。

我完全不同意 Airsource Ltd 当他说“这不可能”时，这并不是面试官想要的答案。 在我的面试中，当我面对一个好的候选人时，我会提出这样的问题，看看当我们向他提出做错事时，他是否能找到正确的论点。 我不想雇用一个即使知道更好的方法也会试图以错误的方式做某事的人。

As pointed out by ZCHudson, determine if something is a palindrome cannot be done with an usual regexp, as the set of palindrome is not a regular language.

I totally disagree with Airsource Ltd when he says that "it's not possibles" is not the kind of answer the interviewer is looking for. During my interview, I come to this kind of question when I face a good candidate, to check if he can find the right argument when we proposed to him to do something wrong. I do not want to hire someone who will try to do something the wrong way if he knows better one.

回复 原文
油焖大侠 2024-07-15 00:58:13

你可以用 perl 做的事情： http://www.perlmonks.org/?node_id=577368

something you can do with perl: http://www.perlmonks.org/?node_id=577368

回复 原文
抽个烟儿 2024-07-15 00:58:13

我会向面试官解释，由回文组成的语言不是常规语言，而是上下文无关的。

匹配所有回文的正则表达式将是无限的。 相反，我建议他将自己限制在可以接受的最大回文大小； 或者，如果需要所有回文，则至少使用某种类型的 NDPA，或者仅使用简单的字符串反转/等于技术。

I would explain to the interviewer that the language consisting of palindromes is not a regular language but instead context-free.

The regular expression that would match all palindromes would be infinite. Instead I would suggest he restrict himself to either a maximum size of palindromes to accept; or if all palindromes are needed use at minimum some type of NDPA, or just use the simple string reversal/equals technique.

回复 原文
怀念你的温柔 2024-07-15 00:58:13

在用完捕获组之前，您可以使用正则表达式做的最好的事情：

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

这将匹配长度最多为 19 个字符的所有回文。

以编程方式求解所有长度是微不足道的：

str == str.reverse ? true : false

The best you can do with regexes, before you run out of capture groups:

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

This will match all palindromes up to 19 characters in length.

Programatcally solving for all lengths is trivial:

str == str.reverse ? true : false
回复 原文
吃颗糖壮壮胆 2024-07-15 00:58:13

我还没有内联评论的代表，但 MizardX 提供并由 Csaba 修改的正则表达式可以进一步修改以使其在 PCRE 中工作。 我发现的唯一失败是单字符字符串，但我可以单独测试它。

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

如果您可以使其在任何其他字符串上失败，请发表评论。

I don't have the rep to comment inline yet, but the regex provided by MizardX, and modified by Csaba, can be modified further to make it work in PCRE. The only failure I have found is the single-char string, but I can test for that separately.

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

If you can make it fail on any other strings, please comment.

回复 原文
赤濁 2024-07-15 00:58:13
#!/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";

#!/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";
回复 原文
落花随流水 2024-07-15 00:58:13

从自动机理论来看，不可能匹配任何长度的回文（因为这需要无限量的内存）。 但匹配固定长度的回文是可能的。
假设可以编写一个正则表达式来匹配长度 <= 5 或 <= 6 等的所有回文，但不匹配 >= 5 等，其中上限不清楚

From automata theory its impossible to match a paliandrome of any lenght ( because that requires infinite amount of memory). But IT IS POSSIBLE to match Paliandromes of Fixed Length.
Say its possible to write a regex that matches all paliandromes of length <= 5 or <= 6 etc, but not >=5 etc where upper bound is unclear

回复 原文
执妄 2024-07-15 00:58:13

在 Ruby 中，您可以使用 \b(?'word'(?'letter'[az])\g'word'\k'letter+0'|[az])\b 来匹配回文诸如a、dad、radar、racecar 和 redivider 之类的词。 ps ：此正则表达式仅匹配奇数个字母长的回文单词。

让我们看看这个正则表达式如何匹配雷达。 单词边界 \b 匹配字符串的开头。 正则表达式引擎输入捕获组“word”。 [az] 匹配 r，然后将其存储在递归级别零的捕获组“letter”的堆栈中。 现在正则表达式引擎进入组“word”的第一次递归。 (?'letter'[az]) 在递归级别 1 匹配并捕获 a。 正则表达式进入组“word”的第二个递归。 (?'letter'[az]) 在二级递归处捕获 d。 在接下来的两次递归中，该小组在第三层和第四层捕获了 a 和 r。 第五次递归失败，因为字符串中没有剩余字符可供 [az] 匹配。 正则表达式引擎必须回溯。

正则表达式引擎现在必须尝试“word”组内的第二种选择。 正则表达式中的第二个 [az] 与字符串中的最后一个 r 匹配。 引擎现在从成功的递归中退出，返回到第三个递归的一级。

匹配 (&word) 后，引擎到达 \k'letter+0'。 反向引用失败，因为正则表达式引擎已到达主题字符串的末尾。 于是又再次倒退。 现在第二个选项与 a 匹配。 正则表达式引擎从第三次递归退出。

正则表达式引擎再次匹配 (&word)，需要再次尝试反向引用。 反向引用指定 +0 或当前递归级别，即 2。在此级别，捕获组匹配 d。 反向引用失败，因为字符串中的下一个字符是 r。 再次回溯，第二个选项匹配 d。

现在，\k'letter+0' 匹配字符串中的第二个 a。 这是因为正则表达式引擎已返回到第一个递归，在此期间捕获组与第一个 a 匹配。 正则表达式引擎退出第一个递归。

正则表达式引擎现在回到了所有递归之外。 即这个级别，捕获组存储了r。 反向引用现在可以匹配字符串中的最后一个 r。 由于引擎不再位于任何递归内部，因此它继续处理组之后的正则表达式的其余部分。 \b 匹配字符串末尾。 到达正则表达式的末尾，雷达作为整体匹配返回。

In Ruby you can use \b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b to match palindrome words such as a, dad, radar, racecar, and redivider. ps : this regex only matches palindrome words that are an odd number of letters long.

Let's see how this regex matches radar. The word boundary \b matches at the start of the string. The regex engine enters the capturing group "word". [a-z] matches r which is then stored in the stack for the capturing group "letter" at recursion level zero. Now the regex engine enters the first recursion of the group "word". (?'letter'[a-z]) matches and captures a at recursion level one. The regex enters the second recursion of the group "word". (?'letter'[a-z]) captures d at recursion level two. During the next two recursions, the group captures a and r at levels three and four. The fifth recursion fails because there are no characters left in the string for [a-z] to match. The regex engine must backtrack.

The regex engine must now try the second alternative inside the group "word". The second [a-z] in the regex matches the final r in the string. The engine now exits from a successful recursion, going one level back up to the third recursion.

After matching (&word) the engine reaches \k'letter+0'. The backreference fails because the regex engine has already reached the end of the subject string. So it backtracks once more. The second alternative now matches the a. The regex engine exits from the third recursion.

The regex engine has again matched (&word) and needs to attempt the backreference again. The backreference specifies +0 or the present level of recursion, which is 2. At this level, the capturing group matched d. The backreference fails because the next character in the string is r. Backtracking again, the second alternative matches d.

Now, \k'letter+0' matches the second a in the string. That's because the regex engine has arrived back at the first recursion during which the capturing group matched the first a. The regex engine exits the first recursion.

The regex engine is now back outside all recursion. That this level, the capturing group stored r. The backreference can now match the final r in the string. Since the engine is not inside any recursion any more, it proceeds with the remainder of the regex after the group. \b matches at the end of the string. The end of the regex is reached and radar is returned as the overall match.

回复 原文
噩梦成真你也成魔 2024-07-15 00:58:13

下面是 PL/SQL 代码，它使用正则表达式判断给定字符串是否是回文：

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;

here is PL/SQL code which tells whether given string is palindrome or not using regular expressions:

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;
回复 原文
帅气称霸 2024-07-15 00:58:13
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";
}

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";
}
回复 原文
树深时见影 2024-07-15 00:58:13

此正则表达式将检测最多 22 个字符的回文，忽略空格、制表符、逗号和引号。

\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

在这里玩一下：https://regexr.com/4tmui

我在这里写了一个关于如何得到它的解释： https://medium .com/analytics-vidhya/coding-the-impossible-palindrome- detector-with-a-regular-expressions-cd76bc23b89b

This regex will detect palindromes up to 22 characters ignoring spaces, tabs, commas, and quotes.

\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

Play with it here: https://regexr.com/4tmui

I wrote an explanation of how I got that here: https://medium.com/analytics-vidhya/coding-the-impossible-palindrome-detector-with-a-regular-expressions-cd76bc23b89b

回复 原文
写下不归期 2024-07-15 00:58:13

对 Airsource Ltd 方法的稍微改进，用伪代码表示：

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

A slight refinement of Airsource Ltd's method, in pseudocode:

WHILE string.length > 1
    IF /(.)(.*)\1/ matches string
        string = \2
    ELSE
        REJECT
ACCEPT
回复 原文
~没有更多了~

关于作者

少女七分熟

暂无简介

0 文章
0 评论
21 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

不再见

文章 0 评论 0

真是无聊啊

文章 0 评论 0

樱娆

文章 0 评论 0

浅语花开

文章 0 评论 0

烛光

文章 0 评论 0

绻影浮沉

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文