wordpress有多少网站,怎么做网络推广优化,中关村,vps 一个ip 多个网站 软件 linux今天去面试#xff0c;面试官出了一道题#xff0c;求两个字符串的最大公共子串(Longest Common Substring)#xff0c;一听起来不是很难#xff0c;但让我在纸上写着写着就迷糊了。回来特地网搜了一下。面试下面经过两种方法来求两个字符串的最大连续公共子串。数组方法1面试官出了一道题求两个字符串的最大公共子串(Longest Common Substring)一听起来不是很难但让我在纸上写着写着就迷糊了。回来特地网搜了一下。面试下面经过两种方法来求两个字符串的最大连续公共子串。数组方法1暴力解法code将字符串s1和s2分别写在两把直尺上面而后将s1固定s2的头部和s1的尾部对齐而后逐渐移动直尺s2比较重叠部分的字符串中的公共子串的长度直到直尺s2移动到s1的头部。在这个过程当中求得的最大长度就是s一、s2最大子串的长度。内存#include#include#includechar* longest_common_substring(char *str1,char *str2){int str1len strlen(str1);int str2len strlen(str2);int i,j,index,max0,num0;int start;//将两个字符串看作两个直尺固定一个直尺另一个从头至尾开始移动逐一与固定的直尺比较值。for(i 0; i str1len; i){for(j 0; j str2len; j){//这里的start一、start2是比较关键的int start1i;int start2j;while((start1 str1len-1) (start2 str2len-1) (str1[start1] str2[start2]))num;if(num max)//若是num是当前最大匹配的个数则赋给max而且在start记下str1最长匹配开始的位置{maxnum;starti;}num0;//若是num不是当前最大的则赋为0值继续循环}}char *str(char *)malloc(max 1);strncpy(str,str1 start,max);//从字符串str1的start位置开始拷贝max个字符到str中这就是咱们找出的最大子串str[max] \0;printf(最长公共连续子串的长度为%d\n,max);return str;}int main(){char str1[1000],str2[1000];printf(请输入第一个字符串);gets(str1);printf(请输入第二个字符串);gets(str2);char *str longest_common_substring(str1,str2);printf(%s\n,str);free(str); //记得要free不然形成内存泄露system(pause);return 0;}方法2动态规划解法字符串主要是定义了一个二维数组这个数组c用来保存str1中每一个字符向前能与str2中的字符匹配的个数。每次会将最大的匹配个数保存到max变量中而且记录拥有max的字符在原字符串中的位置。get当str1[i] str2[j]时子序列长度c[i][j] c[i - 1][j - 1] 1只是当str1[i] str2[j]时c[i][j]长度要为0而不是max{c[i - 1][j], c[i][j - 1]}。string/**找出两个字符串的最长公共连续子串的长度**/#include stdio.h#include string.h#include stdlib.hint longest_common_substring(char *str1, char *str2){int i,j,k,len1,len2,max,x,y;len1 strlen(str1);len2 strlen(str2);int **c new int*[len11];for(i 0; i len11; i)c[i] new int[len21];for(i 0; i len11; i)c[i][0]0; //第0列都初始化为0for(j 0; j len21; j)c[0][j]0; //第0行都初始化为0max -1;for(i 1 ; i len11 ; i){for(j 1; j len21; j){if(str1[i-1]str2[j-1]) //只须要跟左上方的c[i-1][j-1]比较就能够了c[i][j]c[i-1][j-1]1;else //不连续的时候还要跟左边的c[i][j-1]、上边的c[i-1][j]值比较这里不须要c[i][j]0;if(c[i][j]max){maxc[i][j];xi;yj;}}}//输出公共子串char s[1000];kmax;ix-1,jy-1;s[k--]\0;while(i0 j0){if(str1[i]str2[j]){s[k--]str1[i];i--;j--;}else //只要有一个不相等就说明相等的公共字符断了不连续了break;}printf(最长公共子串为);puts(s);for(i 0; i len11; i) //释放动态申请的二维数组delete[] c[i];delete[] c;return max;}int main(void){char str1[1000],str2[1000];printf(请输入第一个字符串);gets(str1);printf(请输入第二个字符串);gets(str2);int len longest_common_substring(str1, str2);printf(最长公共连续子串的长度为%d\n,len);system(pause);return 0;}
