[数据结构与算法]最大公共子串及其长度计算

最大公共子串长度计算

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

两个字符串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 是左闭右开
           }
       }
      
}