A good method to solve this problem is to determine the length L
of a longest common subsequence (maximal matching) for the input and
its reverse.  The answer then is N - L.  An alternative approach is
to match a prefix of the string with the reverse of a postfix.

The length of a longest common subsequence can be determined
by dynamic programming.  A triangular table can be constructed,
of which only two rows need to be stored.  The complexity
is then O(N) space and O(N^2) time.

• Re:Why wa, not memory limit error? (60) anne2277 2005-06-30 11:20:48
  • Re:Why wa, not memory limit error? (98) anne2277 2005-06-30 12:10:00
• Re:Why wa, not memory limit error? (224) hot 2005-11-27 14:00:32
  • ....... (234) frkstyc 2005-11-27 14:31:35
    • Re:....... (65) hot 2005-11-30 19:04:01
  • Please don't fish me... (71) ejkim7199 2006-07-09 13:38:03