用动态规划算法对最大子串问题的java实现

goodluck

<p >最大字串问题描述大概就是给定2个字符串，找出他们两个共有的最长字符串。比如一个是"tabcfg"另外一个"abckj"那么最大子串就是"abc".<p >动态规划算法最重要的就是分解问题，找出递归。说一下我的思考思路，首先拿到2个字符串，如何找到最长子串呢？<p >1.假设他们(字符串a,b)的头字母不相同的话，那么分别去掉首字母比较，也就是说用a.subString(1)和b比较，用b.subString(1)和a比较，最长子字符串没变吧？答案是肯定的。ok递归出现了，结束条件就是有一个字符串变空，返回值就是a和b的最长子串。<p >b.假设他们头字母相同，那么一直比较下去，知道两者的第n个字母不相同，然后把前n-1个字母存为子字符串c,把a.subString(n)和b.subString(n)的最长子字符串记为d,那么返回c和d长的一个。<p >也许有人说应该从后面往前面比较，找到相同的然后一个个再往前比，其实道理都是一样的，关键要找到分解问题的方法。这里只是抛砖引玉，下面是具体的java实现。<p ><p >import java.util.HashMap;<p >import java.util.Map;<p ><p >/**<p >* @author HEACK<p >*<p >*/<p >public class CompareStr {<p ><p >        /**<p >        * @param args<p >        */<p >        public static void main(String[] args) {<p >                // TODO Auto-generated method stub<p >                String str1 = <p >                       "asldkfjiowerbasdfjlkajlfj<p >                        aldjoiernzxcvasldkfjiowerbasdfjlkajlfjaldjoiernzxcvasldkfjiow<p >                        erbasdfjlkajlfjaldjoiernzxcv";<p >                String str2 =<p >                        "asdkjfolasdnflxckvjlasdofiwiuerjalskdfnznxcmvlaskdfjalsdfjl<p >                         asdjfaskdfjasiuejrlasdf";<p ><p >                //String str2 = "abc happyies dutcbirthday peter";<p >                CompareStr cj = new CompareStr();<p >                System.out.println(cj.getLongestString(str1,str2));<p ><p >        }<p ><p >        private boolean isEmpty(String str) {<p >                return str == null || str.trim().length() == 0;<p >        }<p >        private Map<String, String> map = new HashMap();<p ><p >        private String getLongestString(String str1, String str2) {<p >                if (isEmpty(str1) || isEmpty(str2)) {<p >                        return "";<p >                }<p >                StringBuffer key = new StringBuffer();<p >                key.append(str1).append("&&").append(str2);<p >                if (map.containsKey(key.toString())) {<p >                        return map.get(key.toString());<p >                }<p >                StringBuffer longestStr = new StringBuffer();<p >                char[] str1List = str1.toCharArray();<p >                char[] str2List = str2.toCharArray();<p >                int i = 0;<p >                for (i = 0; i < str1List.length && i < str2List.length; i++) {<p >                        if (str1List == str2List) {<p >                                longestStr.append(str1List);<p >                        } else {<p >                                break;<p >                        }<p >                }<p >                String subStr1 = str1.substring(i);<p >                String subStr2 = str2.substring(i);<p >                if (i == 0) {<p >                        String retStr1 = getLongestString(subStr1.substring(1), subStr2);<p >                        String retStr2 = getLongestString(subStr1, subStr2.substring(1));<p >                        String returnStr = retStr1.length() >= retStr2.length() ? retStr1 : retStr2;<p >                        map.put(key.toString(), returnStr);<p >                        return returnStr;<p >                } else {<p >                        String retStr = getLongestString(subStr1, subStr2);<p >                        String returnStr = retStr.length() >= longestStr.toString().length() ? retStr<p >                                        : longestStr.toString();<p >                        map.put(key.toString(), returnStr);<p >                        return returnStr;<p >                }<p >        }<p ><p >}HashMap用来存储已经计算过的字符串，用空间换时间。代码当然还可以优化，您也可以一试身手哦。<p >< align=right></P><p align="center"></p></p>