S1 内の別の文字列 S2 に最も類似した部分文字列 (つまり、S2 とのハミング距離が最小である S1 内の部分文字列) を N log(N) で見つけるアルゴリズムを作成する必要があります。ここで、N = len(S1) + len(S2)、len(S2)<=len(S1)。
例:
S1 = AGTCAGTC
S2 = GTC
答え: GTC (距離 0)
S1 = AAGGTTCC
S2 = TCAA
答え: TTCC (距離 3)
時間の複雑さは O(N Log(N)) を超えることはできません。スペースの複雑さは問題ではありません。
私の場合、LCS (Longest Common Subsequence) は機能しません。例えば：
S1 = GAATCCAGTCTGTCT
S2 = AATATATAT
LCS の回答: AATCCAGTC
GAATCCAGTCTGTCT
|||
あたたたた
正解：AGTCTGTCT
GAATCCAGTCTGTCT
| | | | | | | | | |
あたたたた