## Thursday, January 12, 2012

### Longest Common Substring

Longest Common Substring (LCS)是用來找尋兩字串中最長共同子字串的長度。此方法運用動態規劃(Dynamic Programming, DP)。

```#include <stdio.h>
#include <string.h>

// 2D map
int map[100][100];

/*
* Function : max
* This return the bigger number of the two input variables.
*/
int max(int a, int b){
return (a>b)?a:b;
}

/*
* Function : LCS
* Longest Common Substring function here.
* This function return the length of their longest common
* substings.
*/
int lcs(char str1[], char str2[]){

int i, j;
int m=strlen(str1), n=strlen(str2);

for(i=1 ; i<=m ; i++){
for(j=1 ; j<=n ; j++){
if(str1[i] == str2[j])
map[i][j] = map[i-1][j-1]+1;
else
map[i][j] = max(map[i][j-1], map[i-1][j]);
printf("%d ",map[i][j]);
}
printf("\n");
}

return map[m][n];
}

int main(void){

// variable declarations
char str1[100], str2[100];

// input two strings
printf("String1 >> ");
scanf("%s",str1);
printf("String2 >> ");
scanf("%s",str2);

// print out result
printf("LCS >> %d\n", lcs(str1, str2));

// by checking whether the length of lcs is same as the string1,
// we would know whether string1 is the substring of string2 or not.
if(lcs(str1, str2) == strlen(str1))
printf("String1 is a substring of String2!\n");
else
printf("String1 is NOT a substring of String2!\n");

return 0;
// end
}
```

http://en.wikipedia.org/wiki/Longest_common_substring_problem