Posts tagged with 'palindrome'

PCPlus 322: Finding palindromic substrings

For June 2012, it was back to some computer science. The problem posed was: given a string of characters, find the longest subsequence in that string that is a palindrome. So, taking the example ‘abbaca’ (hey, computer science is full of nonsense strings), it’s fairly obvious there are two palindromic substrings – ignoring those of length 1, which are just silly – ‘abba’ and ‘aca’. The article delves into some algorithms for solving this problem, from the O(n^2) version to a more intricate O(n) one...