【2016-1】求最大公共字串长度
【2016-1】求最大公共字串长度
题目描述：给定两个字符串，求最大公共字串的长度，长度小于1000
分为两种问题：要求计算连续最长字串的长度
如下按照寻找连续的字串理解
输入：
1111hello2222
1133hello444
输出：
5
#include
#include
#include
using namespace std;#define maxn 1005
int dp[maxn][maxn];int main(){string s1, s2;while(cin >> s1 >> s2){int ans = 0;memset(dp, 0, sizeof(dp));s1 = "#"+s1; //空出0号位s2 = "#"+s2; for(int i=1; i - 定义dp[i][j]表示，s1以i为结尾的字串中，和s2以j为结尾的字串中，最长公共字符的个数是多少
- 123rrrr44dd与kkkk123rrrrdddddd的例子中，s1以dd结尾，最长有2个公共的，但是以rrrr结尾，最长有7个公共的，最长的情况在遍历完之前取到了，遍历所有两两搭配的结果，可以得到所有情况中的最长连续公共字串（1定义的可行性）
- 当s1[i]!=s2[j]， 依据定义，dp[i][j]为0
- 当s1[i]==s2[j]时，dp[i][j] = dp[i-1][j-1]+1; 【。。。。。i-1】a【i】
- 与【。。。j-1】a【j】，a相同时，dp【i】【j】的长度取决于i-1及之前，与j-1及之前的长度
- 同类题型参考：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！