dp:最长不重复子串，最长公共子串

public class Solution {
    public int lengthOfLongestSubstring(String str) {
        if(str==null||str.length()==0)
            return 0;
        char[] cs = str.toCharArray();
        int[] charMap = new int[256];
        Arrays.fill(charMap , -1);
        int max = 0;
        int left = 0;
        for(int i=0;i<cs.length;i++){
            if(charMap[cs[i]]>=left)
                left = charMap[cs[i]]+1;
            int tmp = i-left+1;//当前最大长度
            if(tmp>max)
                max = tmp; //之前的最大长度
            charMap[cs[i]]=i;
        }
        return max;
    }
}

package com.ryan.offer;

public class GonggongXuelie {

    public static void main(String[] args) {
        String str1="bbcada";
        String str2="gscadtre";
        System.out.println(getLongestCommonSubstring(str1,str2));

    }
    public static String getLongestCommonSubstring(String str1, String str2){
       
        if(str1==null||str2==null)
            return null;
        //find out the bigger string and the smaller one
        String big = str1.length()>=str2.length()?str1:str2;
        String small = str1.length()<str2.length()?str1:str2;
        //get the end of the longest common substring in small
        int[] help = new int[small.length()];
        int end = 0;
        int length = 0;
        for(int i=0;i<big.length();i++){
            for(int j=small.length()-1;j>=0;j--){
                if(big.charAt(i)==small.charAt(j)){
                    if(j==0)
                        help[j]=1;
                    else{
                        help[j]=help[j-1]+1;
                        if(help[j]>length){
                            length = help[j];
                            end = j;
                        }
                    }
                }else
                    help[j]=0;
            }
        }
        //get the longest common substring and return it
        if(length==0)
            return null;
        else
            return small.substring(end-length+1,end+1);
    }
}