else nat 顺序 post string popu substr 连续
给定一个 query 和一个 text。均由小写字母组成。要求在 text 中找出以相同的顺序连续出如今 query 中的最长连续字母序列的长度。
比如。query 为 "acbac",text 为 "acaccbabb", 那么 text 中的 "cba" 为最长的连续出如今 query 中的字母序列,因此,返回结果应该为其长度 3。请注意程序效率。
代码例如以下:
- 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();
- }
- 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;
- }
阿里笔试题:求两个子序列的最大连续子序列
来源: http://www.bubuko.com/infodetail-2111956.html