0

I have a file with a bunch of strings, one on each line. I want to find and print a string only if it contains a palindrome and that palindrome is not between brackets. Examples:

abba[cdef]gh    # print
abcd[effe]gh    # do not print

I currently have a one-liner that prints a line if the string is a palindrome

awk 'BEGIN { system("perl -lne \"print if length == 4 && reverse eq \\$_\" " ARGV[1]) }' words.txt

modified from here.

I'm thinking of using sed to remove everything between the brackets, then evaluate the remaining for palindromes.

Any other ideas on how to accomplish this in one line?

4
  • Can't you just use negative lookarounds e.g. perl -ne 'print if /(?<!\[)(.)(.)$2$1(?!\])/' ? Sep 15, 2018 at 17:09
  • how long does the palindrome have to be? (nothing) would be a simplistic one; a would be a simple one, aa another...
    – Jeff Schaller
    Sep 15, 2018 at 18:16
  • Just a question: why does the solution have to fit in one line?
    – Jeff Schaller
    Sep 15, 2018 at 18:17
  • The palindrome can be of any length. In the example I used four. It does not necessarily need to fit in one line Sep 15, 2018 at 21:56

3 Answers 3

1

To find all¹ the palindromes of 3 or more characters not inside [...]:

$ echo 'cac[ada]abacab' | perl -nle '
    while (/\[.*?\]|(?=(([^][])(?1)\2|[^][]?))./g) {
      print $1 if length $1 >= 3
    }'
cac
aba
bacab
aca

(note that it assumes single-byte characters, add -Mopen=locale for the locale definition of characters).

The core of the palindrome matching is a recursive regular expression. A palindrome is matched as either the empty string or a single character or a pair of matching characters with another palindrome in between. That would be ((.)(?1)\2|.?), where (?1) does the recursive part (matches what's inside the first part of (), except that here we replace . with [^][] (any character other than ] and [).

When matching all occurrences with /.../g, perl searches for the next occurrence after the end of the first one, so if we had \[.*?\]|(([^][])(?1)\2|[^][]?), we would not find bacab in abacab because it would first find aba, and then resume searching after that aba. So here instead, we match (?=(palindrome)). which matches a single character (.) provided it's at the start of a palindrome which is then captured in $1. That means we resume searching after that single character.


¹ Strictly speaking, it finds the longest (of 3 characters or more) palindromes at every position in the string, skipping the [...]s, so it may not find all the occurrences. For instance in ababa, it would find ababa in first position, bab in third position, aba in second position, but not aba in first position.

1

How about a one-liner? Use the bracketed word as the field separator:

perl -F'\[.*?\]' -le 'for $word (@F) {if ($word eq reverse $word) {print; break}}' file

A couple of edge cases not considered here:

  • It does not look at string length
  • It does not look to find a palindrome within the word: the whole word must be a palindrome.
0

While [...] could be filtered out in advance it may be more sensible to use a lex-like scanner to walk the line:

#!/usr/bin/env perl
use strict;
use warnings;
LINE: while (readline) {    # for each line (files or stdin)
    LEX: {
        # skip any [] or [...] bits
        redo LEX if m{ \G \[ [^\]]* \] }cgx;
        # two or more not-[ not-vertical-whitespace (\r, \n) chars
        if (m{ \G ([^\[\v]{2,}) }cgx) {
            # palindrome? print the whole line
            if ( $1 eq reverse $1 ) {
                print;
                next LINE;
            }
            # may be more to come...
            redo LEX;
        }
        # advance the lexer a single character
        redo LEX if m{ \G . }cgx;
        # oh it's the end of the line as we know it
    }
}

Which with an expanded test case for various edge conditions:

% < input
abba[cdef]gh    # print
abcd[effe]gh    # do not print
[effe]f00f
asdf[]prinirp
a[]b[]edgegde
% perl palin < input
abba[cdef]gh    # print
[effe]f00f
asdf[]prinirp
a[]b[]edgegde
% 

This could easily be adapted to ignore trailing comments or other such input.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .