LCS代表最长连续子序列与最长连续字串
发布时间
阅读量：
阅读量
最长公共子串(LCS)，包括但不限于三种不同的情况:
1.公共子串的元素仅限于相邻的情况。
2.部分相邻的情况也可以被纳入分析范围。
3.该方法适用于涉及多个字符串的最长公共子串研究。
对于公共子串问题而言，在解决该问题时需要确保所涉及的所有元素均为相邻状态。寻找两个字符串之间的最长公共子串的一种有效方法是构造一个动态规划矩阵。当对应位置上的字符相同时标记为1，在其他情况下标记为0。特别地，在动态规划表中将当前单元格与左上方单元格的关系设定为其值加一（此做法有助于后续统计）。通过遍历该矩阵找到具有最长连续1序列的对角线路径。这些路径所经过的位置即代表了最长公共子串的具体位置。
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int main()///求最长公共连续子串
{
int dp[110][110];
string s1="21232523311324";
string s2="312123223445";
char p[110];
int len1=s1.lengt全部评论 (0)
还没有任何评论哟~