Pythonで2つの文字列からプレフィックス圧縮を実行するプログラム

2つの文字列sとtがあるとします（どちらにも小文字の英字が含まれています）。サイズ3のペアのリストを見つける必要があります。ここで、各ペアはこの形式（l、k）です。ここで、kは文字列、lはその長さです。これらの3つのペアのうち、最初のペアには、これら2つの文字列の最長の共通プレフィックスpであるsとtのサブ文字列が含まれ、次に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の部分文字列
• 3つのペアのリストを返す[（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))

入力

"science", "school"

出力

[(2, 'sc'), (5, 'ience'), (4, 'hool')]