Pythonで文字列とその接尾辞の類似性を見つけるプログラム

文字列'input_str'が与えられたとします。 input_strからすべてのサフィックスを決定した場合;たとえば、文字列が「abcd」の場合、接尾辞は「abc」、「bcd」、「cd」、「d」です。ここで、input_strとすべてのサフィックスの類似性を、input_strの最長の共通プレフィックスとサフィックスの長さでチェックします。 input_strとすべてのサフィックスの類似性の合計を返す必要があります。

したがって、入力がinput_str ='tpotp'のような場合、出力は7

文字列「tpotp」のすべてのサフィックスは、「tpotp」、「potp」、「otp」、「tp」、および「p」です。

すべてのサフィックスとinput_strの類似性を確認すると、-

'tpotp' similarity 5
'potp' similarity 0
'otp' similarity 0
'tp' similarity 2
'p' similarity 0

Sum of similarities = 5 + 0 + 0 + 2 + 0 = 7.

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

• return_list：=input_strのサイズを含む新しいリスト
• i：=1
• p：=0
• q：=0
• r：=0
• i
• q
• return_list [i-q]> =q + p-iの場合、
  • r：=q + p-i
  • p：=0
  • q：=0
• それ以外の場合、
  • return_listの最後にreturn_list[i-q]を挿入します
  • i：=i + 1
  • r：=0

def solve(input_str):
   return_list = [len(input_str)]
   i = 1
   p, q = 0,0
   r = 0
   while i < len(input_str):
      if q < i < (q+p):
         if return_list[i-q] >= q+p-i:
            r = q + p - i
            p, q = 0, 0
         else:
            return_list.append(return_list[i-q])
            i += 1
            r = 0
      else:
         while i + r < len(input_str) and input_str[r] == input_str[i+r]:
            r += 1
         return_list.append(r)
         p,q = r,i
         i += 1
         r = 0
      return sum(return_list)

print(solve('tpotp'))

'tpotp'

5