新近在网友一篇博文中看到他提及其一个朋友用了后缀数组、后缀树和EKM算法取字符串中的最长回文子串（即从左到右读和从右到左读都一样的字符串），这些算法我都没有听说过，望其项背中……打算某天去找些资料来学习一下。感叹之余，想想自己如果遇到这题，有什么好的办法吗？YY中，一个想法浮了出来，DP
细想起来，字符串中每个字符都是一个最基本的长度为1的回文，然后相邻的相同字符串也同样构成回文，然后每个字符可以通过前一个字符的回文集合确定自己的集合。具体起来，先分配字符串长度的集合set[n]，迭代到第i个字符时，首先将位置索引i自己放入set[i]，然后如果i与i-1（若i非第一个字符）相同，则把i-1也放入set[i]，然后在遍历set[i-1]中的所有位置索引j，检查i与j-1们是否相同，若相同，则同样构成回文，把j-1也放入set[i]，迭代进行直至字符串结尾即告结束。剩下的工作只需要简单遍历set，找出长度最长的那个回文即可。
转换方程： set[i] = {i} | {i-1: if i>1 && a[i-1]==a[i]} | {k-1: i>1 && k in set[i-1] && a[k-1]==a[i]}
public String getLongest(String str) { if(str.length()<2) return str; Set[] dp = new Set[str.length()]; dp[0] = new HashSet(); dp[0].add(new Integer(0)); for(int i=1; i<dp.length; i++) { dp[i] = new HashSet(); dp[i].add(new Integer(i)); if(str.charAt(i)==str.charAt(i-1)) dp[i].add(new Integer(i-1)); Iterator it = dp[i-1].iterator(); while(it.hasNext()) { int at = ((Integer)it.next()).intValue(); if(at>0&&str.charAt(at-1)==str.charAt(i)) dp[i].add(new Integer(at-1)); } } String ans = ""; int max = 0; for(int i=0; i<dp.length; i++) { Iterator it = dp[i].iterator(); while(it.hasNext()) { int at = ((Integer)it.next()).intValue(); if(max<i-at+1) { max = i-at+1; ans = str.substring(at, i+1); } } } return ans; }
如果字符串比较长而且回文很多，DP的内存开销可能会比较大，所以有空还是要多学些高级的算法，来提升自己，恩。
