资源描述：
《华星笔试题目范文》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、华星笔试题目范文 求两个字符串的最大公共子串 把字符串1(长度m)横排串2(长度n)竖排得到一个m×n的矩阵c矩阵的每个元素的值如下如果m[i]=n[j]则c[j][i]=1,否则c[j][i]=0然后找出矩阵中连续是1的对角线最长的一个则对角线的长度就是公共子串的长度. 经过改进可以不需要构造矩阵因为第i行如果有字母匹配其取值仅与第i1行相关若m[i]=n[j]则c[j][i]=c[j1][i1]+1这样仅需要记录一个长度为m的一维数组就可以了 鼓捣出来的代码如下： include include c
2、har*StringSearch(char*str1,char*str2) { inti; intj; char*ptempBuffer1; char*ptempBuffer2; char*pwork; char*plast; char*ptemp; char*retstr; intresultIndex=0; intresultLength=0; intstr1Size=0; intstr2Size=0; ptempBuffer1=str1; while
3、(*ptempBuffer1=' ') { ptempBuffer1++; str1Size++; } ptempBuffer2=str2; while(*ptempBuffer2=' ') { ptempBuffer2++; str2Size++; } ptempBuffer1=(char*)malloc(str1Size); pwork=ptempBuffer1; memset(pwork,0,str1Size); ptempBuffer2=(char*
4、)malloc(str1Size); plast=ptempBuffer2; memset(plast,0,str1Size); for(i=0;i { for(j=0;j { if(*(str1+j)==*(str2+i)) { if(j==0) { *(pwork+j)=1; } else { *(pwork+j)=*(plast+j1)+1; } if(resultLength<*(pwork+j)) { resultInde
5、x=j; resultLength=*(pwork+j); } } else { *(pwork+j)=0; } } ptemp=pwork; pwork=plast; plast=ptemp; } retstr=(char*)malloc(resultLength+1); memcpy(retstr,str1+resultIndexresultLength+1,resultLength); *(retstr+resultLength)=' ';
6、printf(resultIndex=%d,resultLength=%d,resultIndex,resultLength); free(ptempBuffer1); free(ptempBuffer2); returnretstr; } intmain(intargc,char*argv[]) { char*ret=NULL; ret=StringSearch(adbccadebbca,edabccadece); printf(resultStringis%s,ret);
7、free(ret); system(PAUSE); return0; } 为了方便采用了两个容量为m的一维数组来保存运行中的结果空间复杂度为m+n+2*m(保存打印输出的结果字符串可以不需要)也就是O(m+n)由于需要事先遍历字符串得到长度算法复杂度为m*n+m+nO(m*n)级别 问题描述 一个给定序列的子序列是在该序列中删去若干元素后得到的序列确切地说若给定序列X=则另一序列Z=是X的子序列是指存在一个严格递增的下标序列使得对于所有j=1,2,…,k有Xij=Zj; 例如序列Z=是序列X=的
8、子序列相应的递增下标序列为<2,3,5,7> 给定两个序列X和Y当另一序列Z既是X的子序列又是Y的子序列时称Z是序列X和Y的公共子序列例如若X=
