【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串（LCS）

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int comfix(const char* stra, const char* strb);
int main(void){
    const char
        *stra = "hello world",
        *strb = "malloc";
    printf("%s,%s: %d\n", stra, strb, comfix(stra, strb));
    return 0;
}

int comfix(const char* stra, const char* strb){
    /*
     * 变量第一字符
     * c:char*, l:len
     * 变量第二字符
     * s:small, l:large
     */
    const char
        *cs  = stra,
        *cl  = strb;
    int ret = 0,
        la  = strlen(stra),
        lb  = strlen(strb),
        ls  = la,
        ll  = lb;
    /* 如果不对，就调换呗 */
    if (lb<la)
        cs = strb, ls = lb, cl = stra, ll = la;
    /* 矩阵，只保存矩阵的一行即可动态之 */
    int *pint = (int*)malloc((ls+1)*4);
    memset(pint ,0 , (ls+1)*4);
    int i, j;
    for (i=0; i<ll; i++){
        /* 生成下一行，同时上一行内容被回收 */
       for (j=ls; j>ret; j--)
           if (cl[i]==cs[j])
               pint[j] = pint[j-1]+1;
       /* 如果有更大就更新ret */
       for (j=ls; j>ret; j--)
           if (pint[j]>ret)
               ret = pint[j];
    }
    return ret;
}