题解 | #最长公共子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        if (str1 == null || str2 == null) {
            return "";
        }

        int i = str1.length();
        int j = str2.length();
        int max = 0;
        // 临时大小
        int tmp = 0;
        String maxStr = "";
        StringBuilder tmpStr = new StringBuilder();

        for (int k = 0; k < i; k++) {
            int tmpK = k;
            int tmph = 0;
            boolean haveSame = false;
            for( int h = 0; h<j; h++) {

                char hK = str2.charAt(h);

                if(str1.charAt(tmpK) == hK) {
                    tmp ++;
                    tmpStr.append(str1.charAt(tmpK));
                    if(tmp >= max) {
                        max =tmp;
                        maxStr = tmpStr.toString();
                    }
                    tmpK++;
                    if(tmpK>=i ) {
                        break;
                    }
                    if(!haveSame) {
                        tmph = h;
                    }
                    haveSame = true;
                }else {
                    tmp = 0;
                    if(tmpStr.length() > 0) {
                        tmpStr = new StringBuilder();
                    }
                    tmpK = k;
                    if(haveSame) {
                        h = tmph;
                        haveSame = false;
                    }
                }
            }
            tmp =0;
            tmpStr = new StringBuilder();
        }
        return maxStr;
    }
}