2014年阿里巴巴在線筆試題-第3大題-公共最長字符串長度
來源：程序員人生 發布時間：2014-09-06 18:24:50 閱讀次數：3459次
說明
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
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
