[006] largest_common_substring

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

[Description] Given two different strings, find the largest successive common substring.

e.g.str1[]="qwertyuiopasdfgh";str2[]="jhdfgqwertyudfxcv";

LCsubstr[]="qwertyu";

[Thought] show the correspondence result of this two strings from the 2-D array of 'record[][]', and find the longest non-zero diagonal elements. To save the auxiliary space, we can use only 1-D array 'record[]' to implement. O(n^2)O(m)

[Implementation] C code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h> char* LCS(char longer[], char shorter[])
{
int longer_len=strlen(longer);
int shorter_len=strlen(shorter);
int record[shorter_len];
int i,j,max_len=,substr_end=,substr_begin; for(i=;i<longer_len;i++)
{
for(j=shorter_len-;j>=;j--)
{
if(longer[i]==shorter[j])
{
if(==i || ==j)
{
record[j]=;
}
else
{
record[j]=record[j-]+;
}
}
else
{
record[j]=;
} if(record[j]>max_len)
{
max_len=record[j];
substr_end=j;
}
}
} substr_begin=substr_end-max_len+; // char substr[max_len];
char* substr=(char*)malloc(max_len);
for(i=;i<max_len;i++)
{
substr[i]=shorter[substr_begin+i];
}
return substr;
} int main()
{
char longer[]="asdfghjklqwertyyuio";
char shorter[]="zxvsdffghwerxv"; printf("The longer str:\n\t%s\n",longer);
printf("The shorter str:\n\t%s\n",shorter);
printf("The lagest common str:\n\t%s\n",LCS(longer,shorter));
return ;
}