11077 最长公共子字符串(优先做)
时间: 2023-04-26 11:05:31 浏览: 122
11077 最长公共子字符串是一道经典的字符串算法问题,其解法有多种,其中最常见的是动态规划算法。
动态规划算法的基本思想是将原问题分解为若干个子问题,通过求解子问题的最优解来求解原问题的最优解。在求解最长公共子字符串问题时,我们可以将两个字符串分别以行和列的形式表示出来,然后通过填充一个二维矩阵来求解最长公共子字符串的长度。
具体来说,我们可以定义一个二维数组dp,其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子字符串的长度。则有如下状态转移方程:
dp[i][j] = dp[i-1][j-1] + 1, if s1[i] == s2[j]
dp[i][j] = 0, if s1[i] != s2[j]
其中,s1和s2分别表示两个字符串,如果s1[i]等于s2[j],则说明当前字符可以加入到最长公共子字符串中,因此dp[i][j]的值应该为dp[i-1][j-1]+1;否则,当前字符不能加入到最长公共子字符串中,因此dp[i][j]的值应该为0。
最终,我们只需要在dp数组中找到最大的值,即为最长公共子字符串的长度。
需要注意的是,如果最长公共子字符串有多个,我们只需要输出其中任意一个即可。
相关问题
做一个大二数据结构与算法的计划表详细一点
好的,以下是一个大二数据结构与算法的计划表的详细内容:
1. 第一学期
- 第一周:学习基本数据结构,如数组、链表和栈等。
- 第二周:深入学习栈和队列,包括栈和队列的应用。
- 第三周:学习二叉树的基本概念,如二叉树的遍历和搜索等。
- 第四周:学习平衡二叉树,如AVL树和红黑树等。
- 第五周:学习哈希表和散列表,包括哈希函数的设计和冲突解决方法。
- 第六周:学习图论基础概念,如图的表示和遍历等。
- 第七周:学习最短路径算法,如Dijkstra算法和Floyd算法等。
- 第八周:学习最小生成树算法,如Prim算法和Kruskal算法等。
- 第九周:学习字符串匹配算法,如暴力法和KMP算法等。
- 第十周:学习动态规划算法,包括背包问题和最长公共子序列等。
2. 第二学期
- 第一周:学习高级数据结构,如堆、优先队列和B树等。
- 第二周:学习算法设计与分析的基本知识,如递归和分治等。
- 第三周:学习贪心算法,如活动安排问题和霍夫曼编码等。
- 第四周:学习回溯算法,如八皇后问题和0/1背包问题等。
- 第五周:学习分支限界算法,如旅行商问题和硬币找零问题等。
- 第六周:学习网络流算法,如最大流和最小割等。
- 第七周:学习NP完全性理论和近似算法,如NP完全问题和近似算法等。
- 第八周:学习并行算法和分布式算法的基础知识。
- 第九周:学习排序算法,如快速排序和归并排序等。
- 第十周:进行算法综合实践,包括问题分析、算法设计和代码实现等。
以上是一个大二数据结构与算法的计划表的详细内容,具体实施还需要根据教学计划和个人情况进行调整和完善。
java校招面试题算法
Java校招面试题中常见的算法题有很多,以下是一些常见的题目类型:
1. 排序算法:如冒泡排序、快速排序、归并排序等。
2. 查找算法:如二分查找、哈希表、二叉搜索树等。
3. 字符串操作:如字符串反转、字符串匹配、最长公共子串等。
4. 动态规划:如背包问题、最长递增子序列、最小路径和等。
5. 图论算法:如广度优先搜索(BFS)、深度优先搜索(DFS)、最短路径算法等。
6. 树和二叉树:如二叉树的遍历、求二叉树的深度、判断二叉树是否对称等。
7. 链表:如链表的反转、链表的合并、链表的环检测等。
8. 栈和队列:如用栈实现队列、用队列实现栈、有效的括号等。
9. 动态规划:如背包问题、最长递增子序列、最小路径和等。
以上只是一些常见的算法题目类型,实际面试中可能会遇到更多不同类型的题目。在准备面试时,建议多做练习,熟悉常见的算法思想和解题方法。