蓝桥杯-求最大公共子串

最新推荐文章于 2022-03-16 22:07:19 发布

危笑qwq

最新推荐文章于 2022-03-16 22:07:19 发布

阅读量295

点赞数 1

分类专栏：蓝桥杯文章标签：字符串 leetcode 算法动态规划 java

本文链接：https://blog.csdn.net/qw160/article/details/108051986

版权

蓝桥杯专栏收录该内容

25 篇文章

订阅专栏

题目：求两个字符串的最大公共子串，例如abcd和abcdefsh是abcd输出4

解题：有动态规划的思想，如果两个字母一样，给下一个格子加一

在这里插入图片描述

package august17;

public class 最大公共子串 {
    public static void main(String[] args) {
     String a1="yyabcdefghuu";

     String a2="xxabcdefgh";
     char []b1=a1.toCharArray();
     char []b2=a2.toCharArray();
        int [][]c=new int [b1.length+1][b2.length+1];



        int count=0;

        for(int i=0;i<b1.length;i++)
        {
            for(int j=0;j<b2.length;j++)
            {
                if(b1[i]==b2[j])
                {
                    c[i+1][j+1]=c[i][j]+1;
                    if( c[i+1][j+1]>count)
                        count=c[i+1][j+1];
                }
            }
        }
        System.out.println(count);
    }
}