求兩個字符串最長子串的LCS算法 C語言實現(簡短的實現函數)，lcs算法

求兩個字符串最長子串的LCS算法 C語言實現(簡短的實現函數)，lcs算法

/*************************************************************************
    > 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控制），後者耗時更長就是因為打印矩陣

注：代碼中沒有對最長子串有多個的情況做處理，兩個函數的結果可能會不一樣，可以用數組記錄多個相同長度最長子串