文档章节

最长公共子串

datacube
 datacube
发布于 2016/07/07 11:04
字数 228
阅读 7
收藏 0
public class LongestCommonSubstring {

    public static void main(String[] args) {
        LongestCommonSubstring lcs = new LongestCommonSubstring();
        System.out.println(lcs.longestCommonSubstring("ABCBDAB","BDCABA"));
    }

    public  int compute(char[] str1, char[] str2)
    {
        int size1 = str1.length;
        int size2 = str2.length;
        if (size1 == 0 || size2 == 0) return 0;

        // the start position of substring in original string
        int start1 = -1;
        int start2 = -1;
        // the longest length of common substring
        int longest = 0;

        // record how many comparisons the solution did;
        // it can be used to know which algorithm is better
        int comparisons = 0;

        for (int i = 0; i < size1; ++i)
        {
            int m = i;
            int n = 0;
            int length = 0;
            while (m < size1 && n < size2)
            {
                ++comparisons;
                if (str1[m] != str2[n])
                {
                    length = 0;
                }
                else
                {
                    ++length;
                    if (longest < length)
                    {
                        longest = length;
                        start1 = m - longest + 1;
                        start2 = n - longest + 1;
                    }
                }

                ++m;
                ++n;
            }
        }

        // shift string2 to find the longest common substring
        for (int j = 1; j < size2; ++j)
        {
            int m = 0;
            int n = j;
            int length = 0;
            while (m < size1 && n < size2)
            {
                ++comparisons;
                if (str1[m] != str2[n])
                {
                    length = 0;
                }
                else
                {
                    ++length;
                    if (longest < length)
                    {
                        longest = length;
                        start1 = m - longest + 1;
                        start2 = n - longest + 1;
                    }
                }

                ++m;
                ++n;
            }
        }
        System.out.printf("from %d of str1 and %d of str2, compared for %d times\n", start1, start2, comparisons);
        return longest;
    }

    public  int longestCommonSubstring(String str1, String str2)
    {
        return compute(str1.toCharArray(), str2.toCharArray());
    }
}

/**
 *
 *滚动数组只求大小
 *
 *
 *
 */

© 著作权归作者所有

datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问
求两个字符串的最长公共子串——Java实现

要求:求两个字符串的最长公共子串,如“abcdefg”和“adefgwgeweg”的最长公共子串为“defg”(子串必须是连续的) public class Main03{// 求解两个字符号的最长公共子串public static Str...

知晓的老巢
2018/08/27
0
0
HDU 1159 Common Subsequence

Common Subsequence   A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another seq......

suvvm
2018/11/08
0
0
有趣的算法问题之巧思妙想

有趣的算法 算法之所以有趣,在于他能够化繁为简,他能概括统御世间万物,将一个复杂的问题归结为一个非常简单的问题。其实所有高阶的算法,都可以用两个大的方法去解决,而且屡试不爽。分别...

Nicholas_Jela
2017/09/06
0
0
算法与数据结构(二):动态规划(DP)总结

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/89388883 1. 最长公共子序列 题目描...

dby_freedom
04/21
0
0
动态规划——最长公共子序列

一个数列S,若分别是两个或多个已知序列的子序列,且是所有符合条件序列中最长的,则S称为已知序列的最长公共子序列。 最长公共子串:子串是串的一个连续的部分. 最长公共子序列:子序列则可...

曾劲松
2016/03/29
11
0

没有更多内容

加载失败,请刷新页面

加载更多

kubernetes pod exec接口调用

正文 一般生产环境上由于网络安全策略,大多数端口是不能为集群外部访问的。多个集群之间一般都是通过k8s的ApiServer组件提供的接口通信,如https://192.168.1.101:6443。所以在做云平台时,...

码农实战
41分钟前
6
0
3_数组

3_数组

行者终成事
今天
8
0
经典系统设计面试题解析:如何设计TinyURL(二)

原文链接:https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
今天
7
0
使用logstash同步MySQL数据到ES

概述   在生成业务常有将MySQL数据同步到ES的需求,如果需要很高的定制化,往往需要开发同步程序用于处理数据。但没有特殊业务需求,官方提供的logstash就很有优势了。   在使用logstas...

zxiaofan666
今天
10
0
X-MSG-IM-分布式信令跟踪能力

经过一周多的鏖战, X-MSG-IM的分布式信令跟踪能力已基本具备, 特点是: 实时. 只有要RX/TX就会实时产生信令跟踪事件, 先入kafka, 再入influxdb待查. 同时提供实时sub/pub接口. 完备. 可以完整...

dev5
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部