Longest Common Substring问题描述如下：

给定一个query和一个text，均由小写字母组成。要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如， query为"acbac"，text为"acaccbabb"，那么text中的"cba"为最长的连续出现在query中的字母序列，因此，返回结果应该为其长度3。请注意程序效率。

假设text长为T，query长为Q。

Brute Force

很多人的第一想法就是罗列出query和text的所有子串，挨个比较，取出二者都有的子串，最后返回最长的子串长度。

算法的时间复杂度将为O(T^2 * Q^2)

int get_max_sub_bf(const char* text, const char* query) {
    // Time O(T^2 * Q^2)
    int T = strlen(text);
    int Q = strlen(query);
    int max = -1;
    int flag;
    for (int i = 0; i < T; i++) {
        for (int ii = 0; ii < T - i; ii++) {
            //text[i, ii+i]
            for (int j = 0; j < Q; j++) {
                for (int jj = 0; jj < Q - j; jj++) {
                    // query[j, jj+j]
                    if(jj==ii) {
                        flag=1;
                        for(int k = 0;k < ii; k++) {
                            if(text[i+k]!=query[j+k]) {
                                flag = 0;
                                break;
                            }
                        }
                        if(flag && (max<ii)) {
                            max=ii;
                        }
                    }
                }
            }
        }
    }
    return max;
}

Dynamic Programming

典型的以空间换时间，但是用到了子字符串的相关规律。

假设dp[i][j]是字符串text[0…i]和query[0…j]的最长公共子串长度。

那么有：若text[i]==query[j]，则dp[i][j]=dp[i-1][j-1] + 1。

算法复杂度：时间O(T * Q), 空间O(T * Q)。

int get_max_sub_dp(const char* text, const char* query) {
    // Time O(T*Q)
    // Space O(T*Q)
    int T = strlen(text);
    int Q = strlen(query);
    int dp[T][Q];
    for(int i = 0 ; i < T; i ++)
    {
        for(int j = 0; j < Q; j ++)
        {
            dp[i][j] = 0;
        }
    }
    // dp[i][j]表示T[0...i]和Q[0...j]的最大公共子串长度
    int max = -1;
    for (int i = 1; i < T; i++) {
        for (int j = 1; j < Q; j++) {
            if (text[i - 1] == query[j - 1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if(max<dp[i][j]) {
                    printf("dp[%d][%d]\n", i, j);
                    max=dp[i][j];
                }
            }
        }
    }
    return max;
}

测试与比较

首先需要有测试用的text和query，我在Linux环境用Shell命令生成随机字符串。

rm -f in.dat
####生成长度为1000的text字符串到in.dat第一行
tr -cd '[:alnum:]' < /dev/urandom | fold -w1000 | head -n1 > in.dat
####生成长度为100的query字符串到in.dat第一行
tr -cd '[:alnum:]' < /dev/urandom | fold -w100 | head -n1 >> in.dat

编写C代码，读取text和query，用两种方法进行测试，在标准输出打印所用时间。

#include <sys/time.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
int timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1)
{
    long int diff = (t2->tv_usec + 1000000 * t2->tv_sec) - (t1->tv_usec + 1000000 * t1->tv_sec);
    result->tv_sec = diff / 1000000;
    result->tv_usec = diff % 1000000;

    return (diff<0);
}
void timeval_print(struct timeval *tv)
{
    char buffer[30];
    time_t curtime;

    printf("%ld.%06ld", tv->tv_sec, tv->tv_usec);
    curtime = tv->tv_sec;
    strftime(buffer, 30, "%m-%d-%Y  %T", localtime(&curtime));
    printf(" = %s.%06ld\n", buffer, tv->tv_usec);
}
int main(int argc, char* argv[])
{
    struct timeval tvBegin, tvEnd, tvDiff;
    char *text= NULL;
    char *query= NULL;
    FILE *in = fopen("in.dat","r");
    size_t len=0;
    if(in==NULL) return -1;
    getline(&text, &len, in);
    getline(&query, &len, in);
    printf("%s", text);
    printf("%s", query);
    fclose(in);

    // dp
    gettimeofday(&tvBegin, NULL);
    printf("lcs %d\n", get_max_sub_dp(text,query));
    gettimeofday(&tvEnd, NULL);
    timeval_subtract(&tvDiff, &tvEnd, &tvBegin);
    printf("dp time elapsed %ld.%06ld s\n", tvDiff.tv_sec, tvDiff.tv_usec);

    // br
    gettimeofday(&tvBegin, NULL);
    printf("lcs %d\n", get_max_sub_bf(text,query));
    gettimeofday(&tvEnd, NULL);
    timeval_subtract(&tvDiff, &tvEnd, &tvBegin);
    printf("bf time elapsed %ld.%06ld s\n", tvDiff.tv_sec, tvDiff.tv_usec);

    return 0;
}

编译代码gcc common_sub_str.c -o common_sub_str

运行./common_sub_str

得出结果：

dp time elapsed 0.002574 s
bf time elapsed 5.522046 s

实验重复两次，都是得到dp的时间效率高出bf近2000倍。