問題：需要兩個字符串之間的LCS的長度。字符串的大小最多爲100個字符。字母表是通常的DNA，4個字符「ACGT」。動態方法不夠快。最長公共子序列長度（LCS）的快速（er）算法
我的問題是，我正在處理很多對和很多對（我可以看到數以億計的等級）。我相信我已經將LCS_length函數的調用減少到了可能的最小值，所以使我的程序運行得更快的唯一方法就是擁有更高效的LCS_Length函數。
我已經開始實施通常的動態編程方法。 這給出了正確的答案，並希望能夠正確實施。
#define arrayLengthMacro(a) strlen(a) + 1
#define MAX_STRING 101
static int MaxLength(int lengthA, int lengthB);
/*
* Then the two strings are compared following a dynamic computing
* LCS table algorithm. Since we only require the length of the LCS
* we can get this rather easily.
*/
int LCS_Length(char *a, char *b)
{
int lengthA = arrayLengthMacro(a),lengthB = arrayLengthMacro(b),
LCS = 0, i, j, maxLength, board[MAX_STRING][MAX_STRING];
maxLength = MaxLength(lengthA, lengthB);
//printf("%d %d\n", lengthA, lengthB);
for (i = 0; i < maxLength - 1; i++)
{
board[i][0] = 0;
board[0][i] = 0;
}
for (i = 1; i < lengthA; i++)
{
for (j = 1; j < lengthB; j++)
{
/* If a match is found we allocate the number in (i-1, j-1) incremented
* by 1 to the (i, j) position
*/
if (a[i - 1] == b[j - 1])
{
board[i][j] = board[i-1][j-1] + 1;
if(LCS < board[i][j])
{
LCS++;
}
}
else
{
if (board[i-1][j] > board[i][j-1])
{
board[i][j] = board[i-1][j];
}
else
{
board[i][j] = board[i][j-1];
}
}
}
}
return LCS;
}
這應該是O（mn）（希望）。
然後在尋找速度，我發現這個職位Longest Common Subsequence 這給了邁爾斯的O(ND) paper。我試過這個將LCS與最短編輯腳本（SES）聯繫起來的方法。他們給出的關係是D = M + N - 2L，其中D是SES的長度，M和N是兩個串的長度，L是LCS長度。但是在我的實施中，這並不總是正確的。我給我的實施（我認爲是正確的）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define arrayLengthMacro(a) strlen(a)
int LCS_Length (char *a, char *b);
int MinLength (int A, int B);
int Max (int A, int B);
int snake(int k, int max, char *a, char *b, int lengthA, int lengthB);
int main(void)
{
int L;
char a[] = "tomato", b[] = "potato"; //must give LCS = 4
L = LCS_Length(a, b);
printf("LCS: %d\n", L);
char c[] = "GTCGTTCGGAATGCCGTTGCTCTGTAAA", d[] = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA"; // must give LCS = 20
L = LCS_Length(c, d);
printf("LCS: %d\n", L);
char e[] = "human", f[] = "chimpanzee"; // must give LCS = 4
L = LCS_Length(e, f);
printf("LCS: %d\n", L);
char g[] = "howareyou", h[] = "whoareyou"; // LCS =8
L = LCS_Length(g, h);
printf("LCS: %d\n", L);
char i[] = "TTCTTTCGGTAACGCCTACTTTATGAAGAGGTTACATTGCAATCGGGTAAATTAACCAACAAGTAATGGTAGTTCCTAGTAGAGAAACCCTCCCGCTCAC",
j[] = "GCACGCGCCTGTTGCTACGCTCTGTCCATCCTTTGTGTGCCGGGTACTCAGACCGGTAACTCGAGTTGCTATCGCGGTTATCAGGATCATTTACGGACTC"; // 61
L = LCS_Length(i, j);
printf("LCS: %d\n", L);
return 0;
}
int LCS_Length(char *a, char *b)
{
int D, lengthA = arrayLengthMacro(a), lengthB = arrayLengthMacro(b),
max, *V_, *V, i, k, x, y;
max = lengthA + lengthB;
V_ = malloc(sizeof(int) * (max+1));
if(V_ == NULL)
{
fprintf(stderr, "Failed to allocate memory for LCS");
exit(1);
}
V = V_ + lengthA;
V[1] = 0;
for (D = 0; D < max; D++)
{
for (k = -D; k <= D; k = k + 2)
{
if ((k == -D && V[k-1] < V[k+1]) || (k != D && V[k-1] < V[k+1]))
{
x = V[k+1];
}
else
{
x = V[k-1] + 1;
}
y = x - k;
while ((x < lengthB) && (y < lengthA) && (a[x+1] == b[y+1]))
{
x++;
y++;
}
V[k] = x;
if ((x >= lengthB) && (y >= lengthA))
{
return (lengthA + lengthB - D)/2;
}
}
}
return (lengthA + lengthB - D)/2;
}
有主要的例子。例如， 「番茄」和「馬鈴薯」（不要評論），LCS長度爲4. 實現發現它是5個SES（代碼中的D）出現2，而不是我期望的4 （刪除「t」，插入「p」，刪除「m」，插入「t」）。我傾向於認爲也許O（ND）算法也會計算替換，但我不確定這一點。
任何可以實施的方法（我沒有很多編程技能）都是值得歡迎的。 （如果有人知道如何利用小字母例如）。
編輯：我認爲這將是有益的說，在任何其他的頂部，我在任何時候使用任何兩個字符串之間的LCS函數。所以它不僅是字符串說s1，相比之下有幾百萬人。它可能是s200與s1000，然後s0與s10000，然後250與s100000。不太可能跟蹤最常用的字符串。 我需要的LCS長度不是一個近似值，因爲我正在實現一個近似算法，我不想添加額外的錯誤。
編輯：剛剛跑過callgrind。對於10000個字符串的輸入，我似乎將不同的字符串對稱爲lcs函數大約50,000,000次。 （10000字符串是我想運行的最低字符數，最大值是100萬字符（如果可行的話））。
在第二個版本中，你並沒有刪除'V_'，如果你調用這個函數數億次，肯定會導致問題。每次調用函數時，都應該避免分配內存，因爲這會減慢你的速度。在你的情況下，我只是在棧上聲明一個固定長度的數組'int V_ [2 * MAX_STRING + 2]'。 – TonyK
LCS使用的空間是O（mn）。你可以把它放到O（n），它可以讓你的程序更快，因爲緩存的命中率會增加。但是，如果n，m〜10^3我通常使用這個。您可以嘗試我之前寫過的[this]（http://www.ideone.com/4rG7k）代碼，並及時查看其中的差異（如果有的話）。 –
@logic_max：這是對算法的一個很好的修改，但第19行的副本將撤消避免緩存命中的任何性能優勢（無論如何，我認爲這對於〜40kb陣列來說並不太可怕）。您可以通過保留兩個int指針來避免該副本，即在每次迭代中交換的L和L_old。 –