Longest Common Substring

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

我們必須先開一個二維陣列來儲存到某一狀況時的最長共同子字串的長度為多少。動態規劃即是隨時會紀錄下最新的狀況，往後要用時直接找尋該資料來拿運算，算出一筆新資料之後再記錄下來，以待往後使用... 如此循環運作。此方法可以省下許多時間複雜度，但卻要付出額外的記憶體空間紀錄，我個人會解讀這樣的方法是用空間去換取時間。

此外，若是只要判斷某字串是否為另外一個字串的子字串，只需判斷LCS的長度是否跟比較短的那字串長度相同即可。

#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