最长公共字串-动态规划

╰半夏微凉° 2023-07-21 06:17 95阅读 0赞

在这里插入图片描述

  1. import java.util.*;
  2. public class ll {
  3. static int N=256;
  4. static int f(String s1,String s2){
  5. int a[][]=new int[N][N];
  6. int len1=s1.length();
  7. int len2=s2.length();
  8. // int i,j;
  9. int max=0;
  10. for (int i = 1; i <=len1 ; i++) {
  11. for (int l = 1; l <=len2 ; l++) {
  12. if (s1.charAt(i-1)==s2.charAt(l-1)){
  13. a[i][l]=a[i-1][l-1]+1;
  14. if (a[i][l]>max) max=a[i][l];
  15. }
  16. }
  17. }
  18. return max;
  19. }
  20. public static void main(String[] args) {
  21. System.out.println(f("abefecd","becd"));
  22. }
  23. }

发表评论

表情:
评论列表 (有 0 条评论,95人围观)

还没有评论,来说两句吧...

相关阅读

    相关 动态规划 公共

    核心思路和最长公共子序列一样 区别在于子串必须连续 可以先看我之前这篇文章 [最长公共子序列问题总结][Link 1] 最长公共子串同样是构造二维数组存储最大值,只不过去