UVa10723 - Cyborg Genes

出處：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1664

解題策略：LCS的變形

LCS演算法的變形，不好想

參考 https://github.com/juanplopes/icpc/blob/master/uva/10723.cpp

使用LCS演算法計算兩個字串的LCS，到陣LCS[i][j]。

令L[i][j]為包含字串S1[1到i]與字串S2[1到j]的子序列字串的最短長度的字串個數

初始化L[i][0]=1,L[0][i]=1，個數為1

初始化L[i][j]等於0

若字元S1[i]等於字元S2[j]，則L[i][j]=L[i-1][j-1]，直接使用字元S1[i]或S2[j]串接，字串個數等同於L[i-1][j-1]；

否則字元S1[i]不等於字元S2[j]，

    若LCS[i-1][j]等於LCS[i][j]，表示最長共同子序列字串取到S1的第i-1個為止，須將S1[i]考慮進去，L[i][j] += L[i-1][j]。

    若LCS[i][j-1]等於LCS[i][j]，表示最長共同子序列字串取到S2的第j-1個為止，須將S2[j]考慮進去，L[i][j] += L[i][j-1]。