Pythonで特定の文字列のすべての異なる回文サブ文字列を検索します

小文字のASCII文字を含む文字列があるとすると、その文字列のすべての別個の連続した回文部分文字列を見つける必要があります。

したがって、入力が「bddaaa」のような場合、出力は[a、aa、aaa、b、d、dd]

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

• m：=新しい地図
• n：=sのサイズ
• matrix：=0のn個の0の2つの行を作成します
• s：="@" concatenate s concatenate "＃"
• 0から1の範囲のjについては、
  • temp：=0
  • matrix [j、0]：=0
  • i：=1
  • i <=nの間、do
    • s [i--temp-1]はs[i+ j + temp]と同じですが、
      • temp：=temp + 1
    • matrix [j、i]：=temp
    • k：=1
    • while（matrix [j、i --k] is not same as temp --k）and k
    • matrix [j、i + k]：=最小のmatrix [j、i-k]
    • k：=k + 1
  • temp：=tempの最大値-k、0
  • i：=i + k

例

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

def find_substr(s):
   m = dict()
   n = len(s)
   matrix = [[0 for x in range(n+1)] for x in range(2)]
   s = "@" + s + "#"
   for j in range(2):
      temp = 0
      matrix[j][0] = 0
      i = 1
      while i <= n:
         while s[i - temp - 1] == s[i + j + temp]:
            temp += 1
         matrix[j][i] = temp
         k = 1
         while (matrix[j][i - k] != temp - k) and (k < temp):
            matrix[j][i+k] = min(matrix[j][i-k], temp - k)
            k += 1
         temp = max(temp - k, 0)
         i += k
   s = s[1:len(s)-1]
   m[s[0]] = 1
   for i in range(1,n):
      for j in range(2):
         for temp in range(matrix[j][i],0,-1):
            m[s[i - temp - 1 : i - temp - 1 + 2 * temp + j]] = 1
      m[s[i]] = 1
   for i in m:
      print (i)
find_substr("bddaaa")

入力

bddaaa

出力

a
aa
b
aaa
d
dd