北京网站搭建服务商,me域名的网站,青海城乡建设厅网站 官网,百度小程序对网站seo因为数据结构快学串了#xff0c;以前又做过一些字符串dp的题#xff0c;今天突然就想把它们写在一起吧。 直接开始
问题1#xff1a;给两个字符串#xff0c;求最长公共子串
问题2#xff1a;给两个字符串#xff0c;求最长公共子序列
问题3#xff1a;给一个字符串…因为数据结构快学串了以前又做过一些字符串dp的题今天突然就想把它们写在一起吧。 直接开始
问题1给两个字符串求最长公共子串
问题2给两个字符串求最长公共子序列
问题3给一个字符串求最长回文子串
问题4给一个字符串求最长回文子序列
问题5给一个字符串求将这个字符串变为回文串需要插入的最少字符个数。
问题6最小编辑代价
问题7判断交错组成
问题8给一个字符串求最长相同前后缀
问题9给串a和b判断b是否在a中出现若出现输出第一次出现的位置。
问题1给两个字符串求最长公共子串
串和序列的区别之前提到过串连续序列可以不连续
如果连续那就比较好想了定义DP(ij的含义是两个串分别以下标i和j结尾最长的公共子串长度。
如果a[i]b[j]那DP(ijDP(i-1j-11如果DP(i-1j-10还是同样的操作仅仅是之前不能构成而已那i和j结尾的最长一定是1了。
如果a[i]!b[j]DP(ij0因为定义是以i和j结尾一定不存在这样的相同子串。
初始化先打第一行和第一列相同为1不同为0即可。
问题2给两个字符串求最长公共子序列
举例
S1“ABCBDAB.”
S2“BABCBD.”
可以看出他们的最长公共子序列有ABCB,ABCD ,BCBD等长度为4.
Dp(i,j)表示S的前i位与T的前j位的最长公共子串长度。
如果a[i]b[j]那DP(ijDP(i-1j-11
否则DP(ijmaxDP(i-1jDP(ij-1
仔细体会手模拟几个就懂了。第一次想可能没那么容易
拓展三个字符串纯dp做
注多个字符串要其他做法以后数据结构学到串了或者树了再写。 问题3给一个字符串求最长回文子串
马拉车算法我确实觉得也是动态规划思想跳转看详细介绍吧
https://blog.csdn.net/hebtu666/article/details/79822584 问题4给一个字符串求最长回文子序列
对于任意字符串如果头尾字符相同那么字符串的最长子序列等于去掉首尾的字符串的最长子序列加上首尾如果首尾字符不同则最长子序列等于去掉头的字符串的最长子序列和去掉尾的字符串的最长子序列的较大者。
因此动态规划的状态转移方程为
设字符串为str长度为np[i][j]表示第i到第j个字符间的子序列的个数ij则
状态初始条件dp[i][i]1 i0n-1
状态转移方程dp[i][j]dp[i1][j-1] 2 ifstr[i]str[j] dp[i][j]max(dp[i1][j],dp[i][j-1]) if str[i]!str[j]
计算dp[i][j]时需要计算dp[i1][*]或dp[*][j-1]因此i应该从大到小即递减j应该从小到大即递增。注意必须满足ij的条件。
问题5给一个字符串求将这个字符串变为回文串需要插入的最少字符个数。
举例
ab3bd
只需变为adb3bda即可在前面插入d在后面插入a;
思路
设dp(i,j)为将Ai..Aj变为回文串的最小代价,如果a[i]a[j]那不用说了肯定是dp(i,j)dp(i1,j-1),如果不相同在前面或者后面插入一个字符即dp(i,j)min(dp(i,j-1),dp(i1,j))1
注意dp顺序
for i:n downto 1 for j:i1 to n 另一种思路
将原串与原串的倒序做一次最长公共子序列用原串长度减去最长公共子序列长度即为需要插入字符的个数。逻辑很好想不过多介绍 问题6最小编辑代价
这个解释有点麻烦思路分的比较多是个值得好好思考一下的题。
[题目] 给定两个字符串str1 和str2再给定三个整数ic、dc 和rc分别代表插入、删除和替换一个字符的代价返回将str1编辑成str2的最小代价。
(举例] str1abcstr2adc ic5, dc3, rc2。 从abc编辑成adc把b替换成d是代价最小的所以返回2。str1abcstr2adc, ic5 dc3, rc100。 从abc编辑成adc先删除b 然后插入d是代价最小的所以返回8。str1abcstr2abc, ic5, dc3, rc2。 不用编辑了本来就是一样的字符串所以返回0。 思路定义dp(i,j)为str1下标i之前编辑到str2下标j之前需要的最小代价。
Dp[0][0]0空到空不用改变。
矩阵dp第一列即dp[..M-1][0]。dp[i][0]表 示str1[0..-1]编辑成空串的最小代价亳无疑问是把str1[..i1]所有的字符删掉的代价所以dp[i][0]dc*i。
.矩阵dp第一行即dp[0][..N-1]。 dp[0][j]表示空串编辑成str2[O.j-1]的最小代价亳无疑问是在空串里插入str2[0.j-1]所有字符的代价所以dp[0][]ic*j。 其他位置按照从左到右再从上到下来计算dp[i][j]的值只可能来自以下四种情况。 str1[0.i-1]可以先编辑成str1[..i-2] 也就是删除字符str1[i-1] 然后由str1[0.i-2]编辑成str2[0.j-1] dp[i-1][i]表 示str1[0.i-2]编辑成 str2[0.j-1]的 最小代价那么dp[i][j]可能等于dcdp[i-1][j] str1[0.i-1]可以先编辑成str2[0.j-2], 然后将str2[0.j-2]插入字符str2[j-1] 编辑成str2[0.j-1]dp[i][j-1]表 示str1[..i-1]编 辑成str2[0.j-2]的最小代价 那么dp[i][j]可能等于dp[i][j-1]ic。 如果str1[i-1]!str2[j-1]。先把str1[0.i-1]中str1[..i-2]的 部分变成str2[0.j-2], 然后把字符str1[i-1]替换成str2[-1], 这样str1[..i-1]就编辑成str2[0.j1]了 。dp[i-1][j-1]表示str1[..i-2]编辑成str2[..i-2]的最小代价那么dp[i][j]可 能等于dp[i-1]j-1]rc.
如果str1[i-1]str2[j-1]. 先把str1[0..i-1]中 str1[0..i-2]的 部分变成str2[0.j-2], 因为此时字符str1[i-1]等 于str2[j-1] 所以str1[0.i-1]已 经编辑成str2[0.j-1]了 。dp[i-1][j-1]表示str1[0i-2]编辑 成str2[..i-2]的 最小代价那么dp[]ij]可能等于dp[i-1][j-1] 问题7判断交错组成
给定三个字符串strl str2和aim,如果aim包含且仅包含来自str1 和str2的所有字符而且在aim中属于str1的字符之间保持原来在str1中的顺序属于str2的字符之间保持原来在str2中的顺序那么称aim是str1和str2的交错组成。实现-一个函数判断aim是否是str1和str2交错组成。
思路做这个题一开始脑子没开窍老想三维表示str1的前i个和str2的前j个组成aim的k个但其实k只能是ij所以dp[i][j]为str1的前i个和str2的前j个能否组成aimij。
那就简单了要么放i要么放j都不行就是0有一个可以就是1.
问题8给一个字符串求最长相同前后缀前缀不包括最后一个字符后缀不包括第一个字符。
注意看kmp的next数组思想。先看下面的再看这个
https://blog.csdn.net/hebtu666/article/details/82492803
问题9给串a和b判断b是否在a中出现若出现输出第一次出现的位置。
8和9看kmp详解https://blog.csdn.net/hebtu666/article/details/79822446
