给出两个字符串(可能包含空格),找出其中最长的公共连续子串,输出其长度。
输入描述:
输入为两行字符串(可能包含空格),长度均小于等于50.
输出描述:
输出为一个整数,表示最长公共连续子串的长度。
输入例子1:
abcde
abgde
输出例子1:
2
当s1[i] == s2[j], dp[i][j]=dp[i-1][j-1]+1;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
//因为算空格,所以用nextLIne
String s1 = scan.nextLine();
String s2 = scan.nextLine();
int count = f(s1, s2);
System.out.println(count);
}
}
public static int f(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i < len1 + 1; i++) {
dp[i][0] = 0;
}
for (int j = 0; j < len2 + 1; j++) {
dp[0][j] = 0;
}
int max = 0;
for (int i = 1; i < len1 + 1; i++) {
for (int j = 1; j < len2 + 1; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}else {
dp[i][j] = 0;
}
if (max <= dp[i][j]) {
max = dp[i][j];
}
}
}
return max;
}
}
网友评论