最长公共子串

链接

给定两个字符串str1和str2,输出两个字符串的最长公共子串,如果最长公共子串为空,输出-1。

import java.util.Scanner;

public class Main {

    private static String solve(String str1, String str2) {
        int maxLenght = 0, maxIndex = 0;

        int row = 0, col = str2.length() - 1;

        while (row < str1.length() && col >= 0) {

            int dp = 0;
            int x = row, y = col;

            while (x < str1.length() && y < str2.length()) {
                dp = str1.charAt(x) == str2.charAt(y) ? dp + 1 : 0;

                if (dp > maxLenght) {
                    maxLenght = dp;
                    maxIndex = x;
                }

                x++;
                y++;
            }

            if (col > 0) {
                col--;
            } else {
                row++;
            }
        }

        return maxLenght == 0 ? "-1" : str1.substring(maxIndex - maxLenght + 1, maxIndex + 1);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            System.out.println(solve(in.next(), in.next()));
        }
    }
}
上一篇:Java版图形界面计算器


下一篇:最短包含字符串的长度