2

给出了主要的 DNA 序列（一个字符串）（比如说 string1）和另一个要搜索的字符串（比如说 string2）。您必须在 string1 中找到最小长度窗口，其中 string2 是子序列。
string1 = "abcdefababaef"
string2 = "abf"

我想到但似乎不起作用的方法：
1. 使用最长公共子序列（LCS）方法并检查（LCS 的长度 = string2 的长度）。但这会给我 string2 是否作为子序列存在于 string1 中，但不是最小的窗口。
2. KMP 算法，但不知道如何修改它。
3. 准备string2 中string1 的{characters: pos of characters} 的映射。喜欢： { a : 0,6,8,10
b : 1,7,9
f : 5,12 }
然后一些方法来找到最小窗口并仍然保持“abf”的顺序

我不确定我是否在思考正确的方向，或者我完全偏离了方向。
有没有已知的算法，或者有人知道任何方法吗？请建议。
提前致谢。

4

3 回答 3

0

动态规划！这是一个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;
}
于 2014-08-28T10:22:41.687 回答
0

您可以进行LCS并在LCS结果的 DP 表String1上String2使用递归找到所有最大子序列。然后计算每个LCS的窗口长度，你可以得到它的最小值。如果分支已经超过找到的当前最小窗口的大小，您也可以停止分支。

检查读出所有 LCS：-

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

于 2014-08-28T09:44:50.997 回答
0

我在 CareerCup 上发现了一个类似的面试问题，唯一的区别是它是一个整数数组而不是字符数组。我借用了一个想法并做了一些更改，如果您在阅读此 C++ 代码后有任何问题，请告诉我。

我在这里要做的是：函数中的for循环main用于遍历给定数组的所有元素，并找到遇到子数组第一个元素的位置，一旦找到，我调用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;
}
于 2016-09-04T22:40:08.240 回答