日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > 互聯網 > 2014年阿里巴巴在線筆試題-第3大題-公共最長字符串長度

2014年阿里巴巴在線筆試題-第3大題-公共最長字符串長度

來源:程序員人生   發布時間:2014-09-06 18:24:50 閱讀次數:3463次

說明

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

生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 综合久久综合 | 国产一级片在线 | 欧美精品福利 | 国产精品中文在线 | av一区在线观看 | 亚洲免费网 | 国产欧美欧洲 | 金瓶狂野欧美性猛交xxxx | 九九九久久国产免费 | 欧美国产精品一区二区 | 久久久免费毛片 | 国产一区二区三区四 | 日本黄xxxxxxxxx100 | 久久国产精品网站 | 久久综合国产伦精品免费 | 日韩av电影网站 | 日韩在线免费 | 久久精品国产一区二区 | 亚洲区国产区 | 亚洲狠| 久久精品久久综合 | 91精品国产乱码久久久久久久久 | 欧美福利 | 亚洲一区二区三区中文字幕 | 成人免费大片黄在线播放 | 精品香蕉99久久久久网站 | 中文自拍 | www.久久99| 精品久久精品久久 | 99精品电影| 精品视频在线免费观看 | 男人操女人免费 | 色综合欧美| 欧美激情视频一区二区三区 | 黄色片国产| av麻豆| 日韩在线观看一区 | 欧美在线一级 | 一区二区三区在线 | 精品视频网站在线观看 | 天堂av中文字幕 |