从两个字符串中以Python编程执行前缀压缩的程序

假设我们有两个字符串s和t（均包含小写英文字母）。我们必须查找大小为3的一系列配对，其中每个配对都是这种形式（l，k），其中k是字符串，l是其长度。现在，在这三个配对中，第一个包含s和t的最长公共前缀p的子串，然后s的剩余部分是s’，t的剩余部分是t’。因此，最终列表将像[(p的长度，p)，（s’的长度，s’），（t’的长度，t’）]一样。

因此，如果输入是s =“science” t =“school”，则输出将是[(2，’sc’)，（5，’ience’），（4，’hool’）]

要解决此问题，我们将遵循以下步骤：

lcp：空字符串
对于范围为0到s大小或t大小的最小值的i，执行以下操作
- 如果s[i]与t[i]相同，则
  - lcp：lcp + s[i]
s_rem：从索引（lcp的大小）到结尾的s的子串
t_rem：从索引（lcp的大小）到结尾的t的子串
返回三个对的列表[(lcp的大小，lcp)，（s_rem的大小，s_rem），（t_rem的大小，t_rem）]

例子

让我们看看以下实现，以便更好地理解-

def solve(s, t):
  lcp = ''
  for i in range(min(len(s), len(t))):
    if s[i] == t[i]:
      lcp += s[i]

  s_rem = s[len(lcp):]
  t_rem = t[len(lcp):]
  return [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)]

s = "science"
t = "school"
print(solve(s, t))