Pythonの文字列で回文境界を見つけるプログラム

文字列strが提供されているとします。文字列の境界線は、その文字列の適切なプレフィックスとサフィックスであるサブストリングです。たとえば、「ab」は文字列「ababab」の境界線です。境界線が回文である場合、境界は回文境界と呼ばれます。ここで、指定された文字列strにf（str）個の回文境界があるとします。 strの空でないすべての部分文字列str_kのf（str_k）の合計を見つける必要があります。合計が大きくなる可能性があるため、10 ^ 9+7でモジュロ演算を実行できます。

したがって、入力がstr ='pqpqp'のような場合、出力は5になります。文字列'pqpqp'の15個のサブ文字列が存在します。ただし、パリンドローム境界を持つサブストリングは4つだけです。文字列は次のとおりです。

pqp : f(pqp) = 1
pqpqp : f(pqpqp) = 2
qpq : f(qpq) = 1
pqp : f(pqp) = 1

The sum of these values are 1 + 2 + 1 + 1 = 5.

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

• 関数palindrome_calculator（）を定義します。これにはinput_dict
  が必要です
  • ans：=0
  • input_dictの値のitem1、item2ごとに、do
    • ans：=ans + item2 *（（item2 --1）/ 2のフロア値）
  • 回答を返す
• 関数str_check（）を定義します。これには文字列が必要です
  • t_str：=string [0]
  • 文字列内の各sについて、
    • sがt_strと同じでない場合、
      • Falseを返す
    • Trueを返す
• 関数string_res（）を定義します。これには文字列が必要です
  • ans：=0
  • 範囲2から文字列のサイズ+1までのiの場合、実行
    • ans：=ans + i *（（i-1）/ 2のフロア値）
    • ans：=ans mod 1000000007
  • 戻って
• str_check（string）がTrueの場合、
  • return string_res（string）
• ans：=0
• odd_list：=新しいリスト、新しいマップ、および1を含む新しいリスト
• 文字列内の各sについて、
  • sがodd_list[1]に存在しない場合、
    • odd_list [1、s]：=0
  • odd_list [1、s]：=odd_list [1、s] + 1
• 0から文字列のサイズまでの範囲のiについては、
  • odd_list[0]の最後にiを挿入します
• ans：=ans + palindrome_calculator（odd_list [1]）
• even_list：=新しいリスト、新しいマップ、および1を含む新しいリスト
• 0から文字列のサイズ-1までの範囲のiの場合、do
  • string[i]がstring[i+ 1]と同じ場合、
    • even_list[0]の最後にiを挿入します
    • tmp：=string[インデックスiからi+2へ]
    • tmpがeven_list[1]に存在しない場合、
      • even_list [1、tmp]：=0
    • even_list [1、tmp]：=even_list [1、tmp] + 1
• ans：=ans + palindrome_calculator（even_list [1]）
• 範囲3から文字列のサイズまでの値の場合は
  • val mod 2が0と同じ場合、
    • wt：=even_list
  • それ以外の場合、
    • wt：=odd_list
  • new_t：=新しいリスト、新しいマップ、およびvalを含む新しいリスト
  • wt [0]の各インデックスについて、実行します
    • index-1>=0かつindex+val-2<文字列のサイズおよびstring[index-1]がstring[index+ val-2]と同じである場合、
      • new_t[0]の最後にインデックス-1を挿入
      • tmp：=string[インデックスインデックス-1からインデックス-1+val]
      • tmpがnew_t[1]に存在しない場合、
        • new_t [1、tmp]：=0
      • new_t [1、tmp]：=new_t [1、tmp] + 1
  • ans：=ans + palindrome_calculator（new_t [1]）
  • ans：=ans mod 1000000007
  • val mod 2が0と同じ場合、
    • even_list：=new_t
  • それ以外の場合、
    • odd_list：=new_t
• 回答を返す

例

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

def palindrome_calculator(input_dict):

   ans = 0
   for item1, item2 in input_dict.items():
      ans += item2 * (item2 - 1) // 2
   return ans

def str_check(string):
   t_str = string[0]
   for s in string:
      if s != t_str:
         return False
   return True

def string_res(string):
   ans = 0
   for i in range(2, len(string) + 1):
      ans += i * (i - 1) // 2
      ans %= 1000000007
   return ans

def solve(string):
   if str_check(string):
      return string_res(string)
   ans = 0
   odd_list = [[], {}, 1]
   for s in string:
      if s not in odd_list[1]:
         odd_list[1][s] = 0
      odd_list[1][s] += 1
   for i in range(len(string)):
      odd_list[0].append(i)
   ans += palindrome_calculator(odd_list[1])
   even_list = [[], {}, 1]
   for i in range(len(string) - 1):
      if string[i] == string[i + 1]:
         even_list[0].append(i)
         tmp = string[i:i + 2]
         if tmp not in even_list[1]:
            even_list[1][tmp] = 0
         even_list[1][tmp] += 1
   ans += palindrome_calculator(even_list[1])
   for val in range(3, len(string)):
      if val % 2 == 0:
         wt = even_list
      else:
         wt = odd_list
      new_t = [[], {}, val]
      for index in wt[0]:
         if index - 1 >= 0 and index + val - 2 < len(string) and string[index - 1] == string[index + val - 2]:
            new_t[0].append(index - 1)
            tmp = string[index - 1 : index - 1 + val]
            if tmp not in new_t[1]:
               new_t[1][tmp] = 0
            new_t[1][tmp] += 1
      ans += palindrome_calculator(new_t[1])
      ans %= 1000000007
      if val % 2 == 0:
         even_list = new_t
      else:
         odd_list = new_t
   return ans

print(solve('pqpqp'))

入力

'pqpqp'

出力

5