微软面试100题(56):最长公共子串

56.最长公共字串。

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，

则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。

请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

例如：输入两个字符串BDCABA 和ABCBDAB，字符串BCBA 和BDAB 都是是它们的最长公共子串，则输出它们的长度4，并打印任意一个子串。

扩展问题：上一问中是非连续的，如果是连续的呢。

这个是典型的动态规划算法。本来应该能轻松出来才对，结果折腾了好久没搞定。

动态规划其实就是数学归纳法，核心是推出f(n)与f(n-1)之间的关系。所以，很多情况下需要倒假定n的情况，推出n+1的情况。不能企图从最初始的状态推导出后续状态。这点引以为戒。

假设有：

Xm = x1 x2 x3 ... xm

Yn = y1 y2 y3 ... yn

A. 最长公共子序列(不必连续)（LCS）

定义f(m, n)为Xm和Yn之间最长的子序列的长度

若f(m-1,n-1)已知，那么这时候检查Xm和Yn

1.如果 xm == xn,那么有,说明最后一位应该加入公共子序列，所以其长度 f(m,n) = f(m-1,n-1)+1

2.如果 ym != yn,那么公共子序列是: 

X(m-1)与 Y(n)的最长公共子序列 

X(m)与 Y(n-1)的最长公共子序列

之间较长的那个

则f(m, n) = max{ f(m-1, n), f(m, n-1) }

加入初始条件f(0,0) = 0, f(1,0) = 0, f(0,1).

最后可以递推出结果.

那么最后f(m, n)的值就是结果

B. 最长公共子序列(连续)（LSS）

考虑前m,n个字符，假设到m,n为止，且包含xm,yn的连续公共子串为  f(m,n) = z1 z2 z3 ... zl

那么到第m+1,n+1个字符时，

1.如果x(m+1) == y(n+1),那么到m+1/n+1 且包含最后一个元素的连续公共字串应该延长1位，增加元素x(m+1)/y(n+1)。

有f(m+1,n+1) = f(m,n) +1

2.如果x(m+1) != y(n+1),那么如果要包含最后这位，其连续公共字串长度为0.

有f(m+1,n+1) = 0

加入初始条件f(0,0) = 0, f(1,0) = 0, f(0,1) = 0.

最后可以递推出结果.

和上一问不同，这次填入f(m,n)的过程中，填入的最大值才是结果。

/*
 * =====================================================================================
 *
 *       Filename:  maxsubstr.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  10/08/2012 06:16:16 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  [e-mail] (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#define    MAX 100            /*  */

void lcs(const char* s1, const char* s2){
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int result[MAX][MAX] = {{0}};

    int i = 0, j =0;
    result[i][j] = 0;
    result[1][j] = 0;
    result[i][1] = 0;
    i++;
    j++;
    for(;i<=len1;i++){
        for(j=1;j<=len2;j++){
            if(s1[i-1] == s2[j-1]){
                result[i][j] = result[i-1][j-1] +1;
                printf ( "=fill [%d][%d] = %d\n", i,j, result[i][j] );
            }
            else{
                if(result[i-1][j]>result[i][j-1]){
                    result[i][j] = result[i-1][j];
                    printf ( ", i,j, result[i][j] );
                }
                else{
                    result[i][j] = result[i][j-1];
                    printf ( ">fill [%d][%d] = %d\n", i,j, result[i][j] );
                }
            }

        }
    }
}

void lss(const char* s1, const char* s2){
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int result[MAX][MAX] = {{0}};

    int i = 0, j =0;
    result[i][j] = 0;
    result[1][j] = 0;
    result[i][1] = 0;
    i++;
    j++;
    for(;i<=len1;i++){
        for(j=1;j<=len2;j++){
            if(s1[i-1] == s2[j-1]){
                result[i][j] = result[i-1][j-1] +1;
                printf ( "=fill [%d][%d] = %d\n", i,j, result[i][j] );
            }
        }
    }

}


/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    lss("abcde","bccdebc");
    printf ( "-------------------------------\n" );
    lcs("abcde","bccdebc");
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */