求两个字符串最长子串的LCS算法 C语言实现(简短的实现函数)

/*************************************************************************

    > File Name:                lcs.c

    > Author:                   dingzhengsheng

    > Mail:                             [email protected]

    > Created Time:             2015年05月20日 星期三 16时07分50秒

    > Version:                  v0.01

    > Description:

    > History:

 ************************************************************************/

#include<stdio.h>

#include<time.h>

#include<stdlib.h>

#include <unistd.h>

#include<string.h>

#include<sys/time.h>

#include<ctype.h>

#include"test_time.h"

#define DEBUG   1

void slow_bb(char *a,int lena,char *b,int lenb, char *c)

{

        int i;

        int j;

        int index;

        int max=0;

        int num=0;

        int start;

        for(i=0; i<lena; i++)

        {

                for(j=0; j<lenb; j++)

                {

                        int start1 = i;

                        int start2 = j;

                        while((start1 < lena-1) && (start2<lenb-1) && (a[start1++] == b[start2++]))

                                num++;

                        if(num > max)

                        {

                                max = num;

                                start = i;

                        }

                        num = 0;

                }

        }

        strncpy(c, a+start, max);

}

void lcs(char *a, int lena, char *b, int lenb, char *c)

{

        int i;

        int j;

        int s[lena+1];

        memset(s, 0, sizeof(int)*(lena+1));

        int maxlen = 0;

        int pos;

#ifdef DEBUG

        int *dbg;

        dbg= (int *)malloc(sizeof(int)*(lenb+1)*(lena+1));

        memset(dbg, 0, sizeof(int)*(lenb+1)*(lena+1));

#endif

        for(j=lenb-1; j>=0; j--)

        {

                for(i=0; i<lena; i++)

                {

                        if(b[j] == a[i])

                        {

#ifdef DEBUG

                                *(dbg+j*(lena+1)+i) = s[i] = s[i+1]+1;

#else

                                s[i] = s[i+1]+1;

#endif

                                if(s[i] > maxlen)

                                {

                                        maxlen = s[i] ;

                                        pos = i;

                                }

                        }

                        else

                        {

                                /*

                                if(s[i+1] > maxlen)

                                {

                                        maxlen = s[i+1];

                                        pos = i+1;

                                }

                                */

                                s[i] =  0;

                        }

                }

        }

#ifdef DEBUG

        for(i=0; i<lenb+1; i++)

        {

                if(i == 0)

                {

                        printf("  ");

                        for(j=0; j<lena; j++)

                                printf("%c ", a[j]);

                        printf("\n");

                }

                if(i == lenb)

                        printf(" ");

                for(j=0; j<lena+1; j++)

                {

                        if(j == 0)

                                printf("%c ", b[i]);

                        printf("%d ", *(dbg+i*(lena+1)+j));

                }

                printf("\n");

        }

#endif

        strncpy(c,&a[pos], maxlen);

}

void main(int argc, char *argv[])

{

        char *a;

        char *b;

        int a_len;

        int b_len;

        char *c;

        int n = 100;

        int i=0;

        if(argc >= 1)

                n = atoi(argv[1]);

        if(argc >= 3)

        {

                a_len = atoi(argv[2]);

                b_len = atoi(argv[3]);

        }

        a = malloc(a_len);

        b = malloc(b_len);

        c = malloc(a_len);

        for(i=0; i<a_len; i++)

                a[i] =random()%4 + 0x30;

        for(i=0; i<b_len; i++)

                b[i] =random()%4 + 0x30;

        printf("a=%s\n", a);

        printf("b=%s\n", b);

        memset(c, 0, sizeof(c));

        starts();

        for(i=0;i<n;i++)

                slow_bb(a, a_len, b, b_len, c);

        ends();

        printf("slow_bb c=%s ts=%lld\n", c, tt());

        memset(c, 0, sizeof(c));

        starts();

        for(i=0;i<n;i++)

                lcs(a, a_len, b, b_len, c);

        ends();

        printf("slow_bb c=%s ts=%lld\n", c, tt());

        free(a);

        free(b);

        free(c);

}

　test_time.c：

#include<stdio.h>

#include<time.h>

#include <unistd.h>

#include<string.h>

#include<sys/time.h>

#include<sys/resource.h>

#include"test_time.h"

#define SECTOUSEC 1000000

static struct timeval tv1,tv2;

void starts()

{

        gettimeofday(&tv1,NULL);

}

void ends()

{

        gettimeofday(&tv2,NULL);

}

long int get_diff_time(struct timeval *tv1, struct timeval *tv2)

{

           long int n;

              n = (tv2->tv_sec - tv1->tv_sec)*SECTOUSEC + tv2->tv_usec - tv1->tv_usec;

                     return n;

}

long int tt()

{

        return get_diff_time(&tv1, &tv2);

}

　　test_time.h：

/*************************************************************************

    > File Name:                test_time.h

    > Author:                   dingzhengsheng

    > Mail:                             [email protected]

    > Created Time:             2015年05月20日 星期三 20时02分00秒

    > Version:                  v0.01

    > Description:

    > History:

 ************************************************************************/

#ifndef __TEST_TIME_H

#define __TEST_TIME_H

void starts();

void ends();

long int tt();

#endif

　　

运行结果：（矩阵的打印受宏DEBUG控制），后者耗时更长就是因为打印矩阵

注：代码中没有对最长子串有多个的情况做处理，两个函数的结果可能会不一样，可以用数组记录多个相同长度最长子串