首页 > 代码库 > [006] largest_common_substring
[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:
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 5 char* LCS(char longer[], char shorter[]) 6 { 7 int longer_len=strlen(longer); 8 int shorter_len=strlen(shorter); 9 int record[shorter_len];10 int i,j,max_len=0,substr_end=0,substr_begin;11 12 for(i=0;i<longer_len;i++)13 {14 for(j=shorter_len-1;j>=0;j--)15 {16 if(longer[i]==shorter[j])17 {18 if(0==i || 0==j)19 {20 record[j]=1;21 }22 else23 {24 record[j]=record[j-1]+1;25 }26 }27 else28 {29 record[j]=0;30 }31 32 if(record[j]>max_len)33 {34 max_len=record[j];35 substr_end=j;36 }37 }38 }39 40 substr_begin=substr_end-max_len+1;41 42 // char substr[max_len];43 char* substr=(char*)malloc(max_len);44 for(i=0;i<max_len;i++)45 {46 substr[i]=shorter[substr_begin+i];47 }48 return substr;49 }50 51 int main()52 {53 char longer[]="asdfghjklqwertyyuio";54 char shorter[]="zxvsdffghwerxv";55 56 printf("The longer str:\n\t%s\n",longer);57 printf("The shorter str:\n\t%s\n",shorter);58 printf("The lagest common str:\n\t%s\n",LCS(longer,shorter));59 return 0;60 }
[006] largest_common_substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。