题解 | #公共子串计算#

公共子串计算

https://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b

从右向左收缩及早判断是否必要继续
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();
            int maxLen = 0;
            String small = a.length() > b.length() ? b : a;
            String big = a.length() > b.length() ? a : b;
            for (int i = 0; i < small.length(); i++) {
                if (small.length() - i <= maxLen) {
                    break;
                }
                for (int j = small.length(); j > i; j--) {
                    if (big.contains(small.substring(i, j)) && j - i > maxLen) {
                        maxLen = j - i;
                        break;
                    }
                }
            }
            System.out.println(maxLen);
        }
    }
}


全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务