亚洲天堂自拍视频,久艹中文字幕av,日韩欧美激情性爱

作者： Wen Hui

轉(zhuǎn)載：中間件小哥

在 Redis 6.0-rc4版本的reiease中，我們看到 Redis支持一個新命令及其子命令： STRALO LCS, LCS是longest common subsequence（最長公共子序列）的縮寫，其定義是：一個數(shù)列{\displaystyle S}，如果分別是兩個或多個已知數(shù)列的子序列，且是所有符合此條件序列中最長的，則{\displaystyle S}稱為已知序列的最長公共子序列。例如x = [A,,B,C,B,D,A,B], y = [B,D,C,A,B,A],則序列[B,C,A]為x和y的最長公共子序列。LCS在現(xiàn)實生活中有很多應(yīng)用，例如檢測文本相似度，版本控制等，在生物醫(yī)學中，lcs也被用在檢測DNA樣本的相似度。Redis的作者salvatore也在他的twitter中提到使用使用·lcs測試covid-19冠狀病毒的基因序列。（https://twitter.com/antirez/status/1245448546205216777）。

STRALGO LCS命令格式如下：

STRALGO LCS [KEYS ...] [STRINGS ...] [LEN] [IDX] [MINMATCHLEN <len>] [WITHMATCHLEN]

借用官網(wǎng)的例子，如果我們計算ohmytext和mynnewtext兩個字符串的lcs,可以使用如下命令：

STRALGO LCS STRINGS ohmytext mynewtext
"mytext"

</pre>

我們也可以計算兩個鍵相對應(yīng)的字符串值的lcs，通過使用keys參數(shù)，例子如下：

MSET key1 ohmytext key2 mynewtext
OK
STRALGO LCS KEYS key1 key2
"mytext"

</pre>

我們也可以使用len參數(shù)只計算lcs的長度而不返回具體的lcs字符串：

STRALGO LCS STRINGS ohmytext mynewtext LEN
6

</pre>

另外，我們也可以通過idx參數(shù)得到每一個lcs字符的位置。

STRALGO LCS KEYS key1 key2 IDX

"matches"
1. 1. 1. (integer) 4
    2. (integer) 7
  2. 1. (integer) 5
    2. (integer) 8
2. 1. 1. (integer) 2
    2. (integer) 3
  2. 1. (integer) 0
    2. (integer) 1
"len"
(integer) 6

</pre>

如上所示，字符串key1的值（ohmytest）和key2的值（mynewtest）的lcs結(jié)果為字符串1的4-7索引和字符串2的5-8的索引（對應(yīng)著test）和字符串1的2-3的索引和字符串2的0-1的索引（對應(yīng)著my）。因為計算的時候是從后往前計算的，所以輸出的結(jié)果也是相反的。

我們也可以通過提供minmatchlen參數(shù)指定最小的匹配長度，如下所示：

STRALGO LCS KEYS key1 key2 IDX MINMATCHLEN 4

"matches"
1. 1. 1. (integer) 4
    2. (integer) 7
  2. 1. (integer) 5
    2. (integer) 8
"len"
(integer) 6

</pre>

這樣字符串1的2-3的索引和字符串2的0-1的索引（對應(yīng)著my）的匹配就被過濾掉了。

求解LCS及其長度本身是個·np-hard問題，但可以通過使用空間換時間的思想使用動態(tài)規(guī)劃在多項式時間來求解。

具體思路如下，假如我們要求數(shù)組x [x1,x2,x3,x4 … xm]和數(shù)組y [y1,y2,y3,y4 … yn]的lcs長度，如果xm 和yn的值相等，那么原問題便轉(zhuǎn)化為x的子數(shù)組x [x1,x2,x3,x4 … xm-1] 和y [y1,y2,y3,y4 … yn-1]的lcs長度加一。相反地，如果xm 和yn的值不相等，則lcs的長度為lcs(x[x1,x2,x3,x4 … xm-1], y[y1,y2,y3,y4 … yn]) 和lcs(x[x1,x2,x3,x4 … xm], y[y1,y2,y3,y4 … yn-1])的較大值。綜上所述，通過轉(zhuǎn)換為子問題來求解，狀態(tài)轉(zhuǎn)移方程如下：

image

我們在具體實現(xiàn)時，可以通過建立動態(tài)規(guī)劃表，來存儲之前計算過的兩個前綴字串的lcs長度。例如如果我們要計算mynewtest和ohmytest的lcs長度，則動態(tài)規(guī)劃表如下：

image

我們從上向下，從左向右填充填充動態(tài)規(guī)劃表，需要注意的是邊界情況。在兩個前綴子串有一個為空的時候，lcs的長度也為0.當xi和yj相同時，則當前l(fā)cs長度為左上角的方格的值加1，當xi和yj不相同時，則當前l(fā)cs長度為左邊或右邊方格中的值的最大值。這樣，當處理到最右下角的方格時，計算出的值就為兩個字符串的lcs長度。

接下來我們要考慮的是如果知道lcs長度的動態(tài)規(guī)劃表，怎樣來得到lcs呢？我們可以從后往前查找，如果當前位置i，j滿足xi 等于yj時，記錄當前值到result數(shù)組里，并將i和j各減一。如果當前位置xi和yj不相等，則查找動態(tài)規(guī)劃表，如果lcs（i-1，j）大于lcs（i，j-1）時，i減一，反之j減一。重復以上過程直到i或j有一個為零為止。下表記錄了計算lcs的過程。