问题描写叙述
给定一个 query 和一个 text 。均由小写字母组成。要求在 text 中找出以相同的顺序连续出如今 query 中的最长连续字母序列的长度。
比如， query为“acbac”。text为“acaccbabb”，那么text中的“cba”为最长的连续出如今query中的字母序列，因此，返回结果应该为其长度3。请注意程序效率。
代码思想
1、遍历两字符串的每个元素，遇见同样元素则计算该次同样次数同样元素数目。并与之前最大值比較，遍历结束即得到终于相似元素数目。
2、用vector建立一个二维向量markMatrix，markMatrix[i][j]表示query中第i个字符和text中第j个字符的最长连续字母序列的长度。
源代码实现
#include<iostream>
using namespace std;
int len(char *query,char *text) //求两个字符串的连续公共部分子函数，返回公共字符串长度；
{
int i;
for(i=1;query[i]!=' '&&text[i]!=' ';i++)
if(query[i]!=text[i])
break;
return(i);
}
int main()
{
// char query[100],text[100];
char *query,*text;
int i,j,max=0,lenth=0;
// cout<<"please input query:"<<endl;
// cin>>query;
query = "acbac";
// cout<<"please input text"<<endl;
// cin>>text;
text = "acaccbabb";
for(i=0;query[i]!=' ';i++)
{
for(j=0;text[j]!=' ';j++)
{
if(query[i]==text[j])
{
lenth=len(&query[i],&text[j]);
if(max<lenth)
max=lenth;
//i+=lenth-1;
}
}
}
printf("the longth of the same max string is %d
",max);
return(max);
}
STL 实现
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int FindMaxLength(string query, string text)
{
int m = query.length();
int n = text.length();
vector<vector<int> > markMatrix(m,vector<int>(n)); // m行n列的矩阵
int i = 0, j = 0;
int maxLen = -1;
for (i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (query[i] == text[j])
{
if (i == 0 || j == 0)
{
markMatrix[i][j] = 1;
}
else
{
markMatrix[i][j] = markMatrix[i - 1][j - 1] + 1;
}
}
if (markMatrix[i][j] > maxLen)
maxLen = markMatrix[i][j];
}
}
return maxLen;
}
void main()
{
string query;
string text;
/*
cout << "输入query 和 text ： " << endl;
cin >> query;
cin >> text;
*/
query = "acbac";
text = "acaccbabb";
int maxLength = FindMaxLength(query,text);
cout << "最大公共长度为： " <<maxLength<< endl;
}