Finding Disjoint Motifs in a Gene

1. 暴力滑窗+子序列验证【错误】

最最粗暴的方法就是使用 时间生成motif1 + motif2的所有interwoven可能，然后再使用KMP在DNA中查找是否出现，单次两motif组合检查时间复杂度为 ，其中共有n个motif，两两组合大约有 个，所以总时间复杂度为

我的想法：
使用长度为|u|+|t|的滑动窗口记录s子串字符出现个数cnt，若该窗口内字符出现个数等于u,t字符出现个数时，通过删除子序列u得到剩余字符组合后是否等于t 来判断。

import sys
from typing import List
stdin = sys.stdin
DNA = stdin.readline().strip()
motifs = [motif.strip() for motif in stdin if motif.strip()]
print(DNA, motifs)
def check(s: str, motif1: str, motif2: str) -> bool:
    n, m = len(s), len(motif1)
    match = [True] * n
    i = j = 0
    while i < n and j < m:
        if s[i] == motif1[j]:
            j += 1
            match[i] = False  # 其中一个使用删除它
        i += 1
    return j == m and ''.join(s[i] for i, v in enumerate(match) if v) == motif2
def disjointMotifs(DNA: str, motifs: List[str]) -> int:
    """枚举motif组合，使用滑动窗口在DNA找这个可能组合，使用子序列验证"""
    n = len(motifs)
    ans = [[0] * n for _ in range(n)]
    from collections import Counter
    for i in range(n):
        for j in range(i, n):
            motif = Counter(motifs[i] + motifs[j])
            # 初始化长度为 K-1 的滑窗
            K = len(motifs[i]) + len(motifs[j])
            window = Counter()
            for k in range(K - 1):
                window[DNA[k]] += 1
            for k in range(K - 1, len(DNA)):
                window[DNA[k]] += 1  # 滑入 DNA[k] 元素
                # 检测该窗口字符是否是 Disjoint Motifs 组合
                if window == motif and check(DNA[k-K+1:k+1], motifs[i], motifs[j]):
                    ans[i][j] = ans[j][i] = 1
                    break
                window[DNA[k - K + 1]] -= 1  # 滑出 DNA[k - K + 1] 元素
                if 0 == window[DNA[k - K + 1]]:  # 删除出现次数为零
                    window.pop(DNA[k - K + 1])
    return ans
for lst in disjointMotifs(DNA, motifs):
    for x in lst:
        print(x, end=' ')
    print()

但是上面判断子序列组成上出错了：例如s = 'CCACGCA', t = 'CCGC', u = 'CAA' 使用上面的check 函数输出为 False。下面在s串底部分别使用^, &表示其构成t, u串字符。

我的结果：
C C A C G C A
^ ^ $ $ ^ ^ $
预期结果：
C C A C G C A
^ $ $ ^ ^ ^ $

问题：上面check函数每次只取匹配的最左侧字符造成不匹配，难道需要枚举出所有位置组合的子序列挨个检测有效性吗？

paper：