两个字符串的最长公共串

    #include <stdio.h>
    #include <string.h>
    #define N 100
    char a[N], b[N], str[N];
    int c[N][N], x, y;

    int lcs_len(char* a, char* b, int c[][N])
    {
    int m = strlen(a), n = strlen(b), i, j;
    int lcs = 0;
    for( i=0; i<m; i++ )
    {
    for( j=0; j<n; j++ )
    {
    if (a[i]==b[j])
    {
    c[i][j]= (i*j) ? c[i-1][j-1]+1 : 1;
    if( c[i][j] > lcs)
    {
     lcs = c[i][j];
     x = i;
     y = j;
    }
    }
    else
    c[i][j] = 0;
    }
    }
    return lcs;
    }

    char* build_lcs(char s[], char* a, char* b)
    {
    int i = 0, j = 0;
    int k = lcs_len(a,b,c);
    printf("%d %d %d\n", k, x, y);
    s[k] = '\0';
    for( i = x - k + 1; i < x + 1; i++ )
    {
    s[j++] = a[i];
    }
    return s;
    }

    void main()
    {
    printf("Enter two string (length < %d) :\n",N);
    scanf("%s%s",a,b);
    printf("LCS=%s\n",build_lcs(str,a,b));
    }

 

通过构建比较矩阵来获得最长的字串，这个方法很巧妙。