首页 > 代码库 > 阿里笔试题：求两个子序列的最大连续子序列
阿里笔试题：求两个子序列的最大连续子序列
原题例如以下：
给定一个query和一个text。均由小写字母组成。要求在text中找出以相同的顺序连续出如今query中的最长连续字母序列的长度。
比如。query为 "acbac",text为"acaccbabb",那么text中的"cba"为最长的连续出如今query中的字母序列，因此，返回结果应该为其长度3。请注意程序效率。
解题方法一：
和字符串匹配一样（http://blog.csdn.net/sinat_24520925/article/details/45113651），T字符串和P字符串，相当于在T字符串的每一个字符都求一个和P的最大连续子序列。
代码例如以下：
int sublength(string T,string P)
{
string res="";
int n=T.length();
int m=P.length();
string substring="";
for(int i=0;i<n;i++)
{
substring="";
for(int j=0;j<m;j++)
{
if((i+j)<=(n-1))
{
if(T[i+j]!=P[j])
{
if(substring.length()>res.length())
{
res=substring;
substring="";
}
}
else
substring+=T[i+j];
}
else
{
if(substring.length()>res.length())
{
res=substring;
substring="";
break;
}
}
}
}
return res.length();
}
解题思路二：
和求公共子序列同样（http://blog.csdn.net/sinat_24520925/article/details/42872251），仅仅只是子序列是连续的。我们用一个二维矩阵matrix就能够表示子序列的情况，T代表每一列的字符，P代表每一行的元素，假设P【i】=T【j】,则matrix【i】【j】=matrix【i-1】【j-1】+1。最后输出矩阵中最大的元素就可以。要是求最大连续子序列，依据最大元素的位置，沿着对角线向上回溯就可得到答案。代码例如以下：
int sublength1(string T,string P)
{
int n=T.length();
int m=P.length();
vector<vector<int>> matrix;
vector<int> row(n,0);
for(int i=0;i<m;i++)
matrix.push_back(row);
int max=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(T[j]==P[i])
{
if(i!=0&&j!=0)
{
matrix[i][j]=matrix[i-1][j-1]+1;
if(matrix[i][j]>max)
max=matrix[i][j];
}
else
matrix[i][j]=1;
}
}
}
return max;
}
阿里笔试题：求两个子序列的最大连续子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。