Databases
StackOverflow2013
Postsdbo
POHow does this Java regex detect palindromes?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow does this Java regex detect palindromes?
    primarykey
    data
    text
    <blockquote> <p><sup><em>This is the third part in a series of educational regex articles. It follows <a href="https://stackoverflow.com/questions/3627681/how-does-this-regex-find-triangular-numbers/">How does this regex find triangular numbers?</a> (where nested references is first introduced) and <a href="https://stackoverflow.com/questions/3644266/how-can-we-match-an-bn-with-java-regex/">How can we match a^n b^n with Java regex?</a> (where the lookahead "counting" mechanism is further elaborated upon). This part introduces a specific form of nested assertion, which when combined with nested references allows Java regex to match what most people believe is "impossible": palindromes!!</em></sup></p> </blockquote> <p>The language of palindromes is non-<a href="http://en.wikipedia.org/wiki/Regular_language" rel="nofollow noreferrer">regular</a>; it's actually <a href="http://en.wikipedia.org/wiki/Context-free_language" rel="nofollow noreferrer">context-free</a> (for a given alphabet). That said, modern regex implementation recognizes more than just regular languages, and Perl/PCRE's recursive patterns and .NET's balancing groups can readily recognize palindromes (see: <em>Related Questions</em>).</p> <p>However, Java's regex engine supports neither of these "advanced" features. And yet "someone" <sup>(<em>*wink*</em>)</sup> managed to write the following regex which seems to do the job just fine (<a href="http://ideone.com/lWCRF" rel="nofollow noreferrer">see also on ideone.com</a>):</p> <pre><code>public class Palindrome { // asserts that the entirety of the string matches the given pattern static String assertEntirety(String pattern) { return "(?&lt;=(?=^pattern$).*)".replace("pattern", pattern); } public static void main(String[] args) { final String PALINDROME = "(?x) | (?:(.) add)+ chk" .replace("add", assertEntirety(".*? (\\1 \\2?)")) .replace("chk", assertEntirety("\\2")); System.out.println(PALINDROME); // (?x) | (?:(.) (?&lt;=(?=^.*? (\1 \2?)$).*))+ (?&lt;=(?=^\2$).*) String[] tests = { "", // true "x", // true "xx", // true "xy", // false "xyx", // true "xxx", // true "xxyx", // false "racecar", // true "step on no pets", // true "aManaPlanaCanalPanaMa", // true "this is impossible", // FALSE!!! }; for (String test : tests) { System.out.printf("[%s] %s%n", test, test.matches(PALINDROME)); } } } </code></pre> <p>So this seems to work, but how?</p> <h3>References</h3> <ul> <li><a href="http://download.oracle.com/javase/6/docs/api/java/util/regex/Pattern.html" rel="nofollow noreferrer"><code>java.util.regex.Pattern</code></a></li> <li><a href="http://www.regular-expressions.info/freespacing.html" rel="nofollow noreferrer">regular-expressions.info/Freespacing <code>(?x)</code></a>, <a href="http://www.regular-expressions.info/lookaround.html" rel="nofollow noreferrer">Lookarounds <code>(?=…)</code>/<code>(?&lt;=…)</code></a>, etc.</li> </ul> <hr> <blockquote> <h2><em>COMMON SENSE ALERT!!!</em></h2> <p>This is not the best way to detect palindromes; it's <code>O(N^3)</code>at best. Performing this detection in a more general purpose programming language is both more efficient and more straightforward.</p> <p>You wouldn't want to <em>use</em> regex to detect palindromes for the same reasons you wouldn't want to <em>use</em> regex to find prime numbers. That said, you would <em>study</em> how a non-recursive non-balancing group regex can detect palindromes for the same reasons you would <em>study</em> how a regex can be used for primality testing: it's fun, it's challenging, it's educational.</p> </blockquote> <h3>Related questions</h3> <ul> <li><a href="https://stackoverflow.com/questions/233243/how-to-check-that-a-string-is-a-palindrome-using-regular-expressions">How to check that a string is a palindrome using regular expressions?</a> - it's "impossible"! (unless...)</li> <li><a href="https://stackoverflow.com/questions/52002/how-to-check-if-the-given-string-is-palindrome">How to check if the given string is palindrome?</a> - non-regex solutions in many languages</li> <li><a href="https://stackoverflow.com/questions/2795065/how-to-determine-if-a-number-is-a-prime-with-regex">How to determine if a number is a prime with regex?</a></li> </ul>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USpolygenelubricants
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow does this Java regex detect palindromes?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow does this Java regex detect palindromes?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow does this Java regex detect palindromes?
      1. This table or related slice is empty.
      1. VTUpMod
    1. CODiscussion of the series: http://meta.stackexchange.com/questions/62695/permission-to-start-a-series-of-advanced-regex-articles ; Also, no doubt there are typos/mistakes in this long article. Please leave comments and feedbacks as I do plan to continually revise.
      singulars
      1. POHow does this Java regex detect palindromes?
      1. USpolygenelubricants
    2. COI would just like to mention that the use of regular expressions to detect palindromes is a particularly silly idea. There are much better ways to do it. By all means use this to educate yourself on regular expressions but part of that education is knowing when _not_ to use them. Not trying to rain on your parade, @poly, I'm sure this is a good article :-)
      singulars
      1. POHow does this Java regex detect palindromes?
      1. USpaxdiablo
    3. CO@paxdiablo: This article isn't really about palindromes, for almost the same reason that fables aren't really about talking lions and/or singing donkeys. There are morals and lessons to be had here, and looking at this as just a palindrome detection regex merely scratches the surface.
      singulars
      1. POHow does this Java regex detect palindromes?
      1. USpolygenelubricants
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload