最长公共子串

本文主要是介绍最长公共子串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接

给定两个字符串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()));
        }
    }
}

这篇关于最长公共子串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！