analysis - 我怎样才能使用贪婪获得 O(m+n) ？

Question

我如何O(m+n)为这种情况设计一个贪心算法

给定两种安排L1and L2, where| L1 | = n和| L2 | = m.

L2据说是L1if 元素可以从L1to get中删除的子序列L2。这意味着对于m每个. 设计一个贪心算法，检测是否是 的子序列，如果是 的子序列，则输出索引。ik∈ [0..n]L1 [ik] = L2 [j]j∈ [0..m]O (n + m)L2L1ikL1L2L1

例子：

Input L1 = [1 2 3 4 5 6 7 8 9 10] L2 = [3 5 7 9] Output ik = [2 4 6 8]

Input L1 = [2 1 4 3 6 5 7 8 9 10] L2 = [1 6 5 10] Output ik = [1 4 5 9]

Input L1 = [1 2 3 4 5 6 7 8 9 10] L2 = [1 5 9 12] Output L2 is not subsequence of L1

我一直在用这个做经典代码

bool isSubsequence(string str1, string str2) {
    int i=0;
    int j=0;

while (j<str1.length() && i<str2.length()){
    if(str1[j]==str2[i]){
        cout<<i<<" ";
        j++;
    }

    i++;
} 
    
return j==str1.length(); 
}

但我不知道如何O(m+n)使用贪婪。谢谢

标签： analysisgreedy