查找另一個字符串中的最大相似子字符串

我給出了兩個字符串，n1和n2。除了這些，我所提供的數字，K.查找另一個字符串中的最大相似子字符串

現在我需要找到三個號碼 - I，J，L這樣的：子串開始於指數N1我，長度l，具有atmost K與n2的索引j處的長度l的子串不匹配。這是K不相似性可能的最大子串。

一個例子應該清楚：
N1 =大不里士
N2 =托裏諾
K = 2
則輸出應該是：
I = 2
J = 1
L = 4
[因爲「briz」和「orin」有兩個不相似性]

當前方法：對於n1的每個子序列，我試圖找到n2中的最大公共子序列st K不匹配）。任何人都有更好的方法來更有效地解決這個問題？

來源

2012-02-18 letsc

如果我理解正確的話，在我看來是近似串匹配的變體（請參見：http://en.wikipedia.org/wiki/Approximate_string_matching）。 – 2012-02-18 08:52:44

可能是近似字符串匹配和查找最長公共子字符串的組合：http://en.wikipedia.org/wiki/Longest_common_substring_problem – 2012-02-19 05:09:50

來自hackerrank：https://www.hackerrank.com/challenges/substring-diff – 2014-04-03 22:08:33

我認爲你可以像LCS動態規劃做到這一點，在S1在我

常見的（I，J，L，K）=最大子strats，具有長度l，且至少爲k錯配（用於所有i < = n，j < = n，l < = n，k < = K）首先，您應該計算普通的（i，j，l，0），這是微不足道的。

對於k> 0：

對於所有1 ≤˚F≤ k-1個& & KF ≤噸≤ L-1：

如果str1 [I + LT] = STR2 [J加LT]
common(i,j,l,k) = maximum{common(i,j,l-t-1,k-f) + common(i,j,t,f-1)} 
else 
    common(i,j,l,k) = maximum{common(i,j,l-t,k-f) + common(i,j,t,f)} 

來源

2012-02-18 09:05:31

它保證有一個簡單解決方案？在這種情況下會發生什麼：

N1 = qertyq

N2 = quertac

K = 2

將有多個解決方案的算法 0,0,6

1,1,5-

2,2,4

3,3,3

2,2,2

，如果你保證，只有一個解決問題的辦法，我認爲賽義德是正確的，你必須使用動態規劃來解決它

來源

2012-02-19 04:48:36

我沒有認爲你的問題是正確的。 – letsc 2012-02-19 16:39:02

這裏是一個簡單的暴力。它計算每個可能的i和j對的長度。複雜度是O（n1.length * n2。長度* min（n1.length，n2.length））。當兩個字符串長度爲n時，這是O（n ）。

for (i = 0; i < n1.length; i++) 
{ 
    for (j = 0; j < n2.length; j++) 
    { 
     errors = 0 
     len = 0 

     while (errors <= k && i+len < n1.length && j+len < n2.length) 
     { 
      if (n1[i+len] != n2[j+len]) errors++ 
      if (errors <= k) len++ 
     } 

     if (len > best) update best 
    } 
}

下面是一個更有效的解決方案，通過i和j之間的所有可能的偏移量推移，設置有k個錯誤的子串在該偏移量，然後轉移沿子（與恰好有k誤差保持它）並觀察每個點的長度。複雜度爲O（（n1.length + n2.length）* min（n1.length，n2.length））。當兩個字符串長度爲n時，這是O（n ）。

for (offset = -n1.length; offset < n2.length; offset++) 
{ 
    // j is equal to (i + offset) 

    start = (offset > 0) ? 0 : -offset 
    stop = min(n1.length, n2.length - offset) 

    errors = 0 
    e = start // e is one past the end of the sequence, so l = e - i 

    for (i = start; i < stop; i++) 
    { 
     // move the end of the substring to maintain exactly k errors 
     while (e < stop && (errors < k || n1[e] == n2[e+offset])) 
     { 
      if (n1[e] != n2[e+offset]) errors++ 
      e++ 
     } 

     if (e - i > best) update best 

     if (n1[i] != n2[i+offset]) errors-- 
    } 
}

來源

2012-02-21 10:38:30 tom

查找另一個字符串中的最大相似子字符串

回答

如果str1 [I + LT] = STR2 [J加LT]

相關問題