Pythonで文字列とその部分文字列の完全な類似性を見つけるプログラム

文字列sがあるとします。文字列の各サフィックスとの類似性の合計を見つける必要があります。ここで、2つの文字列の類似性は、両方の文字列に共通する最長のプレフィックスの長さです。

したがって、入力がs ="pqpqpp"の場合、文字列のサフィックスは "pqpqpp"、 "qpqpp"、 "pqpp"、 "qpp"、 "pp"、および "p"であるため、出力は11になります。これらの部分文字列と文字列"pqpqpp"の類似点は、6,0,3,0,1、および1です。したがって、合計は6 + 0 + 3 + 0 + 1 + 1=11です。

これを解決するには、次の手順に従います-

• 長さ：=sのサイズ
• 合計：=長さ
• z：=0最初に0を含むリスト
• l：=0、r：=0
• 範囲1から長さ-1のkの場合、実行
  • k> rの場合、
    • match：=0
    • インデックス：=k
  • インデックス<長さ、実行
    • s[index]がs[match]と同じ場合、
      • 一致：=一致+1
      • index：=index + 1
    • それ以外の場合、
      • ループから抜け出す
  • zの最後に一致を挿入
  • 一致>0の場合、
    • 合計：=合計+一致
    • l：=k
    • r：=index-1
  • それ以外の場合、
    • z [k-l] <（r-k）+1の場合、
      • zの最後にz[k-l]を挿入します
      • 合計：=合計+ z [k-l]
    • それ以外の場合、
      • match：=r-k
      • インデックス：=r
      • インデックス<長さ、実行
        • s[index]がs[match]と同じ場合、
          • 一致：=一致+1
          • index：=index + 1
        • それ以外の場合、
          • ループから抜け出す
      • zの最後に一致を挿入
      • 合計：=合計+一致
      • l：=k
      • r：=index-1
• 合計を返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(s):
   length = len(s)
   total = length

   z = [0]
   l = 0
   r = 0

   for k in range(1,length):
      if k > r:
         match=0
         index = k
         while index < length:
            if s[index] == s[match]:
               match +=1
               index +=1
            else:
               break
         z.append(match)
         if match > 0:
            total+=match
            l = k
            r = index-1
      else:
         if z[k-l] < (r-k)+1:
            z.append(z[k-l])
            total+=z[k-l]
         else:
            match = r-k
            index = r
            while index < length:
               if s[index] == s[match]:
                  match +=1
                  index +=1
               else:
                  break
            z.append(match)
            total+=match
            l = k
            r = index-1
   return total

s = "pqpqpp"
print(solve(s))

入力

"pqpqpp"

出力

11