最大公共子串及其长度计算

最大公共子串长度计算

两重遍历，即将两个字符串都遍历。

两个字符串str1 , str2。定义两个内部变量作为指针用于内部遍历，从字符串str1的第一个字符开始遍历，分别与字符串str2的每个字符进行比较，如果相同，则count+1，两内部指针都+1，用与在内部遍历继续判断字符是否相等，max记录最大的count值，一轮遍历之后i+1，即抛弃str1的第一个元素剩余的字符串再与str2整体进行比较。最终输出的max就是最大公共子串的长度。

最大公共子串长度输出

只需要增加一个变量int index 用于记录最大子串的末尾索引位置（其实记录的是末尾索引位置+1）。输出的时候直接调用String.substring(int beginIndex, int endIndex)，substring 方法不包括endIndex，即左闭右开。所以输出的就是最长子串。

import java.util.*;public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String str1 = sc.nextLine(); String str2 = sc.nextLine(); int max = 0; for(int i = 0; i < str1.length(); i++){ //遍历字符串1 for(int j = 0; j < str2.length(); j++){ //遍历字符串2 int a = i; int b = j; int count = 0; int index = 0; //记录最长子串的末尾索引 while(str1.charAt(a) ==str2.charAt(b)){ //字符相等则进入遍历 a++; b++; count++; //字符相等则当先相同子串长度计数+1 if(max < count){ max = count; index = a; //记录最大字串最后一位的索引位置（其实是末尾索引+1） } if(a == str1.length()|| b ==str2.length()) //遍历到任何一个字符串末尾则跳出循环，进行下一轮遍历。 break; } } } System.out.println(max); System.out.println(str1.substring(index-max,index); //substring 是左闭右开 } } }