<p>要缩短<code>m</code>,您必须查看<code>S</code>中的当前字母
和<code>U</code>。如果两个字母相同,则有两个(非
(排他性)情况:</p>
<ul>
<li><p>您当前正在匹配<code>S</code>的子字符串(这意味着使用
您已经打开了一个字符串,如<code>[aa...</code>中的符号
哪种情况下可以继续匹配</p>
</li>
<li><p>您仍然有严格正数量的子字符串要匹配
在哪种情况下,您可以开始新的匹配(无论您当前是什么)
是否匹配字符串)</p>
</li>
</ul>
<p>为此,您将需要一个用于递归的附加参数
它指定当前是否匹配子字符串</p>
<p>指示已找到与问题匹配的基本情况
是当您到达<code>U</code>的末尾并且<code>m</code>等于<code>0</code>时</p>
<p>以下是实现此解决方案的代码(请注意,该函数处理字母列表而不是字符串):</p>
<pre class="lang-py prettyprint-override"><code>#!/usr/bin/env python3
import functools
def lcs(s, u, m) -> int:
# recursive function
# i: index in list s
# j: index in list j
# m: number of sub-strings to find
# match: are we currently matching a sub-string or not?
@functools.lru_cache(maxsize=10000) # cache the result of our function
def loop(i, j, m, match) -> int:
# base cases
if j >= len(u): # end of u reached => no more letter to look for
if m == 0: # check if have found our m sub-strings
return 1
return 0
if i >= len(s): # end of s reached and still letter to look for
return 0
result = loop(i + 1, j, m, False) # skip the current letter
# letter in s and u are the same (we will move both i and j)
if s[i] == u[j]:
if match: # we are currently matching a sub-string => continue
result += loop(i + 1, j + 1, m, True)
if m > 0: # we can start a new sub-string
result += loop(i + 1, j + 1, m - 1, True)
return result
return loop(0, 0, m, False)
print(lcs(list("aabacaab"), list("aab"), 2))
</code></pre>