2014年阿里巴巴在线笔试题-第3大题-公共最长字符串长度
来源：程序员人生 发布时间：2014-09-06 18:24:50 阅读次数：3298次
说明
2014年阿里巴巴在线笔试题-第3大题 首先，我没参加这次的阿里巴巴在线笔试题，题目全部是从别人口中描述而来，对于以下的分析，如果有什么不对的地方还望指教。也希望大家能够有更好的办法，希望大家来能不吝赐教。
题目描述
给定一个主字符串和一个匹配字符串，现在问你，找出 “主串中可匹配到的匹配串中子串的最大长度”，可能比较绕，举个例子吧
主字符串 abcdefgsdff 记为A
匹配字符串 abefgf 记为B
要求的值就是 3 因为 A中有efg B中也有efg ,而且也是AB中公共最长字符串
就是求两个字符串中连续公共最长字符串的长度。
分析
思路1.
由于匹配穿B的长度有限，所以可以求出B的所有连续子串 （时间复杂度O(M^2)）,然后用每一个子串向主串匹配（每次操作最快O（N）），这种思路的时间复杂度就是O（M^2*N）,代码自行设计，此处不赘述。
思路2.
使用DP的方式，思路我就不说了。
时间复杂度： O（M*N）
空间复杂度：O（M）
下面使用这种思路实现的c++代码：
#include <iostream>
#include <string.h>
using namespace std;
#define SUBLEN 50
#define MAINLEN 1000
char str1[SUBLEN]; //匹配串
char str2[MAINLEN]; //主串
int tmp1[SUBLEN]; //辅助1
int tmp2[SUBLEN]; //辅助2
//数组复位
void init(int * arr,int len){
for(int i = 0 ; i < len ;i++)arr[i]=0;
}
/**
计算主串中可匹配到的匹配串中子串的最大长度
时间复杂度:O(m*n)
空间复杂度:O(m)
*/
int getMaxSubLen(){
int maxLen = 0;
for(int i = 0 ; i < strlen(str2);i++){
if(i&1){
for(int j = 0 ; j < strlen(str1) ; j++ ){
if(str2[i]==str1[j]){
tmp1[j+1] = tmp2[j] + 1;
if(maxLen < tmp1[j+1])maxLen = tmp1[j+1];
}else tmp1[j+1] = 0;
}
}else{
for(int j = 0 ; j < strlen(str1) ; j++ ){
if(str2[i]==str1[j]){
tmp2[j+1] = tmp1[j] + 1;
if(maxLen < tmp2[j+1])maxLen = tmp2[j+1];
}else tmp2[j+1] = 0;
}
}
}
return maxLen;
}
/*
asawdecsescdsfdrfrc ascsesfdr
sdjnfksdsdlkmfl sjskm
sdsdsdsdsdsdwwwww sdswwwsdsdwwwww
测试结果
4
2
9
*/
int main()
{
while(cin>>str2>>str1){
init(tmp1,50);
init(tmp2,50);
cout<<getMaxSubLen()<<endl;
}
return 0;
}
是不是还有更好的算法？O(N)?
好吧，这个问题好像就是 “最长公共子串” 看来自己退化的不行不行的了
这里有时间复杂度：O（m+n）的解法
http://blog.csdn.net/yysdsyl/article/details/4226630
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
