string1中的最小長度窗口其中string2是子序列

Question

主要的DNA序列（字符串）被給出（讓我們說string1）和另一個字符串來搜索（讓我們說string2）。您必須在string1中找到最小長度窗口，其中string2是子序列。
字符串1 =「abcdefababaef」
字符串2 =「ABF」

，我想到了，但似乎並不奏效途徑：
1.使用最長公共子序列（LCS）方法，並檢查（長度LCS = string2的長度）。但是，這會給我string2是否存在於string1中作爲子序列，但不是最小的窗口。
2. KMP算法，但不知道如何修改它。
3.準備字符串2中的字符串{characters：pos of characters}的string1的映射。像： {A：0,6,8,10
B：1,7,9
F：5,12}
然後一些方法來找到分鐘窗口，仍維持 「ABF」

的順序

我不確定我是在正確的方向思考還是我完全不在。
有沒有一個已知的算法，或者有沒有人知道任何方法？請建議。
在此先感謝。

Answer 1

你可以做LCS，發現使用的LCS結果的規劃表遞歸在String2的String1所有的最大的子序列。然後計算每個LCS的窗口長度，您可以獲得最小值。如果分支已經超過當前找到的最小窗口的大小，您也可以停止分支。

檢查讀出所有LCS： -

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Answer 2

動態規劃！ 這裏是一個C實現

#include <iostream> 
#include <vector> 

using namespace std; 

int main() { 
    string a, b; 
    cin >> a >> b; 

    int m = a.size(), n = b.size(); 
    int inf = 100000000; 

    vector < vector <int> > dp (n + 1, vector <int> (m + 1, inf)); // length of min string a[j...k] such that b[i...] is a subsequence of a[j...k] 
    dp[n] = vector <int> (m + 1, 0); // b[n...] = "", so dp[n][i] = 0 for each i 

    for (int i = n - 1; i >= 0; --i) { 
     for (int j = m - 1; j >= 0; --j) { 
      if(b[i] == a[j]) dp[i][j] = 1 + dp[i+1][j+1]; 
      else    dp[i][j] = 1 + dp[i][j+1]; 
     } 
    } 

    int l, r, min_len = inf; 

    for (int i = 0; i < m; ++i) { 
     if(dp[0][i] < min_len) { 
      min_len = dp[0][i]; 
      l = i, r = i + min_len; 
     } 
    } 

    if(min_len == inf) { 
     cout << "no solution!\n"; 
    } else { 
     for (int i = l; i < r; ++i) { 
      cout << a[i]; 
     } 
     cout << '\n'; 
    } 

    return 0; 
} 

Answer 3

我發現CareerCup類似的面試問題，唯一的區別是它的整數，而不是一個字符數組。我借用了一個想法並做了一些修改，在閱讀完C++代碼後，如果您有任何疑問，請告訴我。

我在這裏要做的是：main函數中的for循環用於遍歷給定數組的所有元素，並找到我遇到子陣列第一個元素的位置，一旦找到，我稱之爲find_subsequence函數，其中我遞歸匹配給定數組的元素與子數組在同一時間保留元素的順序。最後，find_subsequence返回位置，我計算子序列的大小。

請原諒我的英文，希望我能更好地解釋它。

#include "stdafx.h" 
#include "iostream" 
#include "vector" 
#include "set" 
using namespace std; 
class Solution { 
public: 
    int find_subsequence(vector<int> s, vector<int> c, int arrayStart, int subArrayStart) { 
    if (arrayStart == s.size() || subArrayStart ==c.size()) return -1; 
    if (subArrayStart==c.size()-1) return arrayStart; 

    if (s[arrayStart + 1] == c[subArrayStart + 1]) 
     return find_subsequence(s, c, arrayStart + 1, subArrayStart + 1); 
    else 
     return find_subsequence(s, c, arrayStart + 1, subArrayStart); 
    } 
}; 

int main() 
{ 
vector<int> v = { 1,5,3,5,6,7,8,5,6,8,7,8,0,7 }; 
vector<int> c = { 5,6,8,7 }; 
Solution s; 
int size = INT_MAX; 
int j = -1; 
for (int i = 0; i <v.size(); i++) { 
    if(v[i]==c[0]){ 
     int x = s.find_subsequence(v, c, i-1, -1); 
     if (x > -1) { 
      if (x - i + 1 < size) { 
       size = x - i + 1; 
       j = i; 
      } 
      if (size == c.size()) 
       break; 
     } 
    } 
} 
cout << size <<" "<<j; 
return 0; 
}