Simple linear palindrom finding algorithm

A simple algorithm designed by Manacher in 1975. It scans the longest palindrom in left-to-right fashion.
int palindrom_odd(const char *st, int n, int *p) {
  int a = 0, m = 1;
  p[0] = 1;
  for (int i = 1; i < n; ++i) {
      int w = 1;
      if (a + p[a] > i ) 
          w = std::min(p[a + a -i], a-i+p[a]);
      while(i >= w && i+w < n && st[i+w] == st[i-w])
          ++w;
      if (w + i > a + p[a])
        a = i;
      p[i] = w;
      m = std::max (w, m);
  }
  return m + m – 1;
}

The algorithm is quite straightforward. If you take the two lines in bold away, you will immediately see that it becomes a naive palindrom finding algorithm. What are the two lines for?
Assuming you are computing the radius of index i and there is some index a < i such that p[a] + a > i.
If the palindrom centered at index 2a-i is covered by the range [a-p[a], a+p[a]], then by symetric property, the radius of index i cannot be larger than p[2a-i]. So it is enough for us to compute p[i] starting from min(p[a + a -i], a-i+p[a]).
Why the algorithm is linear? For each comparison, you either extend the coverage of a+p[a] (on sucess) or finish the computation of p[i] immediately.

Is this algorithm fast? Not really, a naive algorithm most probably will beat it in practice. The algorithm is good for interview since it is simple and nature. It is much faster than a naive algorithm in some extreme case (e.g. a lot of 0’s followed by a single 1, in this case, the running time of a naive algorithm is \Theta(n^2))

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s