最长公共子串LCS,JAVA版

直接看代码：

package oj3;

import java.util.Arrays;
import java.util.Scanner;

//最长公共子串
public class Main21 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String[] strArray = str.split("\\s+");
        String str1 = strArray[0].toLowerCase();
        String str2 = strArray[1].toLowerCase();
        String commonStr = getCommonLongestStr(str1, str2);
        System.out.print(commonStr.length());
        scanner.close();
    }

    private static String getCommonLongestStr(String str1, String str2) {
        int xlen = str1.length(); // 横向长度
        int[] tmp = new int[xlen]; // 保存矩阵的上一行
        int[] arr = new int[xlen]; // 当前行
        int ylen = str2.length(); // 纵向长度
        int maxelement = 0; // 矩阵元素中的最大值
        int pos = 0; // 矩阵元素最大值出现在第几列
        for (int i = 0; i < ylen; i++) {// i为列数
            String s1 = str2.substring(i, i + 1);
            Arrays.fill(arr, 0);
            for (int j = 0; j < xlen; j++) {// j为行数
                String s2 = str1.substring(j, j + 1);
                if (s1.equals(s2)) {
                    if (j == 0)
                        arr[j] = 1;
                    else
                        arr[j] = tmp[j - 1] + 1;
                    if (arr[j] > maxelement) {
                        maxelement = arr[j];
                        pos = j;
                    }
                }
            }
            System.arraycopy(arr, 0, tmp, 0, arr.length);
        }
        return str1.substring(pos - maxelement + 1, pos + 1);
    }
}