Palindrome Iteration

gistfile1.md

Discovered an interesting algorithm for finding longest palindrome by playing with sequences in a text editor. Anyone know if there's a name for this algorithm?

Worst running time is O(n^2), which is better than the naive implementation of O(n^3) but not as efficient as some O(n) implementations (http://www.akalin.cx/longest-palindrome-linear-time). In general, assuming a non-pathological case, running time is around 2n * m where n is the length of the string and m is the mean length of all palindromes. For non-pathological cases (i.e. human sentences), n is often logarithmic (log n) and fast approaches 1 as n increases. This puts the average case complexity at around n log n and best-case n.

Developed as a solution to: http://www.therubygame.com/challenges/4

Algorithm

Original hand-work to discover a pattern:

x - hit
. - miss

a/b/c: (i.e. 1/2/2)
  a: scan size (max size of linked list to scan/compare)
  b: max size of palindrome -- a*2 / (c%2)
  c: num shifts of n to the right (iterations)

m:         unclebob
n: bobelcnu

m:         unclebob         [u]
n:  bobelcnu                [u]
           x                1/1/1

m:         unclebob         u [n]
n:   bobelcnu               [u] u
            .               1/2/2

m:         unclebob         u [nc]
n:    bobelcnu              c [nu]
            ..              2/3/3

m:         unclebob         un [cl]
n:     bobelcnu             lc [nu]
             ..             2/4/4

m:         unclebob         un [cle]
n:      bobelcnu            le [cnu]
             ...            3/5/5

m:         unclebob         unc [leb]
n:       bobelcnu           bel [cnu]
              ...           3/6/6

m:         unclebob         unc [lebo]
n:        bobelcnu          obe [lcnu]
              x...          4/7/7

m:         unclebob         uncl [ebob]
n:         bobelcnu         bobe [lcnu]
               ....         4/8/8

m:         unclebob         uncl [ebob]
n:          bobelcnu        bob [elcn] u
               ....         4/7/9

m:         unclebob         uncle [bob]
n:           bobelcnu       bob [elc] un
                ...         3/6/10

m:         unclebob         uncle [bob]
n:            bobelcnu      bo [bel] cnu
                x..         3/5/11

m:         unclebob         uncleb [ob]
n:             bobelcnu     bo [be] lcnu
                 ..         2/4/12

m:         unclebob         uncleb [ob]
n:              bobelcnu    b [ob] elcnu
                 xx         2/3/13

m:         unclebob         unclebo [b]
n:               bobelcnu   b [o] belcnu
                  .         1/2/14

m:         unclebob         unclebo [b]
n:                bobelcnu  [b] obelcnu
                  x         1/1/15

Diagrams used to identify pattern and convert to code:

v a                    m                    n
- -                    -                    -
  unclebob -           []                   []

u nclebob  -           [u]                  [u]
  v = "u"; m.push(v); n.unshift(m.first)

n clebob.  -         u [n]                n [u]
  v = "n"; m.shift; m.push(v)

c lebob..  -         u [nc]               c [nu]
  v = "c"; m.push(v); n.unshift(m.first) # repeated from above

l ebob...  -        un [cl]              lc [nu]
  v = "l"; m.shift; m.push(v) # repeated from above (see how it alternates?)

e bob....  -        un [cle]             el [cnu]
b ob.....  -       unc [leb]            bel [cnu]
o b......  -       unc [lebo]           obe [lcnu]
b .......  -      uncl [ebob]          bobe [lcnu]
. .......  -      uncl [ebob.]         .bob [elcnu]
. .......  -     uncle [bob..]        ..bob [elcnu]
. .......  -     uncle [bob...]       ...bo [belcnu]
. .......  -    uncleb [ob....]      ....bo [belcnu]
. .......  -    uncleb [ob.....]     .....b [obelcnu]
. .......  -   unclebo [b......]    ......b [obelcnu]
. .......  -   unclebo [b.......]   ....... [bobelcnu]
. .......  -  unclebob [........]  ........ [bobelcnu]

You can use nil's to represent '.' in the n list or you can compact them out; they are an artifact of pushing onto the end of the list once your original source list is empty. You could also pop no longer needed values from the n list (to match the first hand-work section above) but they don't get in the way and just increase complexity.

What's interesting from the pattern above, is that, if the implementation language efficiently supports doubly linked lists or rotate[r,l] on fixed-size arrays, you can create two lists that are twice the length of the string and just alternate between rotatel(m) and rotater(n). However, if you have efficient character-by-character access (i.e. via pointers), you could just iterate over the original string in different directions. meh.

Implementation

Code was not written to be easy to follow. I might create a easy to follow version at a later date. Ruby (Array based)

def find_longest_palindrome(string)
  # works for raw array, just remove pack/unpack
  a, m, n, l = string.unpack("U*"), [], [], [0, []]
  (1..l.size*2).each do |i|
    m.push(*a.shift); i % 2 == 1 ? n.unshift(m.first) : m.shift
    x = n.dup; t = m.take_while { |v| v == x.shift }
    len = t.size*2-(i%2)
    l = [len, t.reverse + t.drop(len%2)] if len > l[0]
  end

  l[1].pack("U*")
end

Ruby (String based)

def find_longest_palindrome(string)
  a, m, n, l, p = string, '', '', 0, ''
  (1..a.size*2).each do |i|
    m << a.slice!(0,1); i % 2 == 1 ? n.insert(0, m[0,1]) : m.slice!(0)
    t = ''; 0.upto(m.size-1) { |i| m[i] == n[i] ? t << m[i] : break }
    len = t.size*2 - (i % 2)
    l, p = len, t.reverse + (t.slice!(0, len % 2) && t) if len > l
  end
  p
end

Unfortunately, pushing and popping arrays or strings is very slow. As a solution to therubygame challenge, the following solution runs much faster due to optimizations in the underlying regular expression library:

# http://www.therubygame.com/challenges/4/submissions/13397
def find_longest_palindrome(string)
  smax = string.bytesize
  [/(.)(.)(.).?\3\2\1/, /(.)(.).?\2\1/, /(.).?\1/, /./].each do |r|
    i, l, o = 0, 0, nil
    while md = string.match(r, i)
      b, e = md.offset(0); i = b + 1
      b, e = b-1, e+1 while b > 0 && e < smax && string.getbyte(b-1) == string.getbyte(e)
      l, o = e-b, b if e-b > l
    end
    return string[o,l] if o
  end
  ""
end