博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最长公共子串-golang
阅读量:5806 次
发布时间:2019-06-18

本文共 1138 字,大约阅读时间需要 3 分钟。

解题方法:

首先生成动态规划表dp,生成规则如下:

对于两个字符串str1和str2,dp[i][j]表示将str1[i]和str[j]作为公共子串最后一个字符的长度

非第一行,第一列:

如果str1[i]==str2[j],则dp[i][j] = dp[i-1][j-1]+1

如果str1[i] != str2[j], 则dp[i][j] = 0

第一行或者第一列

第一行:如果str1[i]==str2[0],则dp[i][0] = 1

第一列:如果str1[0] != str2[j], 则dp[0][j] = 1

按照上述规则生成动态规划表dp,时间复杂度为O(MXN),空间复杂度为O(MXN)。查询dp中的最大值,然后向左上方向查找,直到dp值为1,即可得到最终公共子串。

从动态规划表可以看到其大致形式如下图:

因此可以按照图中箭头方向查询两个字符串,并用一个变量记录公共子串的长度,代码如下:

func getMaxLengthCommonString(str1, str2 []rune)[]rune{    chs1 := len(str1)    chs2 := len(str2)    maxLength := 0 //记录最大长度    end := 0//记录最大长度的结尾位置    rows := 0    cols := chs2-1    for rows < chs1 {        i,j := rows, cols        length := 0 //记录长度        for i< chs1 && j < chs2 {            if str1[i] != str2[j]{                length = 0            }else{                length ++            }            if length > maxLength {                end = i                maxLength = length            }            i ++            j ++        }        if cols > 0 {            cols --        }else{            rows++        }    }    return str1[(end-maxLength+1):(end+1)]}

  

转载于:https://www.cnblogs.com/youhongpp/p/8971406.html

你可能感兴趣的文章
Oracle命令导入dmp文件
查看>>
OCP读书笔记(24) - 题库(ExamD)
查看>>
Http、TCP/IP协议与Socket之间的区别(转载)
查看>>
解决Unable to load R3 module ...VBoxDD.dll (VBoxDD):GetLastError=1790
查看>>
.net excel利用NPOI导入oracle
查看>>
vrpie在Visio Studio 中无法调试的问题
查看>>
第六课:数据库的基本工具
查看>>
关于二叉树重构的思索
查看>>
$_SERVER['SCRIPT_FLENAME']与__FILE__
查看>>
skynet实践(8)-接入websocket
查看>>
系统版本判断
查看>>
关于Css选择器优先级
查看>>
My97DatePicker 日历插件
查看>>
0603 学术诚信与职业道德
查看>>
小点心家族第3位成员——楼层定位效果
查看>>
Knockout.Js官网学习(enable绑定、disable绑定)
查看>>
hive基本操作与应用
查看>>
excel快捷键设置
查看>>
poj3692
查看>>
python之信号量【Semaphore】
查看>>