[Java知识库]牛客网最长公共子串

package com.example.interview;

import java.util.Scanner;

/**
给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。
*/
public class SubString {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String str1 = sc.nextLine();
String str2 = sc.nextLine();
SubString test = new SubString();
String r = test.lcs(str1, str2);
System.out.println?;
}
sc.close();
}

public String lcs(String str1, String str2){

if(str1.length() == 0 || str2.length() == 0){
return “-1”;
}
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int endIndex = -1;
int max = 0;

int[][] arr = new int[s1.length][s2.length];
for (int i = 0; i < s1.length; i++) {
for (int j = 0; j < s2.length; j++) {
if(i0 || j0) {
arr[i][j] = s1[i] == s2[j] ? 1: 0;
} else {
if(s1[i] == s2[j]) {
arr[i][j] = arr[i-1] [j-1] + 1;
}

    }
    if(arr[i][j] > max) {
        max = arr[i][j];
        endIndex = i;
    }
    // System.out.print(arr[i][j]+ " ");
}
// System.out.println();

}

return endIndex==-1 ? “-1” : str1.substring(endIndex-max+1, endIndex+1);
}
}