（更新：我已经重写了这个答案的开头，包括对复杂性的讨论以及一些替代方法和潜在风险的讨论。）
（简短的回答，我能想到的在 O(nm) 方法之上的唯一真正改进是观察到我们通常不需要计算表中的所有n次m条目。我们可以只计算我们需要的那些单元格。但实际上它可能非常好，具体取决于数据集。）
澄清问题：我们有一个S长度n字符串和一个T长度字符串m。允许的最大间隙是k- 这个间隙也将在字符串的开头和结尾强制执行。间隙是两个匹配字符之间的不匹配字符数 - 即如果字母相邻，则间隙为0，而不是1。
想象一个有n+1行和m+1列的表格。
0 1 2 3 4 ... m
--------------------
0 | ? ? ? ? ? ?
1 | ? ? ? ? ? ?
2 | ? ? ? ? ? ?
3 | ? ? ? ? ? ?
... |
n | ? ? ? ? ? ?
首先，我们可以定义行r和列中的条目c是一个二进制标志，它告诉我们 of 的第一个字符是否是 的第一个r字符的有效S子k序列。（不用担心如何计算这些值，甚至这些值是否有用，我们只需要先明确定义它们。）cT
然而，这个二进制标志表并不是很有用。不可能轻松地将一个单元格计算为附近单元格的函数。相反，我们需要每个单元存储稍微多一点的信息。T除了记录相关字符串是否为有效子序列外，我们还需要在我们的子字符串（带有字符的子字符串）的末尾记录连续不匹配字符的个数c。例如，如果are的第一个r=2字符和Sare"ab"的第一个c=3字符，那么这里有两种可能的匹配：第一个字符显然相互匹配，但可以与后者匹配。因此，我们可以选择留下一个或T"abb"bb最后零unmatched bs。我们在表中记录哪一项？
答案是，如果一个单元格有多个有效值，那么我们取最小的一个。我们希望在匹配字符串的其余部分的同时让自己的生活尽可能轻松，这是合乎逻辑的，因此最后的间隙越小越好。警惕其他不正确的优化 - 我们不希望匹配尽可能多的字符或尽可能少的字符。那会适得其反。但是，对于给定的一对字符串S,T，找到使最后间隙最小化的匹配项（如果有任何有效匹配项）是合乎逻辑的。
另一项观察是，如果字符串S比 短得多T，则它无法匹配。k这显然也取决于。S可以覆盖的最大长度是rk，如果小于c，那么我们可以很容易地标记(r,c)为-1。
（可以做出任何其他优化语句吗？）
我们不需要计算此表中的所有值。不同可能状态的数量为 k+3。它们以“未定义”状态 ( ?) 开始。如果这对（子）字符串无法匹配，则状态为-。如果匹配是可能的，那么单元格中的分数将是一个介于 0 和 k 之间的数字，包括最后的不匹配连续字符的最小可能数量。这给了我们总共 k+3 个状态。
我们只对表格右下角的条目感兴趣。如果f(r,c)是计算特定单元格的函数，那么我们只对 感兴趣f(n,m)。可以根据附近的值计算特定单元格的值。我们可以构建一个递归算法，将r和c作为输入，并根据附近的值执行相关的计算和查找。如果此函数查找f(r,c)并找到 a ?，它将继续计算它，然后存储答案。
存储答案很重要，因为算法可能会多次查询同一个单元格。而且，某些单元格永远不会被计算。我们刚开始尝试计算一个单元格（右下角），并根据需要进行查找、计算和存储。
这是“明显的” O(nm) 方法。这里唯一的优化是观察到我们不需要计算所有单元格，因此这应该使复杂度低于 O(nm)。当然，对于非常糟糕的数据集，您最终可能会计算几乎所有的单元格！因此，很难对此进行官方的复杂性估计。
最后，我应该说如何计算一个特定的单元格f(r,c)：
r==0和c <= k，那么f(r,c) = 0。 空字符串可以匹配包含最多k字符的任何字符串。r==0和c > k，那么f(r,c) = -1。比赛时间太长了。S[r]==T[c]和f(r-1,c-1) != -1，那么f(r,c) = 0。这是最好的情况 - 没有尾随差距的匹配。f(r,c-1) != -1和f(r,c) < k，那么f(r,c) = f(r,c-1)+1。f(r,c) = -1.这个答案的其余部分是我最初的基于 Haskell 的方法。它的一个优点是它“理解”它不需要计算每个单元，只在必要时计算单元。但这可能会导致多次计算一个单元格的效率低下。
*另请注意，Haskell 方法有效地解决了镜像中的问题 - 它试图从结尾的子字符串S和T最小的不匹配字符的前导字符串中构建匹配。我没有时间以它的“镜像”形式重写它！
递归方法应该有效。我们想要一个接受三个参数的函数，int K、StringS和 String T。然而，我们不只是想要一个关于 S 是否是 T 的有效 k 子序列的布尔答案。
对于这种递归方法，如果 S 是有效的 k 子序列，我们还想通过返回从 T 的开头可以删除多少个字符来了解可能的最佳子序列。我们想找到“最好的”子序列。如果 S 和 T 不可能有 k-子序列，那么我们返回 -1，但如果可能，那么我们希望返回可以从 T 中提取的最少字符数，同时保留 k-子序列属性。
helloworld
l r d
这是一个有效的 4 子序列，但最大的间隔（最多）有四个字符 ( lowo)。这是最好的子序列，因为它在开头 ( he) 处只留下两个字符的间隙。或者，这是另一个具有相同字符串的有效 k 子序列，但它不是那么好，因为它在开始时留下了 3 个间隙：
helloworld
l r d
这是用 Haskell 编写的，但应该很容易用任何其他语言重写。我将在下面更详细地分解它。
best :: Int -> String -> String -> Int
-- K S T return
-- where len(S) <= len(T)
best k [] t_string -- empty S is a subsequence of anything!
| length(t_string) <= k = length(t_string)
| length(t_string) > k = -1
best k sss@(s:ss) [] = (-1) -- if T is empty, and S is non-empty, then no subsequence is possible
best k sss@(s:ss) tts@(t:ts) -- both are non-empty. Various possibilities:
| s == t && best k ss ts /= -1 = 0 -- if s==t, and if best k ss ts != -1, then we have the best outcome
| best k sss ts /= -1
&& best k sss ts < k = 1+ (best k sss ts) -- this is the only other possibility for a valid k-subsequence
| otherwise = -1 -- no more options left, return -1 for failure.
逐行分析：（Haskell 中的注释以 开头--）
best :: Int -> String -> String -> Int
一个接受一个 Int 和两个字符串并返回一个 Int 的函数。如果不可能有 k 子序列，则返回值为 -1。否则它将返回一个介于 0 和 K（含）之间的整数，告诉我们 T 开始处可能的最小间隙。
我们只是按顺序处理案件。
best k [] t -- empty S is a subsequence of anything!
| length(t) <= k = length(t)
| length(t) > k = -1
上面，我们处理了 S 为空 ( []) 的情况。这很简单，因为空字符串始终是有效的子序列。但是要测试它是否是一个有效的k-subsequence，我们必须计算 T 的长度。
best k sss@(s:ss) [] = (-1)
-- if T is empty, and S is non-empty, then no subsequence is possible
那条评论解释了它。这给我们留下了两个字符串都是非空的情况：
best k sss@(s:ss) tts@(t:ts) -- both are non-empty. Various possibilities:
| s == t && best k ss ts /= -1 = 0 -- if s==t, and if best k ss ts != -1, then we have the best outcome
| best k sss ts /= -1
&& best k sss ts < k = 1+ (best k sss ts) -- this is the only other possibility for a valid k-subsequence
| otherwise = -1 -- no more options left, return -1 for failure.
tts@(t:ts)匹配一个非空字符串。字符串的名称是tts。但是在 Haskell 中还有一个方便的技巧，允许您为字符串中的第一个字母 ( t) 和字符串的其余部分( ) 命名ts。这里ts应该作为复数形式大声朗读t——s这里的后缀是“复数”的意思。我们说有一个t和一些ts，它们一起构成完整的（非空）字符串。
最后一段代码处理两个字符串都非空的情况。这两个字符串称为sssand tts。但是为了省去我们编写head sss和tail sss访问字符串的第一个字母和字符串剩余部分的麻烦，我们只需@(s:ss)告诉编译器将这些数量存储到变量s和ss. 例如，如果这是 C++，您将获得与char s = sss[0];函数的第一行相同的效果。
最好的情况是第一个字符匹配s==t并且字符串的其余部分是有效的 k-subsequence best k sss ts /= -1。这允许我们返回 0。
如果当前完整字符串 ( sss) 是其他字符串 ( ts) 的剩余部分的有效 k 子序列，则唯一的其他成功可能性。我们将其加 1 并返回，但如果差距太大，则例外。
不要改变最后五行的顺序非常重要。它们按分数“好”的降序排列。我们希望首先测试并返回最好的可能性。
朴素的递归解决方案。Bonus := 返回值是字符串可以匹配的方式数。
#include <stdio.h>
#include <string.h>
unsigned skipneedle(char *haystack, char *needle, unsigned skipmax)
{
unsigned found,skipped;
// fprintf(stderr, "skipneedle(%s,%s,%u)\n", haystack, needle, skipmax);
if ( !*needle) return strlen(haystack) <= skipmax ? 1 : 0 ;
found = 0;
for (skipped=0; skipped <= skipmax ; haystack++,skipped++ ) {
if ( !*haystack ) break;
if ( *haystack == *needle) {
found += skipneedle(haystack+1, needle+1, skipmax);
}
}
return found;
}
int main(void)
{
char *ab = "ab";
char *test[] = {"ab" , "accb" , "abcccb" , "abcb", NULL}
, **cpp;
for (cpp = test; *cpp; cpp++ ) {
printf( "[%s,%s,%u]=%u \n"
, *cpp, ab, 2
, skipneedle(*cpp, ab, 2) );
}
return 0;
}
一个 O(p*n) 解，其中 p = T 中 S 的可能子序列数。
扫描字符串 T 并维护 S 的可能子序列列表，其中包含
1. 找到的最后一个字符的索引和
2. 找到要删除的字符数
继续在 T 的每个字符处更新此列表。
不确定这是否是您的要求，但您可以从每个字符串创建一个字符列表，并在另一个列表中搜索一个列表的实例，然后 if(list2.length-K > list1.length) 返回 false。
考虑一种递归方法：让int f(int i, int j)表示 S[i...n] 匹配 T[j...m] 在开始时的最小可能间隙。如果不存在这样的匹配则f返回。-1这是 的实现f：
int f(int i, int j){
if(j == m){
if(i == n)
return 0;
else
return -1;
}
if(i == n){
return m - j;
}
if(S[i] == T[j]){
int tmp = f(i + 1, j + 1);
if(tmp >= 0 && tmp <= k)
return 0;
}
return f(i, j + 1) + 1;
}
如果我们将这种递归方法转换为动态规划方法，那么我们的时间复杂度可以为O(nm).
以下是一个建议的算法： - O(|T|*k) 平均情况
1> 扫描 T 并将字符索引存储在哈希表中：-
例如。S = "abc" T = "ababbc"
符号表条目：-
一个 = 1 3
b = 2 4 5
c = 6
2.> 我们知道 isValidSub(S,T) = isValidSub(S(0,j),T) && (isValidSub(S(j+1,N),T)||....isValidSub(S(j +K,T),T))
a.> 我们将使用自下而上的方法来解决上述问题
b.> 我们将维护一个有效的数组 Valid(len(S))，其中每条记录都指向一个哈希表（在我们进一步求解时进行解释）
c.> 从 S 的最后一个元素开始，查找符号表中字符对应存储的索引
例如。在上面的例子中 S[last] = "c"
在符号表中 c = 6
现在我们将 (5,6) , (4,6) ,.... (6-k-1,6) 之类的记录放入 Valid(last) 的哈希表中
解释： - 因为 s(6,len(S)) 是有效的子序列，因此 s(0,6-i) ++ s(6,len(S)) （其中 i 在范围内（1,k+1））也是有效的子序列，前提是 s(0,6-i) 是有效的子序列。
3.> 开始从最后一个到 0 元素填充有效数组：-
a.> 从对应于 S[j] 的哈希表条目中获取一个索引，其中 j 是我们正在分析的有效数组的当前索引。
b.> 检查索引是否在 Valid(j+1) 中，如果小于则将 (indice-i,indice) where i in range(1,k+1) 添加到 Valid(j) 哈希表中
例子：-
S = "abc" T = "ababbc"
迭代 1：
j = 长度 (S) = 3
S[3] = 'c'
符号表：c = 6
在 Valid(j) 中添加 (5,6),(4,6),(3,6) 作为 K = 2
有效(3) = {(5,6),(4,6),(3,6)}
j = 2
迭代 2：
S[j] = 'b'
符号表：b = 2 4 5
在 Valid(3) 中查找 2 => 未找到 => 跳过
在 Valid(3) 中查找 4 => 找到 => 添加 Valid(2) = {(3,4),(2,4),(1,4)}
在 Valid(3) 中查找 5 => 找到 => 添加 Valid(2) = {(3,4),(2,4),(1,4),(4,5)}
j = 1
迭代 3：
S[j] = "一个"
符号表：a = 1 3
在 Valid(2) 中查找 1 => 未找到
在 Valid(2) => found => stop 中查找 3，因为它是最后一次迭代
结尾
因为 3 在 Valid(2) 中找到，这意味着存在从 T 开始的有效子序列
开始 = 3
4.> 重构在有效数组中向下移动的解决方案：-
例子 ：
开始 = 3
在 Valid(2) 中查找 3 => found (3,4)
在 Valid(3) 中查找 4 => found (4,6)
结尾
重构的解决方案 (3,4,6) 确实是有效的子序列
请记住，如果我们在该迭代中添加了 (3,5) 而不是 (3,4)，则 (3,5,6) 也可以是一个解决方案
时间复杂度和空间复杂度分析：-
时间复杂度：
第 1 步：扫描 T = O(|T|)
第 2 步：使用 HashTable 查找填写所有有效条目 O(|T|*k) 大约为 O(1)
第三步：重构解 O(|S|)
总体平均情况时间：O(|T|*k)
空间复杂度：
符号表 = O(|T|+|S|)
Valid table = O(|T|*k) 可以通过优化来改进
总空间 = O(|T|*k)
Java实现： -
public class Subsequence {
private ArrayList[] SymbolTable = null;
private HashMap[] Valid = null;
private String S;
private String T;
public ArrayList<Integer> getSubsequence(String S,String T,int K) {
this.S = S;
this.T = T;
if(S.length()>T.length())
return(null);
S = S.toLowerCase();
T = T.toLowerCase();
SymbolTable = new ArrayList[26];
for(int i=0;i<26;i++)
SymbolTable[i] = new ArrayList<Integer>();
char[] s1 = T.toCharArray();
char[] s2 = S.toCharArray();
//Calculate Symbol table
for(int i=0;i<T.length();i++) {
SymbolTable[s1[i]-'a'].add(i);
}
/* for(int j=0;j<26;j++) {
System.out.println(SymbolTable[j]);
}
*/
Valid = new HashMap[S.length()];
for(int i=0;i<S.length();i++)
Valid[i] = new HashMap<Integer,Integer >();
int Start = -1;
for(int j = S.length()-1;j>=0;j--) {
int index = s2[j] - 'a';
//System.out.println(index);
for(int m = 0;m<SymbolTable[index].size();m++) {
if(j==S.length()-1||Valid[j+1].containsKey(SymbolTable[index].get(m))) {
int value = (Integer)SymbolTable[index].get(m);
if(j==0) {
Start = value;
break;
}
for(int t=1;t<=K+1;t++) {
Valid[j].put(value-t, value);
}
}
}
}
/* for(int j=0;j<S.length();j++) {
System.out.println(Valid[j]);
}
*/
if(Start != -1) { //Solution exists
ArrayList subseq = new ArrayList<Integer>();
subseq.add(Start);
int prev = Start;
int next;
// Reconstruct solution
for(int i=1;i<S.length();i++) {
next = (Integer)Valid[i].get(prev);
subseq.add(next);
prev = next;
}
return(subseq);
}
return(null);
}
public static void main(String[] args) {
Subsequence sq = new Subsequence();
System.out.println(sq.getSubsequence("abc","ababbc", 2));
}
}
这是一个通常*在 O(N) 中运行并占用 O(m) 空间的实现，其中 m 是长度 (S)。
它使用了测量员链的概念：
想象一系列由长度为 k 的链连接的极点。将第一个极点固定在弦的开头。现在将下一根杆向前移动，直到找到匹配的字符。放置那根杆子。如果有松弛，继续下一个字符；否则之前的杆子已经被拖到了前面，你需要返回并把它移到下一个最近的匹配。重复直到你到达终点或用完松弛。
typedef struct chain_t{
int slack;
int pole;
} chainlink;
int subsequence_k_impl(char* t, char* s, int k, chainlink* link, int len)
{
char* match=s;
int extra = k; //total slack in the chain
//for all chars to match, including final null
while (match<=s+len){
//advance until we find spot for this post or run out of chain
while (t[link->pole] && t[link->pole]!=*match ){
link->pole++; link->slack--;
if (--extra<0) return 0; //no more slack, can't do it.
}
//if we ran out of ground, it's no good
if (t[link->pole] != *match) return 0;
//if this link has slack, go to next pole
if (link->slack>=0) {
link++; match++;
//if next pole was already placed,
while (link[-1].pole < link->pole) {
//recalc slack and advance again
extra += link->slack = k-(link->pole-link[-1].pole-1);
link++; match++;
}
//if not done
if (match<=s+len){
//currrent pole is out of order (or unplaced), move it next to prev one
link->pole = link[-1].pole+1;
extra+= link->slack = k;
}
}
//else drag the previous pole forward to the limit of the chain.
else if (match>=s) {
int drag = (link->pole - link[-1].pole -1)- k;
link--;match--;
link->pole+=drag;
link->slack-=drag;
}
}
//all poles planted. good match
return 1;
}
int subsequence_k(char* t, char* s, int k)
{
int l = strlen(s);
if (strlen(t)>(l+1)*(k+1))
return -1; //easy exit
else {
chainlink* chain = calloc(sizeof(chainlink),l+2);
chain[0].pole=-1; //first pole is anchored before the string
chain[0].slack=0;
chain[1].pole=0; //start searching at first char
chain[1].slack=k;
l = subsequence_k_impl(t,s,k,chain+1,l);
l=l?chain[1].pole:-1; //pos of first match or -1;
free(chain);
}
return l;
}
*我不确定大O。我最初认为它类似于 O(km+N)。在测试中，好的匹配平均小于 2N，失败匹配的平均小于 N。
...但是..有一个奇怪的退化案例。对于从大小字母表中选择的随机字符串A，当k = 2A+1. 即使在这种情况下，它也比 O(Nm) 好，并且当 k 略微增加或减少时，性能恢复到 O(N)。 如果有人好奇，请在这里要点。