首页 > 代码库 > 最长连续字母序列的长度（阿里2015在线研发工程师笔试题）
最长连续字母序列的长度（阿里2015在线研发工程师笔试题）
给定一个query和一个text，均由小写字母组成。要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如， query为“acbac”，text为“acaccbabb”，那么text中的“cba”为最长的连续出现在query中的字母序列，因此，返回结果应该为其长度3。请注意程序效率。
直接暴力，时间复杂度：m*n*n
int Solve(char qu[],int n,char te[],int m){ int i,j; int k,p; int Max; int ans=0; for(i=0;i<m;i++)//te { k=i; for(j=0;j<n;j++)//qu { p=j; Max=0; while(k<m&&p<n&&te[k]==qu[p]) { j++; p++; Max++; } if(ans<Max)ans=Max; } } return ans;}
简单DP做法，时间复杂度：m*n
#include<stdio.h>int Solve(char qu[],int n,char te[],int m){ int sum[n][m]; int i,j; for(i=0;i<n;i++)//qu { for(j=0;j<m;j++)//te { if(i==0||j==0) { if(qu[i]==te[j]) sum[i][j]=1; else sum[i][j]=0; } else { if(qu[i]==te[j]) sum[i][j]=sum[i-1][j-1]+1; else sum[i][j]=0; } } } int Max=0; for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(sum[i][j]>Max)Max=sum[i][j]; } } return Max;}int main(){ char s1[6]="acbac"; char s2[10]="acaccbabb"; int ans=Solve(s1,5,s2,9); printf("%d\n",ans); return 0;}
听说有KMP的做法，对于例子。
个人思路：
求出“acbac”，“cbac”，“bac”……的next[1][],next[2][]next[3][]……
时间复杂度n*n；
匹配“acbac”与“acaccbabb”，“cbac”与“acaccbabb”……
时间复杂度（m+n）*n；
最长连续字母序列的长度（阿里2015在线研发工程师笔试题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。