素数：一个大于1的正整数，如果除了1和它本身以外，不能被其他正整数整除，就叫素数。如2，3，5，7，11，13，17…
举个例子：s1="abcfde"，s2="bcde"。那么s1与s2的最长公共子序列就是"bcde"，注意不要求连续。该问题是典型的动态规划问题。
动态规划是大厂的热门考点，其中最长公共子串与最长公共子序列这两道题出现得尤其频繁，这两道题其实有挺多变种，很适合考察侯选人对动态规划的掌握情况，今天我们就先来看看如何求解最长公共子串，图文并茂，清晰易懂！
我们还从一个非常经典的题目出发，最长公共子串问题。给定两个字符串S和T，求S和T的最长公共子串的长度。比如abcdefg和abacabca的最长公共子串是abc 这是一道经典的动态规划问题，大致思路就是用fi表示同时以S[i]和T[j]结尾的最长公共子串的长度。下面看伪代码：
比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。最长公共子序列（Longest Common Subsequence,LCS），顾名思义，是指在所有的子序列中最长的那一个。子串是要求更严格的一种子序列，要求在母串中连续地出现。在上述例子的中，最长公共子序列为blog（cnblogs,belong），最长公共子串为lo（cnblogs, belong）。
0. 引言 最近鄙人面试百度，出了这道求解公子序列长度的算法题。故此总结一下，这是一个很典型的题目，希望对大家将来的面试中能起到学习的作用。 1. 问题描述 子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。最长公共子序列（Longest Common Subsequence,LCS），顾名思义，是指在所有的子序列中最长的那一个。子串
——老子
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
最长公共字串，最长公共子序列，最长递增子序列都是典型的动态规划问题，最长公共子串和最长公共子序列的差别是最长公共子序列可以不连续，但是最长公共子串必须连续。先来看最长公共子串，首先会想到暴力法解决，最长公共子串的暴力法会达到指数级，所以我们直接用dp解决，先确定状态，由于最长公共子串必须是连续的，所以我们这个状态很好想出来，dp[i][j]代表字符串str1位置i之前和str2位置j之前公共子串多长，下面确定状态转移方程
子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而他们的最长公共子序列是adf。
根据回文串的定义，正着和反着读一样，那我们是不是把原来的字符串倒置了，然后找最长的公共子串就可以了。例如 S = "caba" ，S = "abac"，最长公共子串是 "aba"，所以原字符串的最长回文串就是 "aba"。
我们将两个字符串的字符逐一对比，然后将对比的结果（即如果相等，那么在原有的长度基础上加1）保存在数组中。因为要返回子串，因此需要拿到最长子串的起始位置和长度，长度保存在了数组中，起始位置我们通过计算得出来。请看下图：
倘若要在一堆数据中对一个关键词进行匹配搜索，传统做法是把数据拆分开，然后遍历他们，看看是否包含这个关键词，对于 “fin” 和 “finish” 这样存在包含关系的单词来说是没问题的，但是对于 “fish” 和 “finish” 这样并不存在包含关系的单词就失效了，这时候期望计算出两个单词的相似性，比如 “fish” 和 “finish” 都包含 “ish”，“ish” 的长度是 3，我们可以理解相似性为 3。目前主流做法是通过最长公共子串来寻找两个或多个已知字符串最长的子串。
MaxLen(i, j) = 0 //两个空串的最长公共子序列长度当然是0
问题描述： 求两个字符序列的公共最长子序列。 ---- 最长公共子串 在回到子序列问题之前，先来了解一下子串的问题。 例如，HISH和FISH两个字符序列的公共最长子串就是：ISH。很容易理解。 ---- 绘制网格 通过上一次背包问题的学习，给了我一些很重要的启示： 每种动态规划解决方案都设计网格。 动态规划可以帮助你在给定约束条件下找到最优解。 问题可分解为彼此独立且离散的子问题时，就可以使用动态规划法来解决。 那么，要解决这个问题的网格长什么样呢？要确定这一点，你首先得回答： 1.单元格中的值是什么？
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
本文记录寻找两个字符串最长公共子串和子序列的方法。 名词区别 最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。 最长公共子串 是指两个字符串中最长连续相同的子串长度。 例如：str1=“1AB2345CD”,str2=”12345EF”,则str1，str2的最长公共子串为2345。 动态规划 如果 str1 的长度为
dynamic programming被认为是一种与递归相反的技术，递归是从顶部开始分解，通过解决掉所有分解出的问题来解决整个问题，而动态规划是从问题底部开始，解决了小问题后合并为整体的解决方案，从而解决掉整个问题。
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
小明负责维护项目下的代码，需要查找出重复代码，用以支撑后续的代码优化，请你帮助小明找出重复的代码。 重复代码查找方法：以字符串形式给出两行代码（字符串长度1 < length <= 100，由英文字母、数字和空格组成），找出两行代码中的最长公共子串。 注：如果不存在公共子串，返回空字符串。
阅读本文大概需要 5 分钟。 在使用搜索引擎时，当我们输入错误的关键词时，当然这里的错误是拼写错误，搜索引擎的下拉框中仍会显示以正确关键词为前前辍的提示，当你直接回车搜索错误的关键词时，搜索引擎的结果
很久前就有小伙伴被动态规划所折磨，确实，很多题动态规划确实太难看出了了，甚至有的题看了题解理解起来都费劲半天。
看了几天的后缀自动机，感觉这玩意儿确实比较神奇。但是感觉自己肯定讲不明白，就简单的来写写心得和应用吧 性质 1、每个状态$s$代表的长度区间为$(len[fa[s]],len[s])$ 也就是说$min(s) = max(s) + 1$ 2、每个状态$s$代表的所有串在原串中的出现次数及出现位置右端点相同。 这也是后缀自动机能够压缩状态的原因，就是把很多相同的串压缩到一个节点中 3、在parent树中，对于状态$s$，$fa[s]$所代表的状态是$s$所代表状态的后缀 4、在parent树中，每个状态的$r
Description 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。 任务： l 读入单词 l 计算最长公共子串的长度 l 输出结果 Input 文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。 Output 仅一行，一个整数，最长公共子串的长度。 Sample Input 3 abcb bca acbc Sample Output ２ 其实这题我没A因为权限号密码忘了 但是在COGS过了那就发一下吧。。 感
模板题直接上dp，dp[i] [j] 为A数组以 i 结尾，B数组以 j 结尾的最长公共子串长度。
回文串是面试常常遇到的问题（虽然问题本身没啥意义），本文就告诉你回文串问题的核心思想是什么。
故事起源于工作的一个实际问题，要分析两个文本序列间的相似性，然后就想着干脆把一些常见的字符串相似性内容一并整理一下好了。
原文链接：https://blog.csdn.net/humanking7/article/details/84645055
贪心算法属于比较简单的算法，它总是会选择当下最优解，而不去考虑单次递归时是否会对未来造成影响，也就是说不考虑得到的解是否是全局最优。在很多实际问题中，寻找全局最优解的代价是非常大的，这时候就可以通过求次优解来解决问题，这种思想其实在软件工程中很常见，例如React中著名的DOM Diff算法中需要对比两棵DOM树，树的完全对比时间复杂度为O(n^3)，而React团队通过只比较同层节点的策略将问题简化为O(n)，也就是说得到的结果从全局角度来说并不一定是绝对最优的，但是它可以在大多数情况下表现并不差。
http://blog.csdn.net/u012102306/article/details/53184446 http://blog.csdn.net/hrn1216/article/details/51534607
参考：https://www.jb51.net/article/144122.htm
解释：一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串，如下图示：
1、把a1,a2,…,an排序，假设得到a’1,a’2,…,a’n，然后求a的a’的最长公共子串，这样总的时间复杂度为o(nlg(n))+o(n^2)=o(n^2);
选择一个元素作为排序的基准值，然后将数组中小于该值的和大于该基准值的分别进行排序，不断递归该过程，最后将小于该基准值的数组、基准值、大于基准值的数组拼接为一个完整数据即可
构造备忘录P[i,c]，P[i,c]表示在前i个商品中选择，背包容量为c时的最优解
Description A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.
1、先建立一个二维数组array[str1.size()][str2.size()]（全部初始化为0），初始化第一行和第一列（元素相同处置1），然后进入状态方程
最长公共子序列，。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
最近由于某些原因，又回顾了一次KMP算法。上一次回顾KMP算法还是在刷题的时候遇到的： http://blog.csdn.net/dacc123/article/details/50994611 在我的记忆力，每次回顾KMP算法都会有新的理解，以为自己理解的很透彻了，等过一段时间再去回顾，又要花一些时间去弄门清。这次也一样。 刚接触Next数组的时候我很反感字符串前缀和后缀的最长公共子串的长度来解释next数组，我认为next数组就是一个字符串的对称程度。在这样的理解之下，计算next数组的理解就是：
判断一个字符串是不是回文串，可以用动态规划方法 dp[i][j]:表示i到j的字符串，是不是回文串，是就为true，不是就为false 那么当s[i] == s[j]的时候，dp[i][j] = dp[i+1][j-1],这是根据回文串的特点，比较容易理解的，比如我们知道bab是回文串，如果a = a,那么ababa也就是回文串！ 所以我们可以用动态规划法求出最长回文串，然后也知道了他的起始位置，i和j，所以就比较容易求解了，唯一注意的问题是，我们得倒着求，而不能跟往常一样顺着求解，因为状态转移方程的依赖关系，是倒着依赖的。
咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
Given an unsorted array of integers, find the length of longest increasing subsequence.
还是先看暴力解法:枚举子串的两个端点i和j,判断在[i, j]区间内的子串是否回文。从复杂度上来看，枚举端点需要0(n2),判断回文需要0(n)，因此总复杂度是O(n3)。终于碰到一个暴力复杂度不是指数级别的问题了!但是O(n)的复杂度在n很大的情况依旧不够看。 可能会有读者想把这个问题转换为最长公共子序列(LCS) 问题来求解:把字符串S倒过来变成字符串T,然后对S和T进行LCS模型求解，得到的结果就是需要的答案。而事实上这种做法是错误的，因为一旦S中同时存在一个子串和它的倒序，那么答案就会出错。例如字符串S= “ABCDZJUDCBA”,将其倒过来之后会变成T = “ABCDUJZDCBA”,这样得到最长公共子串为”ABCD”，长度为4,而事实上S的最长回文子串长度为1。因此这样的做法是不行的。 动态规划解决 令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0。这样根据S[i]是否等于S[j]，可以把转移情况分为两类： ①若S[i]=S[j],那么只要S[i+1]和S[j-1]是回文子串，S[i+1]至S[j-1]就是回文子串；如果S[i+1]至S[j-1]不是回文子串，则S[i]至S[j]一定不是回文子串。 ②若S[i]!=S[j]，那S[i]至S[j]一定不是回文子串。 由此可以写出状态转移方程
题目有意思的地方在于，最长公共子串与最长连续公共子串都是比较经典的问题，但是这道题在其基础上加了限制。 首先这道题应该是最长连续公共子串问题，状态转移方程就不写了，挺简单的。就记录下最大的子串所在的位置的行坐标和列坐标，就能把子串拿到手。 但是对于O(nm)的动态规划所有点都会超时，这就很厉害了，目前通过的做法使用的是滑动窗口法，我还在研究。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议
