今天去面試，面試官出了一道題，求兩個(gè)字符串的最大公共子串(Longest Common Substring)，一聽起來不是很難，但讓我在紙上寫著寫著就迷糊了。回來特地網(wǎng)搜了一下。面試

下面經(jīng)過兩種方法來求兩個(gè)字符串的最大連續(xù)公共子串。數(shù)組

方法1：暴力解法code

將字符串s1和s2分別寫在兩把直尺上面，而后將s1固定，s2的頭部和s1的尾部對齊，而后逐漸移動直尺s2，比較重疊部分的字符串中的公共子串的長度，直到直尺s2移動到s1的頭部。在這個(gè)過程當(dāng)中求得的最大長度就是s一、s2最大子串的長度。內(nèi)存

#include

#include

#include

char* longest_common_substring(char *str1,char *str2)

{

int str1len = strlen(str1);

int str2len = strlen(str2);

int i,j,index,max=0,num=0;

int start;

//將兩個(gè)字符串看作兩個(gè)直尺，固定一個(gè)直尺，另一個(gè)從頭至尾開始移動，逐一與固定的直尺比較值。

for(i = 0; i < str1len; i++)

{

for(j = 0; j < str2len; j++)

{

//這里的start一、start2是比較關(guān)鍵的

int start1=i;

int start2=j;

while((start1 <= str1len-1) && (start2 <= str2len-1) && (str1[start1++] == str2[start2++]))

num++;

if(num > max)//若是num是當(dāng)前最大匹配的個(gè)數(shù)，則賦給max，而且在start記下str1最長匹配開始的位置

{

max=num;

start=i;

}

num=0;//若是num不是當(dāng)前最大的，則賦為0值繼續(xù)循環(huán)

}

}

char *str=(char *)malloc(max + 1);

strncpy(str,str1 + start,max);//從字符串str1的start位置開始，拷貝max個(gè)字符到str中，這就是咱們找出的最大子串

str[max] = '\0';

printf("最長公共連續(xù)子串的長度為：%d\n",max);

return str;

}

int main()

{

char str1[1000],str2[1000];

printf("請輸入第一個(gè)字符串：");

gets(str1);

printf("請輸入第二個(gè)字符串：");

gets(str2);

char *str= longest_common_substring(str1,str2);

printf("%s\n",str);

free(str); //記得要free，不然形成內(nèi)存泄露

system("pause");

return 0;

}

方法2：動態(tài)規(guī)劃解法字符串

主要是定義了一個(gè)二維數(shù)組，這個(gè)數(shù)組c用來保存str1中每一個(gè)字符向前能與str2中的字符匹配的個(gè)數(shù)。每次會將最大的匹配個(gè)數(shù)保存到max變量中，而且記錄擁有max的字符在原字符串中的位置。get

當(dāng)str1[i] == str2[j]時(shí)，子序列長度c[i][j] = c[i - 1][j - 1] + 1；只是當(dāng)str1[i] ！= str2[j]時(shí)，c[i][j]長度要為0，而不是max{c[i - 1][j], c[i][j - 1]}。string

/**

找出兩個(gè)字符串的最長公共連續(xù)子串的長度

**/

#include "stdio.h"

#include "string.h"

#include "stdlib.h"

int 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*[len1+1];

for(i = 0; i < len1+1; i++)

c[i] = new int[len2+1];

for(i = 0; i < len1+1; i++)

c[i][0]=0; //第0列都初始化為0

for(j = 0; j < len2+1; j++)

c[0][j]=0; //第0行都初始化為0

max = -1;

for(i = 1 ; i < len1+1 ; i++)

{

for(j = 1; j < len2+1; j++)

{

if(str1[i-1]==str2[j-1]) //只須要跟左上方的c[i-1][j-1]比較就能夠了

c[i][j]=c[i-1][j-1]+1;

else //不連續(xù)的時(shí)候還要跟左邊的c[i][j-1]、上邊的c[i-1][j]值比較，這里不須要

c[i][j]=0;

if(c[i][j]>max)

{

max=c[i][j];

x=i;

y=j;

}

}

}

//輸出公共子串

char s[1000];

k=max;

i=x-1,j=y-1;

s[k--]='\0';

while(i>=0 && j>=0)

{

if(str1[i]==str2[j])

{

s[k--]=str1[i];

i--;

j--;

}

else //只要有一個(gè)不相等，就說明相等的公共字符斷了，不連續(xù)了

break;

}

printf("最長公共子串為：");

puts(s);

for(i = 0; i < len1+1; i++) //釋放動態(tài)申請的二維數(shù)組

delete[] c[i];

delete[] c;

return max;

}

int main(void)

{

char str1[1000],str2[1000];

printf("請輸入第一個(gè)字符串：");

gets(str1);

printf("請輸入第二個(gè)字符串：");

gets(str2);

int len = longest_common_substring(str1, str2);

printf("最長公共連續(xù)子串的長度為：%d\n",len);

system("pause");

return 0;

}

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的c语言找出公共子字符串,经典C语言面试题：求解最大公共子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。